A sudoku solver

This module can read the simple representation of a sudoku found in the newspaper and display the solution. Ex:

~$ python sudoku.py
The problem:

       6        7    4   3
            9   6      2
   5        3   4        6

   7 4                 1
   8   9             3   4
     1                 5 7

   2        6   3        5
     3      2   8
   4   5    7        2

A solution:

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

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

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

As a human brain usually scans the sudoku board and eventually deduces the right digit in the slots, the algorithm presented below operates in a different way. The algorithm below starts from the top left slot and stacks up assumptions for which digit is put in a slot, for each slot all the way to the bottom right slot. Eventually backtrack to a previous slot to try a different assumption when no number can be set for the current slot. On the contrary to the human brain, the algorithm does not do deductions but can easily remember a full stack of assumptions, which is something hard to do for the human brain.

The sudoku module offers three objects building a sudoku solver:

• the Sudoku class modelling the sudoku board and sudoku rules,
• the stack_assumptions generic backtracking algorithm. The function takes a list of generator functions as argument,
• the make_generators function returning a list of generator functions suited for manipulating a sudoku and compatible with the bactracking algorithm.

class sudoku.Sudoku(problem)

The Sudoku board class has the methods for reading the start state of a sudoku board, for representing a board. It also has the methods for setting and freeing a digit in a slot of the board, according to the rules of the sudoku game.

board

A 9x9 matrix which contains the digits on the sudoku board. An empty position is represented by a False value

candidates(col, row)

Returns the list of possible values for the slot specified by the arguments, according to the current state of the sudoku board and according to the rules of the sudoku game.

The sudoku rules states that the candidates are the numbers which are not present neither in the column col, neither in the line row, neither in the square identified by col and row.

attempt(*args, **kwds)

A context manager which sets the value of the board at position: col, line on entering the context and which frees the position on exiting the context.

sudoku.stack_assumptions(generators, i=0)

Takes a list of generators. This list is assumed to manipulate a shared representation of the problem. When this algorithm yields, a solution has been found and can be printed.

The algorithm works by calling the generator at the nth position of the list, and pulls the next() method on the iterator returned:

1. either next() returns, in which case, the algorithm instantiates the generator from position n+1 of the input list function and tries to pull its next() method,
2. or the method raises a StopIteration, in which case, the algorithm trigger next() on the generator at position n-1,

This algorithm yields whenever every generator of the list has yielded, at this point, every position of the board is filled with a digit according to the sudoku rules: a solution has been reached and the board can be printed.

When a generator has yielded, this means that a suitable candidate could be found and was set in the board’s slot and that an assumption can be tried on the next slot, with generator i+1.

When a generator raises a StopIteration, then a dead-end was met. A wrong assumption must have been taken somewhere along the stack of the previous recursion: the algorithm backtracks at the previous recursion, another assumption can be attempted.

It is interesting to note that the backtracking algorithm (the algorithm whichis able to stack assumptions) really is independant from the sudoku rules. The algorithm requires an argument with a precise interface and blindly triggers them, whether the argument is manipulating a sudoku, the eight queens or the knight problem. When the algorithm yields, the sudoku board or chessboard manipulated by the argument has cooked a solution.

sudoku.make_generators(sudoku)

Returns a list of candidate generators for use with the backtrack algorithm stack_assumptions. The sudoku argument must provide two functions: candidates(i,j), and attempt(col, row, candidate) and a member attribute called board, which is a 9x9 matrix.

There are as many generator functions than there are slots on the sudoku board, they are stored in a list. Each generator function is specific to a slot: it actually contains the coordinates of the slot, like a closure.

When called for the first time, the generator computes the list of candidate numbers for the slot, according to the current sudoku board. The list of candidates depends on the state of the board at the time the generator is called for the first time.