DLX and Sudoku Solver
Author 
Message 
bbi5291

Posted: Tue May 26, 2009 4:07 pm Post subject: DLX and Sudoku Solver 


Here's my implementation of Knuth's "Algorithm X with Dancing Links", or DLX for short, for solving the exact cover problem. This is in the file dlx.h. The file dlx_driver.cpp is, as its name suggests, a driver for the header, reducing Sudoku to exact cover.
To use the Sudoku solver, simply input 81 cells to standard input. Digits 1..9 represent givens (as one would expect). The digit zero and the period represent blank cells. All other characters are ignored. Thus, input is accepted in several different formats. In most cases you can simply copyandpaste into the console what you find online. (Spaces are ignored, not treated as placeholders. This means if spaces are used as placeholders, this won't work properly. On the other hand if I treat spaces as placeholders, leading and trailing spaces cause problems, which IMHO is worse.)
Solutions are printed to standard output as 9x9 grids of digits  all possible solutions are printed, as they are generated one by one as the recursive algorithm proceeds. Each solution is followed by a blank line. If no solutions are found, nothing will be printed.
Also, before I start getting attacked over my misuse of templates, choice of language, poor commenting, and overall sloppiness, remember that I'm primarily a computer science enthusiast, not a software engineer.
Tested and working on g++ 4.3.2, although it shouldn't cause problems with other compilers.
Description: 

Download 
Filename: 
dlx_driver.cpp 
Filesize: 
1.31 KB 
Downloaded: 
918 Time(s) 
Description: 

Download 
Filename: 
dlx.h 
Filesize: 
5.84 KB 
Downloaded: 
1163 Time(s) 






Sponsor Sponsor



saltpro15

Posted: Tue May 26, 2009 8:37 pm Post subject: RE:DLX and Sudoku Solver 


wow... this is very impressive. I haven't read the full code yet, but I read that wiki and well, wow...






bbi5291

Posted: Tue May 26, 2009 8:45 pm Post subject: Re: DLX and Sudoku Solver 


Actually Wikipedia just has a tendency to formalize mathematical concepts because, well, that's the way they're supposed to be treated. But exact cover is not nearly so difficult as it might seem  given a matrix of 1s and 0s, select a subset of rows to form a new matrix with exactly one 1 in each column. (My code actually removes empty columns; this is not strictly necessary as empty columns actually mean that there is, obviously, no solution to the exact cover problem, but such empty columns are a relic of the algorithm used to fill in the known values.)
The code is intended to show off how fast it is, not how smart I am, or how good I am at coding







