During EMEA@PDC trip to the PDC in September, we had to find something to keep ourselves busy (more than 11 hours flight from Amsterdam to Los Angeles) :-). Wim Verhaegen, sitting next to me, brought a book with Sudoku puzzles he bought on the airport before our (delayed) departure. It was the first time I heard about the thing but after a while we were in the middle of thinking how to automate solving such a puzzle in C# (to geek or not to geek). No laptops involved, just thinking. A few weeks ago, when I was reading my aggregated blog feeds, I noticed a post by Brad Abrams on the same subject: solving Sudoku puzzles somewhere on an altitude of 35000 feet. That was the time I decided to open up my Visual Studio 2005 environment and code our algorithmic ideas in C# 2.0. After a couple of delays to publish the code, here it finally is: download (requires VS2005 or MSBuild).

Other than Brad's code, my solution is:

• ready for Sudoku puzzles of all kinds of dimensions (read: almost ready, because the main function can't work with digits higher than 9 in the current build);
• not doing any guessing or backtracking, it's only using logical reasoning (see below) to (try to) find a solution;
• based on a variety of concepts (mapped to classes), including Cell and Unit (see blow).

This also means that my "Sudoku Solver" is not really a solver, it's a simplifier. Based on two theorems, it tries to fill in cells which can only have one remaining value:

1. If the cell is the only cell in a unit that still has the possibility to contain a specific value, it should have this value.
2. If a cell has only one possibility left (based on elimination through the units it belongs to), it should take that possibility as its value.

Basically, every cell of the puzzle belongs to three units: a row, a column and a tile. For example: A 3x3 Sudoku has 9 rows, 9 columns and 9 tiles. All 81 cells belong to exactly one of each kind of unit. During initialization, cells are created and linked in the associated units. Then, every cell is updated to have a "possibility list" of remaining possibilities. All cells start with all possibilities open (e.g. 1-9). By looking at known cells in the cell's units (row, column, tile) possibilities can be reduced. This kind of "possibility lists" helps to develop rule 2 reductions. In order to support rule 1 reductions, every unit has a list of "possibility counts". For every digit the Sudoku can contain (e.g. 1-9), the cells count of cells that hace that digit as a remaining possibility is maintained (e.g. if a column has 3 cells where 1 occurs in the possibility list, that column will have a mapping 1->3 to indicate that there are 3 cells that have 1 as a possibility). The reduction logic checks every unit for possibility counts that have dropped to 1, which means there's only one cell left in the unit that has a particular digit as its possibility.

For Brad's puzzle, the application reduces the Sudoku only slightly (although most - if not any of them - Sudokus in the local newspapers over here are solved completely using these two theorems). Here's the output:

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

Unknown cells: 54

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

Unknown cells: 46

The Sudoku hasn't been solved completely. Below you'll find open possibilities for each unknown cell.
0,4 - 1,4,8
0,6 - 1,4,8
0,8 - 1,8
1,1 - 2,5
1,2 - 1,2,4,5
1,3 - 6,9
1,4 - 1,4,6,9
1,5 - 1,4,6,9
1,8 - 1,5,6,9
2,0 - 1,4
2,1 - 5,7
2,2 - 1,4,5,7
2,4 - 1,4,6,8,9
2,6 - 1,4,5,6,8,9
2,7 - 1,5,6,8
2,8 - 1,5,6,8,9
3,0 - 1,3,4
3,2 - 1,4,5,7,8
3,3 - 8,9
3,4 - 1,3,4,5,8,9
3,5 - 1,4,8,9
3,6 - 1,5,7,8
3,7 - 1,5,8
4,0 - 1,3
4,2 - 1,5,8
4,5 - 1,6,8
4,6 - 1,5,6,8
4,8 - 1,3,5,6,8
5,1 - 5,7,8
5,2 - 1,4,5,7,8
5,3 - 6,8
5,4 - 1,3,4,5,6,8
5,5 - 1,4,6,8
5,6 - 1,5,6,7,8
5,8 - 1,3,5,6,8
6,1 - 2,8
6,2 - 2,8,9
6,4 - 6,8,9
6,6 - 1,5,6,8,9
6,7 - 1,5,6,8
6,8 - 1,5,6,8,9
7,5 - 6,8,9
7,6 - 6,8,9
7,7 - 6,8
8,2 - 8,9
8,4 - 8,9

A brute-force (read: guessing and backtracking) algorithm can be used to search further on the reduced puzzle that my program spits out.

Notes:

• I've been thinking about a better design for the application based on events to do the bookkeeping when something changes but have not been implementing this yet. It might come later although.
• If anyone can think of another theorem to reduce a puzzle based on certainties (no guessings), please let me know.

Enjoy (but avoid to become a Sudoku addict)!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Filed under: , , ,

### Comments

#### #re: Sudoku solver

Saturday, April 22, 2006 1:01 PM by sudoku online

Hi,
Great article!!
Here you can play sudoku online : http://sudoku.arrelnet.com/