Sudoku

I guess hardly anyone could have missed the Sudoku craze that have swept the world the last couple of years, but in case you just crawled out from under a rock, here is a short summary:
Sudoku is a little logical game. A board is divide into 9x9 squares, and also grouped into 9 3x3 regions or blocks. The aim of the game is to fill in all the numbers from 1 to 9 in each row, column and region. It does not have to be numbers, any set of 9 symbols works, but numbers are nice since they are easily recognized by most people. The challenge is that some of the squares are prefilled with numbers which constrains the game to a single possible solution. Sudoku games can be found in many newspapers and also on the Internet.

Example of a Sudoku game.

Hacking Sudoku

I thought it would be nice to have a little program that helped me solve Sudoku games and perhaps also generated new ones. I first had grand schemes about generating super Sudokus with 25x25 squares or more. However, after reading up a bit on the thing it turned out that solving Sudoku problems in the general case is NP-hard. For the Computer Science challenged out there, it means that there is no known way to find an algorithm that is guaranteed to find a solution in less than polynomic time (i.e. an algorithm that can always find the correct answer in a reasonable amount of time) for all possible puzzles. The program I ended up writing works well for 9x9 games but not larger, unless you are gifted with an exceptional amount of patience...

Solving Sudoku

The basic task of a Sudoku program is the ability to solve games, hopefully reasonably fast. A Google search will reveal several approaches people have used. Roughly one can divide them into two camps, human imitating techniques and brute force search. The human imitating methods tries to solve the game in a logical reasoning way, using similar strategies as a human would. The easiest way to program however, is a brute force backtracking search that test all numbers in all free squares until a solution is found. The search space for that approach can be vast however, and finding solutions can take a surprisingly long time. The are some tricks that can be used to reduce the search space though.

My little program uses the backtracking search approach with the following tricks:

Traverse all free positions on the board first and check which numbers are valid to put in each position.
Traverse all candidates found in step 1 and check if one of them is valid only in that position in its row, column or region. In that case, make it the only candidate for that position.
Sort the positions so we have those with fewest candidates first.
If any positions have only a single candidate (those would now be first in our list of positions), enter those candidates onto the board and repeat from step 1.

If we are lucky, this procedure can solve the whole game, and this is actually quite often the case for games labeled "easy" in papers and on line. If we are not so lucky, we now need to search. I use a simple backtracking search that traverses the remaining positions in the sorted order from the above procedure, starting with the positions with fewest candidates. This normally speeds up the search so that most games are solved within a fraction of a second. Some really tricky ones can take as much as 30 seconds though.

Generating games

My way of generating a new Sudoku game consists of two steps:

Generate a random full board that is a valid solution.
Remove positions from this solution, but make sure there is still only one unique solution.

The first step is not too hard. My approach is to generate a random, but valid, first row and column and then let the program solve the rest of the board. The second step is a bit trickier. A good thing about a searching solution though, is that it is very easy to adapt to search for more than one solution. We just make a note when we find a solution but continue the search as if we had not. As soon as we find another solution we can stop, because we know there are more than one solution which is all we need. If the solution was unique, we will need to search until we run out of positions to try without finding another solution.

My program traverses all positions in random order and tries to clear that position, if the result still has only one solution we move on to the next position. If not, we put the value back before moving on. Since this whole procedure involves solving numerous Sudoku games, some without a unique solution, it can take much longer time than just solving a single game. In some cases more than a minute.

The program

The program itself is easy enough. It is written in C# using VS 2005 so you most likely need .NET 2.0 installed to run it. I provide it here below as a zip file with the complete source inside. A compiled executable is in there as well.

You can enter numbers on the board by clicking a position and typing a number. You can also move around using the arrow keys. Backspace clears the current position. There is also a Clear button that clears the whole board.

The Solve and Generate buttons should be self explanatory. A couple of minor things in the GUI might be worth pointing out though. When solving, there is a small text box down to the left that displays the search depth. That is simply how many candidates that had to be tried before a solution was found. I don't know if a large search depth actually corresponds to a game that is also hard for humans to solve, but it might be a hint. Also note the neat little trick of using the same text box as a progress bar during game generation.

There is another button as well, labeled Hint. It might be useful if you want to solve games yourself and use the program as an easy way to enter and erase numbers on a board. The Hint button will run step 1 and 2 of the solution procedure described above and then draw colored circles in the positions with the fewest resulting candidates. A red circle means a single candidate, an orange one means two and a yellow circle means three candidates. No circle means more than three.

Example of a Sudoku game with hints displayed

Result

Here you can download the complete Visual Studio solution to play with. I have also put a ready made executable version of the program in the top directory for your convenience. As mentioned above, you will need .NET framework 2.0 to run this. You can also click here, or on the Play Sudoku link in the menu, to get to a page where you can run the program directly from the web.

Download the file

Happy Hacking!