Sudoku solver program: A challenge just for fun.

Some years ago, newspapers and magazines worldwide introduced us a novelty puzzle: the sudoku. The game gained popularity from its first publishing, in 1979, becoming an international hit in 2005.

A sudoku puzzle.

Then, we decided to design a computer program to solve the puzzle automatically, using AI techniques — just a programming challenge. In this post we show you how the program works; explaining first the theory and then how was it coded.

The algorithm basis

The method used to solve a sudoku is inspired on a classic AI technique: a heuristic search procedure.

Consider the whole space of sudoku puzzles, this is, 9×9 matrixes, satisfying or not the yet well-known game rules — let’s call ‘state’ to any of these matrixes. Consider also transitions among states representing the possible settings of a given digit for a given empty cell in a sudoku table. Therefore, there are some sequences of states —differing only a digit between a given state and the next one— that lead to the final state: the puzzle solved.

But think about it: there are millions of possibilities, and only a few ones are valid. How can we find the good ones avoiding to run thru the whole tree of states? Using an heuristic is the answer.

In order to let the algorithm to find a good sequence of states (to solve the puzzle), we must define an utility function. That functions gives us an estimation of the goodness of any possible movement. Then we can use it applied on any empty cell to know how good is to try filling that cell with any valid digit. Choosing the right cell to fill is very important and filling it should reduce the most uncertainty as possible.

So we need an heuristic with an utility function that depends on the number of possibilities going from a given state to another valid one. The function we have choosen is the one that gives the number of candidates for a given empty cell in the puzzle, so if a cell can fit any of N digits without violate the puzzle rules the function will return N.

Then we operate recursively on the puzzle matrix, choosing the empty cell with less candidates and trying to fill it with each one of those digits. If we reach a state with empty cells but no candidates we must undo some actions and keep on trying with other candidates and other cells. At the end, we get a state with no empty cell; that means the puzzle is solved.

The code

The program’s code is simple and easily understandable. There are three major functions, working together, to perform the heuristic algorithm. We defined a procedure to look for empty cells in a sudoku table, another procedure that tries to fill those empty cells with the candidates given by the third function: the heuristic itself. These functions are called, respectively, do_sudoku, try_a_number and find_candidates.

The do_sudoku function looks for blanks in a given sudoku, calculates the candidate digits for those blanks and tries to solve the puzzle filling the empty cell that has less candidates. All the work is done applying this rule recursively.

The try_a_number function iterates recursively the algorithm, trying to fit a candidate digit in a given empty cell. If it reaches a ‘dead-end’ state, returns undoing that try.

The find_candidates function looks for all fittable digits for a given cell. It checks if a digit is not being used in the same row, the same column and the same 3×3 block; in this case, it’s a valid candidate.

Results

After trying the program with several sudokus, we have observed that:

• This is a very simple algorithm with no optimizations. With the most of the cases it finds a solution quickly. Nothing is done in order to shortcut some trivial or repetitive cases.
• Memory consumption: Tables are backuped at each recursion. Therefore, the memory allocated is proportional to the maximum level of recursion achieved; this is equivalent to the number of empty cells at the initial state.

Links

• Sudoku solver source code.