Sudoku Solver
What is this?
This program will solve a puzzle following the rules of Sudoku. A description of the rules used can be found at http://en.wikipedia.org/wiki/Sudoku.
The application implements a N x N puzzle. There is a constant in block3x3.h which defines the size of the puzzle. The name of the constant is BLOCKSIZE.
How does it work?
It is a command line application that can take several parameters.
-h/-? : Shows help
-s old|simann : Uses old style or Simulated Annealing to search for a solution.
-i filename : This loads a text file with initial values for the puzzle. The
format of the file is as follows:
x y value
Where x and y is in the range 0 to ( NN ) - 1 and value is in the range 1 to NN.
Very little verification is done on this file, so I expect many bugs related to this function. It will not detect if an impossible starting condition has been set.
The application will load the initial state ( if specified ), initialize the rest of the puzzle to random values and then do a search to find a solution where the conditions of the game has been met.
Performance
With version 0.0.5 I had the following experimental results for solving puzzles.
With the original (old) search technique, I had the following results:
N rounds time 2 12 - 31 < 1 second 3 815 - 2706 < 1 second 4 16500 - 20954 < 1 second 5 121347 - 148071 1 - 2 seconds 6 441864 - 1048322 9 - 23 seconds 7 2584317 - 20384945 87 - 679 seconds
With version 0.0.4 a new technique was introduced: Simulated Annealing. It seems to perform better for large N. Further improvements may be possible by mixing the search algorithm by using the old style for large error values and switching to the new style for small error values.
With Simulated Annealing I had the following experimental results:
N rounds time
2 10 - 144 < 1 second
3 152851 - 172192 1 second
4 234445 - 239997 1 second
5 320521 - 440319 4 - 5 seconds
6 799286 - 1090965 18 - 26 seconds
7 3062905 - 3653777 106 - 128 seconds
With version 0.0.5 I introduced a "mixed" search that mixed the old search technique with simulated annealing. With the mixed search I had the following experimental results:
N rounds time
2 5 - 111 < 1 second
3 641 - 2262 < 1 second
4 18128 - 21799 < 1 second
5 124580 - 195620 1 - 2 seconds
6 664994 - 1039628 14 - 22 seconds
7 3143163 - 4807989 106 - 161 seconds
Something to remember is that due to the nature of the search algorithm the time to solve a puzzle can vary widely.
These times were on an AMD64 3700+ running 64-bit Linux over at least 3 runs for every test. Yes, I know it does not make for good statistics. But this is a hobby, not a scientific paper.
Does these times imply anything about the different technique's? Not really. All of these techniques are non-deterministic and has parameters that can be modified to change their behavior. There are probably better parameters that can be selected, I have just not found them yet.
Are there better algorithms for solving Sudoku? For small BLOCKSIZE's: Without a doubt. For larger BLOCKSIZE's, likely. I will try to find them and implement them.
Compiling
This code has been tested on Mac OS X, Solaris Sparc and Linux.
Just run ./configure. If you want optimization enabled set CXXFLAGS=-O3 before running configure.
Then type make.
The binary is in the src folder.
License
GPL license as can be found at
http://www.gnu.org/licenses/licenses.html#GPL
The GPL license is also included in the COPYING file in the distribution.
Disclaimer
This software is as is. I do not guarantee that it will do anything at all. I have tested it, and it works for me. The source is available, you are welcome to look at it and fix any bugs you find.