I started doing those Sudoku like puzzles in the NYT Magazine while working on the crossword. I figured why not write a solver.
My first pass was to do a mostly naive depth-first search with backtracking. It solved most 7x7 puzzles in around 10ms, so I decided not to go for the fancier exact cover approach. I also didn't really use any heuristics other than fixing the squares with equality constraints.
My second pass was to add some heuristics to cutoff the search sooner once I could know that a constraint was for sure going to be violated. This brought 7x7 puzzles down to about 1.5ms, and then I took another 0.5ms off through some simple optimizations. 5x5 puzzles are solved in around 20us.
Final pass on this as I should stop playing with this tiny project, but I really wanted to get the 7x7 time below 1ms. One final optimization where I check the rows and columns for a hole before putting in a guess to only use unused values. Before I was just starting at 1 and incrementing by 1 and letting the constraint violation handle the issue. This small change cuts the 7x7 time roughly in half so that the full solve time including parsing the input file is about 600us (see numbers at the bottom). Any more optimization at this point would probably not be worthwhile.
But wait, there's more. I forgot that since I am handling the unique row/column constraint inside the search generator, I don't actually ever need to check those and therefore don't even need to create them. So I deleted a bunch of code and cut the runtime in half again. The average 7x7 time is now around 250us. This is down from about 10ms for the most naive approach, i.e. 97.5% faster.
Example input:
7
AABBBCC
DEEFFGG
DHJLMMG
IHJNNOO
IKJJPQQ
RRRSPTU
VVWSPTU
A - 3
B * 84
C - 5
D / 3
E - 1
F / 2
G + 16
H - 1
I - 2
J + 18
K = 7
L = 2
M - 1
N + 6
O / 2
P + 10
Q - 3
R * 126
S + 8
T / 2
U + 8
V + 10
W = 1
The first line, N, is the size, either 5 or 7. The code can handle any integer up to (and including) 9,
but the magazine only has the two sizes. Followed by N lines each with N characters which
represents the puzzle grid. A unique char is required to represent each grouping, any ascii will
work just fine, I use capital letters. Then follows the constraints, this will be one for each
character used in the grid. There are 5 different constraint types, each with the format:
X o nnnn
where X is the character used in the grid above, o is the operation, one of +, -, *, \,
or =, and nnnn is the value from the puzzle. The = operation is for the squares in the puzzle
where it just tells you what the number is.
There are a few example files included in the repo, these are used with the benchmark suite.
This is built using Rust, so for speed you should probably use the release build:
$ cargo build --release
$ ./target/release/kenken [file]
where [file] is the path to the file containing the input data. If this is missing it is assumed
to be puzzle.dat in the current working directory.
If you want to see some extra output, you can use the RUST_LOG=kenken=xxx environment variable to
turn on logging, where xxx is one of trace, debug, info, warn. Each higher level gives
less information. If you want to see how many steps it took just turn on the info level. The lower
levels print out intermediate grids.
For example, with the above example input in puzzle.dat I get this on my machine:
[weiss:kenken (master)]$ RUST_LOG=kenken=info time ./target/release/kenken puzzle.dat
INFO kenken > loading puzzle.dat
INFO kenken::solver > Done @ 1729
2 5 3 4 7 6 1
1 4 5 3 6 7 2
3 1 6 2 4 5 7
7 2 4 5 1 3 6
5 7 2 6 3 1 4
6 3 7 1 2 4 5
4 6 1 7 5 2 3
0.00 real 0.00 user 0.00 sys
So it took 1729 steps to get a solution in a small amount of time. The previous
verison took 7229 steps, and the one before that took 45596.
$ cargo bench
There are also benchmarks using criterion.rs which measure solving different size puzzles. I split out the solving bit from the input processing step to get the speed for just that part, but I also have a benchmark for the whole process. Spoiler: the input processing takes a negligble amount of time.
The most recent runs on my machine for the four benchmarks after the last set of changes are:
solve 5 time: [6.4186 us 6.4721 us 6.5341 us]
change: [-62.624% -60.445% -58.244%] (p = 0.00 < 0.05)
Performance has improved.
Found 15 outliers among 100 measurements (15.00%)
10 (10.00%) high mild
5 (5.00%) high severe
solve 6 time: [10.271 us 10.396 us 10.537 us]
change: [-58.932% -58.211% -57.437%] (p = 0.00 < 0.05)
Performance has improved.
Found 10 outliers among 100 measurements (10.00%)
9 (9.00%) high mild
1 (1.00%) high severe
solve 7 time: [246.64 us 248.53 us 250.55 us]
change: [-58.672% -57.940% -57.187%] (p = 0.00 < 0.05)
Performance has improved.
Found 4 outliers among 100 measurements (4.00%)
4 (4.00%) high severe
solve 7 full time: [274.45 us 277.40 us 280.54 us]
change: [-54.924% -53.916% -52.864%] (p = 0.00 < 0.05)
Performance has improved.
Found 8 outliers among 100 measurements (8.00%)
4 (4.00%) high mild
4 (4.00%) high severe
They should be self-explanatory, the time is a 95% confidence interval about the mean.
Sudoku puzzles are almost a subset of Kenken, the only variation being the latin square constraint,
i.e. each 3x3 grid must contain each digit in 1-9 once. The row and column constraints are the same,
and the known values are equality constraints like in Kenken. So I also added one more constraint
type, B for box. It still has the same format as the other ones but the "character" is ignored, and the
value is the size of the boxes. So the below is an example Sudoku puzzle input:
9
....A....
BC....D.E
FGHI.....
.J...KL..
M.......N
..OP...Q.
.....RSTU
V.W....XY
....Z....
A = 5
B = 4
C = 2
D = 3
E = 1
F = 8
G = 9
H = 5
I = 4
J = 5
K = 8
L = 7
M = 9
N = 4
O = 3
P = 6
Q = 9
R = 1
S = 4
T = 6
U = 3
V = 3
W = 8
X = 1
Y = 5
Z = 6
. B 3
This is a harder puzzle so it takes quite a few steps:
[weiss:kenken (master)]$ RUST_LOG=kenken=info time ./target/release/kenken sudoku.dat
INFO kenken > loading sudoku.dat
INFO kenken::solver > Done @ 11121
6 3 1 7 5 2 8 4 9
4 2 7 8 9 6 3 5 1
8 9 5 4 1 3 6 7 2
1 5 2 9 4 8 7 3 6
9 8 6 1 3 7 5 2 4
7 4 3 6 2 5 1 9 8
2 7 9 5 8 1 4 6 3
3 6 8 2 7 4 9 1 5
5 1 4 3 6 9 2 8 7
But without doing anything fancy, it is still decently fast:
sudoku evil time: [2.9185 ms 2.9592 ms 3.0021 ms]