Jay Zelos - SuDoku Solver

SuDoku

SuDoku is a Japanese puzzle game whereby a grid of nine by nine boxes must be filled with the numbers one to nine, no number may appear more than once in a single column or row and its three by three sub grid. Puzzles are set by filling in a few of the numbers so that by a process of elimination the remainder can be found. Sometimes the harder puzzles require a bit of guess work when the grid has no cells with single possibilities and no deductions can be made, (this script will not solve puzzles involving guesswork).

More information can be found at http://en.wikipedia.org/wiki/Sudoku.

Solution

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

Completed in 2 passes.

Solved in 0s

Progress

Inital Table

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

Pass 1

(0,1) : 2 - found unique.
(0,8) : 4 - found by deduction
(1,2) : 3 - found by deduction
(1,3) : 2 - found by deduction
(1,6) : 6 - found unique.
(1,8) : 1 - found unique.
(2,1) : 9 - found unique.
(2,5) : 4 - found by deduction
(2,7) : 3 - found unique.
(3,2) : 1 - found by deduction
(3,3) : 3 - found by deduction
(3,5) : 8 - found unique.
(3,7) : 7 - found unique.
(3,8) : 9 - found unique.
(4,4) : 7 - found unique.
(4,6) : 2 - found by deduction
(4,8) : 5 - found by deduction
(5,0) : 4 - found by deduction
(5,1) : 7 - found unique.
(5,3) : 1 - found unique.
(5,5) : 5 - found unique.
(5,6) : 8 - found unique.
(6,1) : 5 - found unique.
(6,3) : 9 - found unique.
(6,4) : 6 - found unique.
(6,7) : 2 - found unique.
(6,8) : 8 - found unique.
(7,2) : 7 - found by deduction
(7,5) : 2 - found unique.
(7,6) : 3 - found unique.
(8,0) : 2 - found by deduction
(8,2) : 6 - found unique.
(8,4) : 3 - found by deduction
(8,5) : 1 - found unique.
(8,7) : 4 - found unique.
(8,8) : 7 - found unique.

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

Pass 2

(0,0) : 6 - found by deduction
(0,3) : 7 - found unique.
(0,4) : 1 - found unique.
(0,6) : 5 - found unique.
(2,0) : 1 - found unique.
(2,4) : 8 - found unique.
(4,0) : 8 - found by deduction
(4,2) : 9 - found unique.
(7,0) : 9 - found unique.

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

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

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

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

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

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

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

http://www.zelos.org.uk