I came across str8ts puzzles recently and want to implement have implemented a
solver in Common Lisp similar to my binoxxo solver. I am using basic ideas from
Peter Norvig’s Soduko solver as implemented here or here in Common Lisp.
While in a Sudoku puzzle the units are always the same for every puzzle, in str8ts the units have to be found for each puzzle due to varying the blocked fields and digits.
I have chosen to encode a blocked field with 10 and a digit within a blocked
field with a negative integer. A puzzle is read from a text file with one
puzzle per line given a integers from -9 to 10 separated by white space.
I am sure there are certain things which could be improved with respect to
performance. I have chosen to store the puzzle itself in a two-dimensional array
allowing to access the fields in a straight-forward way. The calculation of the
units and sub-units is not optimized for space or speed. I found the usage
of lists of lists pretty straight-forward during implementation and am pretty
happy with it.
After reading the puzzle from the file for each field the impossible digits are
eliminated using assign and eliminate. Then for the field with the least
possible digits the next step is generated and further checked using
search-puzzle and valid-puzzle-p until solvedp signals that the puzzle is
solved.
Load and test the program with:
(asdf:make :str8ts)
(asdf:test-system :str8ts)See the directory puzzles for the given puzzles or add more yourself.
To solve a puzzle use solve-puzzle:
(solve-puzzle #p"puzzles/2019-01-29-hard")
Initial puzzle:
-----------------------------------------------------
| 10 | 0 | 0 | -8 | 4 | 0 | 0 | 0 | 10 |
| 10 | 0 | 0 | -1 | 0 | 0 | 10 | 0 | 9 |
| 0 | 0 | 2 | 10 | 0 | 0 | -7 | 0 | 0 |
| 0 | 0 | 10 | 0 | 0 | 10 | 0 | 0 | 10 |
| 10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 10 |
| 10 | 0 | 0 | 10 | 0 | 0 | -9 | 0 | 2 |
| 7 | 0 | -4 | 0 | 0 | 10 | 0 | 1 | 0 |
| 0 | 0 | -5 | 0 | 0 | 10 | 0 | 0 | -6 |
| 10 | 0 | 0 | 0 | 0 | -2 | 0 | 0 | 10 |
-----------------------------------------------------
Final state:
-----------------------------------------------------
| 10 | 2 | 1 | -8 | 4 | 5 | 6 | 7 | 10 |
| 10 | 4 | 3 | -1 | 7 | 6 | 10 | 8 | 9 |
| 3 | 1 | 2 | 10 | 5 | 4 | -7 | 9 | 8 |
| 4 | 3 | 10 | 2 | 1 | 10 | 5 | 6 | 10 |
| 10 | 6 | 7 | 3 | 2 | 8 | 4 | 5 | 10 |
| 10 | 5 | 6 | 10 | 8 | 7 | -9 | 3 | 2 |
| 7 | 8 | -4 | 5 | 6 | 10 | 2 | 1 | 3 |
| 8 | 9 | -5 | 4 | 3 | 10 | 1 | 2 | -6 |
| 10 | 7 | 8 | 6 | 9 | -2 | 3 | 4 | 10 |
-----------------------------------------------------
Puzzle solved in 0.005 seconds.Thanks to the wonderful vecto package the puzzles can also be drawn instead of
just print them to the REPL.
(draw-puzzle (make-puzzle) #p"puzzle.png")
(draw-puzzle (search-puzzle (make-puzzle) 0) "solved.png")Or just:
(solve-puzzle "puzzles/2019-03-05-hard" :draw t)
Although I claimed before that I am happy with my solution, the performance is
quite poor, s. below. Obviously, generating every puzzle and then reject it
because of in-valid sub-units makes not sense. I have to change eliminate to
take care of the checking for valid candidates.
STR8TS> (solve-puzzle "puzzles/2019-03-05-hard")
Initial puzzle:
-----------------------------------------------------
| 3 | 0 | 10 | 10 | 9 | 0 | 0 | 10 | -4 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 10 | 10 | 0 | 0 | 8 | -5 | 10 | 0 | 0 |
| 0 | 10 | 10 | 0 | 0 | 10 | 0 | 0 | -1 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| -7 | 0 | 6 | -3 | 0 | 0 | 10 | 10 | 0 |
| 0 | 0 | 10 | 10 | 0 | 0 | 0 | -9 | 10 |
| 0 | 0 | 3 | 0 | 0 | 0 | 0 | 0 | 0 |
| 10 | 10 | 0 | 0 | 0 | 10 | -8 | 5 | 0 |
-----------------------------------------------------
Final state:
-----------------------------------------------------
| 3 | 2 | 10 | 10 | 9 | 8 | 7 | 10 | -4 |
| 2 | 1 | 8 | 9 | 5 | 7 | 6 | 4 | 3 |
| 10 | 10 | 7 | 6 | 8 | -5 | 10 | 1 | 2 |
| 5 | 10 | 10 | 7 | 6 | 10 | 4 | 3 | -1 |
| 4 | 6 | 5 | 8 | 7 | 1 | 3 | 2 | 9 |
| -7 | 5 | 6 | -3 | 1 | 2 | 10 | 10 | 8 |
| 8 | 7 | 10 | 10 | 4 | 3 | 2 | -9 | 10 |
| 9 | 8 | 3 | 5 | 2 | 4 | 1 | 6 | 7 |
| 10 | 10 | 2 | 4 | 3 | 10 | -8 | 5 | 6 |
-----------------------------------------------------
Puzzle solved in 13.034 seconds.
T
measuring PROFILE overhead..done
seconds | gc | consed | calls | sec/call | name
--------------------------------------------------------------
0.690 | 0.020 | 405,385,632 | 34,094 | 0.000020 | VALID-PUZZLE-P
0.427 | 0.049 | 16,511,376 | 220,724 | 0.000002 | LIST-PLACES-WITH-SINGLE-UNIT-SOLUTION
0.420 | 0.003 | 35,634,048 | 2 | 0.210000 | DRAW-PUZZLE
0.256 | 0.007 | 76,331,952 | 2,411,095 | 0.000000 | VALID-SUBUNIT-P
0.177 | 0.004 | 33,642,896 | 14,527 | 0.000012 | FIND-FIELD-WITH-FEWEST-POSSIBILITIES
0.146 | 0.000 | 16,354,864 | 68,186 | 0.000002 | COPY-PUZZLE-ARRAY
0.022 | 0.000 | 5,963,776 | 42,585 | 0.000001 | FIRST-SET-VALUE
0.021 | 0.000 | 0 | 220,724 | 0.000000 | UNSET-POSSIBLE-VALUE
0.009 | 0.000 | 0 | 14,529 | 0.000001 | SOLVEDP
0.004 | 0.000 | 1,539,824 | 34,093 | 0.000000 | COPY-PUZZLE
0.004 | 0.000 | 819,200 | 14,527 | 0.000000 | LIST-ALL-POSSIBLE-DIGITS
0.001 | 0.000 | 0 | 1 | 0.000776 | PUZZLE-SUB-UNITS
0.000 | 0.000 | 32,768 | 2,018,680 | 0.000000 | ELIMINATE
0.000 | 0.000 | 98,304 | 121 | 0.000000 | LIST-UNITS-CONTAINING
0.000 | 0.000 | 0 | 1 | 0.000000 | MAKE-PUZZLE
0.000 | 0.000 | 0 | 42,592 | 0.000000 | ELIMINATE-VALUE-IN-UNITS
0.000 | 0.000 | 36,144 | 1 | 0.000000 | READ-GRID
0.000 | 0.000 | 0 | 57 | 0.000000 | SPLIT-SUB-ROWS
0.000 | 0.000 | 0 | 226 | 0.000000 | IN-SUB-UNIT-P
0.000 | 0.000 | 0 | 2,018,680 | 0.000000 | VALUE-IS-SET-P
0.000 | 0.000 | 0 | 1,397,411 | 0.000000 | COUNT-REMAINING-POSSIBLE-DIGITS
0.000 | 0.000 | 65,504 | 2 | 0.000000 | PRINT-PUZZLE
0.000 | 0.000 | 0 | 57 | 0.000000 | FIND-SUB-UNITS
0.000 | 0.000 | 0 | 1 | 0.000000 | SOLVE-PUZZLE
0.000 | 0.000 | 0 | 1 | 0.000000 | PUZZLE-UNITS
0.000 | 0.000 | 0 | 65,283 | 0.000000 | ASSIGN
0.000 | 0.000 | 0 | 34,094 | 0.000000 | SEARCH-PUZZLE
0.000 | 0.000 | 0 | 2,983,534 | 0.000000 | ONLY-POSSIBLE-VALUE-IS-P
0.000 | 0.000 | 0 | 57 | 0.000000 | SPLIT-SUB-COLS
--------------------------------------------------------------
2.176 | 0.083 | 592,416,288 | 11,635,885 | | Total
estimated total profiling overhead: 10.64 seconds
overhead estimation parameters:
6.0e-9s/call, 9.14e-7s total profiling, 4.22e-7s internal profilingAfter some optimization and implementing only-valid-digits to reduce the
search space to valid possibilities only, I gained some speed:
STR8TS> (solve-puzzle "/Users/Martin/Documents/src/lisp/str8ts/puzzles/2019-03-05-hard")
Initial puzzle:
-----------------------------------------------------
| 3 | 2 | 10 | 10 | 9 | 8 | 7 | 10 | -4 |
| 0 | 0 | 0 | 0 | 0 | 0 | 6 | 0 | 0 |
| 10 | 10 | 0 | 0 | 8 | -5 | 10 | 0 | 0 |
| 0 | 10 | 10 | 0 | 0 | 10 | 0 | 0 | -1 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| -7 | 5 | 6 | -3 | 0 | 0 | 10 | 10 | 0 |
| 0 | 0 | 10 | 10 | 0 | 0 | 0 | -9 | 10 |
| 0 | 0 | 3 | 0 | 0 | 0 | 0 | 0 | 0 |
| 10 | 10 | 0 | 0 | 0 | 10 | -8 | 5 | 6 |
-----------------------------------------------------
Final state:
-----------------------------------------------------
| 3 | 2 | 10 | 10 | 9 | 8 | 7 | 10 | -4 |
| 2 | 1 | 8 | 9 | 5 | 7 | 6 | 4 | 3 |
| 10 | 10 | 7 | 6 | 8 | -5 | 10 | 1 | 2 |
| 5 | 10 | 10 | 7 | 6 | 10 | 4 | 3 | -1 |
| 4 | 6 | 5 | 8 | 7 | 1 | 3 | 2 | 9 |
| -7 | 5 | 6 | -3 | 1 | 2 | 10 | 10 | 8 |
| 8 | 7 | 10 | 10 | 4 | 3 | 2 | -9 | 10 |
| 9 | 8 | 3 | 5 | 2 | 4 | 1 | 6 | 7 |
| 10 | 10 | 2 | 4 | 3 | 10 | -8 | 5 | 6 |
-----------------------------------------------------
Puzzle solved in 0.082 seconds.
T
seconds | gc | consed | calls | sec/call | name
---------------------------------------------------------
0.408 | 0.005 | 35,691,440 | 2 | 0.204000 | DRAW-PUZZLE
0.005 | 0.000 | 0 | 8,076 | 0.000001 | COUNT-REMAINING-POSSIBLE-DIGITS
0.003 | 0.000 | 131,072 | 84 | 0.000039 | FIND-FIELD-WITH-FEWEST-POSSIBILITIES
0.002 | 0.000 | 688,128 | 1,272 | 0.000002 | ONLY-VALID-DIGITS
0.002 | 0.000 | 229,376 | 2,628 | 0.000001 | LIST-ALL-POSSIBLE-DIGITS
0.002 | 0.000 | 32,768 | 457 | 0.000004 | FIRST-SET-VALUE
0.002 | 0.000 | 0 | 12,508 | 0.000000 | ONLY-POSSIBLE-VALUE-IS-P
0.001 | 0.000 | 131,056 | 2 | 0.000500 | PRINT-PUZZLE
0.001 | 0.000 | 65,376 | 316 | 0.000003 | COPY-PUZZLE-ARRAY
0.001 | 0.000 | 0 | 1,272 | 0.000000 | UNSET-POSSIBLE-VALUE
0.000 | 0.000 | 65,536 | 1,045 | 0.000000 | LIST-PLACES-WITH-SINGLE-UNIT-SOLUTION
0.000 | 0.000 | 262,064 | 7,246 | 0.000000 | VALID-SUBUNIT-P
0.000 | 0.000 | 0 | 57 | 0.000000 | SPLIT-SUB-COLS
0.000 | 0.000 | 0 | 1 | 0.000000 | PUZZLE-UNITS
0.000 | 0.000 | 0 | 25,064 | 0.000000 | VALUE-IS-SET-P
0.000 | 0.000 | 0 | 57 | 0.000000 | FIND-SUB-UNITS
0.000 | 0.000 | 0 | 85 | 0.000000 | SEARCH-PUZZLE
0.000 | 0.000 | 98,304 | 226 | 0.000000 | IN-SUB-UNIT-P
0.000 | 0.000 | 0 | 464 | 0.000000 | ELIMINATE-VALUE-IN-UNITS
0.000 | 0.000 | 0 | 1,272 | 0.000000 | INTEGERS->DIGITS
0.000 | 0.000 | 0 | 1,095 | 0.000000 | ASSIGN
0.000 | 0.000 | 0 | 1 | 0.000000 | VALID-PUZZLE-P
0.000 | 0.000 | 0 | 1 | 0.000000 | SOLVE-PUZZLE
0.000 | 0.000 | 0 | 1 | 0.000000 | READ-GRID
0.000 | 0.000 | 32,768 | 158 | 0.000000 | COPY-PUZZLE
0.000 | 0.000 | 0 | 57 | 0.000000 | SPLIT-SUB-ROWS
0.000 | 0.000 | 0 | 1 | 0.000000 | MAKE-PUZZLE
0.000 | 0.000 | 0 | 25,064 | 0.000000 | ELIMINATE
0.000 | 0.000 | 0 | 1 | 0.000000 | PUZZLE-SUB-UNITS
0.000 | 0.000 | 0 | 86 | 0.000000 | SOLVEDP
0.000 | 0.000 | 65,536 | 121 | 0.000000 | LIST-UNITS-CONTAINING
---------------------------------------------------------
0.427 | 0.005 | 37,493,424 | 88,720 | | Total
estimated total profiling overhead: 0.08 seconds
overhead estimation parameters:
4.0000003e-9s/call, 8.8599995e-7s total profiling, 3.48e-7s internal profilingAfter finding the final(?) bugs this is pretty impressive for my standards. I
had to make sure that the *units* were calculated correctly and the digits
were set to reasonable values, then I do not have to check each puzzle for
validity and save quite some time. I guess I really will leave it as it is this
time…
I found great help at Stackoverflow for some detail problems which is gratefully acknowledged.