# Sudoku Solver
	
I'm not a fervent sudoku solver but I always wanted to try implementing a program
to solve the puzzles faster than I can.The program uses Qt 5 for its user interface, 
you will need to have it installed to build or run the program.
	
## Building

Basic building instructions:

    autoreconf -i
    mkdir build
    cd build
    ../configure --with-qt-includes=/usr/include/qt
    make
			
The binary is called 'sudoku' and will be located in the 'src' directory.
You can run it from within the build directory:
	
    src/sudoku

## Usage

Running the program will show the main window, which consists of a basic
9x9 sudoku grid and a number of menu options.
	
### Game menu
	
The *New* option will clear the current game

The *Load* option allows you to load a previously loaded game.

The *Save* option allows you to save the current sudoku puzzle to the current file.

The *Save As* option allows you to save the current sudoku puzzle to a new file.

The *Revert* option will reload the current file from disk.
 
The *Quit* option will close the program.
	
### Move menu
	
The *Step* option will try to solve a single random unsolved cell,
using the sudoku rules only.
		
The *Guess* option will try to solve a single random unsolved cell,
and will guess (search) for a solution as required.
		
The *Solve Rules* option will try to solve the game,
using sudoku rules only.
		
The *Find Solution* option will try to solve the game,
and will guess (search) for a solution where required.
		
The *Validate* option will verify if the current puzzle is valid.

### Settings menu

* The *Mark solveable* option will, if enabled, mark cells that can be solved without guessing in yellow.
	
## Save game file format

The file format is extremely simple:
the files can be opened and edited with a text editor.
Unsolved positions are saved as well and are indicated by zeroes.
	
Example:
	
		0 0 0  8 0 2  9 0 0
		0 0 0  9 0 7  3 6 0
		4 0 9  0 0 0  0 0 7

		0 8 0  0 0 5  0 4 6
		1 3 0  0 7 8  0 0 0
		0 0 0  2 0 0  0 7 0

		3 4 6  1 2 0  7 0 0
		0 1 0  0 0 0  6 0 2
		0 5 0  0 8 0  0 0 0

While the file format is optimized for readability, the program will
actually ignore extra whitespace while loading a file. This allows you to
load games from a simple file with a sequence of 81 numbers.
	
## Algorithm

The constraint solver will try to find a solution by applying
two sets of sudoko constraints: the sudoku elimination rules, 
where every number from 1 to 9 can only appear once in every row, column and subgrid,
and the sudoko inclusion rules, where every number has to appear exactly once
in every row, column and subgrid.
	
The search solver will apply constraints until there are no cells left with a unique solution.
From there, it will pick a random unsolved cell, fill it with one of the remaining possibilities
and recurse into the next iteration. 
	
## Copyright

This sudoku solver was written by Stijn "Ingar" Buys and is available under
the terms and conditions of the GNU Public License, version 3 or higher.