| Mark
| Joined: 19 Oct 2005 | Posts: 30 | : | Location: Arizona | Items |
|
Posted: Fri Nov 11, 2005 9:36 am Post subject: Fast Compact Solver using Knuth's DANCE Program |
|
|
Here's a 38-line program that solves sudokus with reasonable efficiency:
http://home.comcast.net/~mshelor/files/sudeku
It uses Donald Knuth's DANCE program to do all the heavy lifting. You can find a copy of dance.c at:
http://home.comcast.net/~mshelor/files/dance.c
Note that this is a slightly re-configured version of Knuth's original program; the following four constants
Code: | #define max_level 81
#define max_degree 9
#define max_cols (324+1)
#define max_nodes (4*729) |
have been redefined to fit the constraints imposed by Sudoku.
To set up the solver, compile dance.c and store the executable (along with sudeku) in your path. You can then feed a puzzle to "sudeku" via standard input or a file:
Code: | $ sudeku 48-unwind.dat
185923764
234687519
697514382
471398256
968275431
523461978
316742895
749856123
852139647 |
Mark |
|