rsandila / sudoku-solver Goto Github PK

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 ( N*N ) - 1 and value is 
in the range 1 to N*N.

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.