"""
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.
"""
import array
from contextlib import contextmanager
class Sudoku(object):
[docs] """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."""
def __init__(self, problem):
newarray = lambda: array.array('i', [0] * 9)
# helper of initialisation of the data structures
# Private bitfield presence sets
self._lines = newarray() # Lines, columns and
self._columns = newarray() # square are bitfields of length 9.
self._squares = newarray() # When bit 3 is set in lines[5], 3
# is present in the fifth line.
self.board = [newarray() for i in range(9)]
# a 9x9 matrix of of ints between 1 and 9, an empty position
# is represented by a false value.
# Reading the problem
k=0
for i in range(9):
for j in range(9):
if int(problem[k]) != 0:
self.set(i, j, int(data[k]))
k+=1
_one = lambda self, val, index: val | 1 << index - 1
_zero = lambda self, val, index: val & ~(1 << index - 1)
_get = lambda self, val, index: (val >> index - 1) & 1
# Bitfield manipulation
def set(self, i, j, val):
"""Sets a new digit on the board in position i,j. This only
updates the board *without* checking first if the rules of the
sudo game are respected"""
self.board[i][j] = val
# Not only update the board but also the lines, columns and
# squares arrays
self._lines[i] = self._one(self._lines[i], val)
self._columns[j] = self._one(self._columns[j], val)
self._squares[(j/3)*3+i/3] = self._one(
self._squares[(j/3)*3+i/3], val)
def free(self, i, j):
"""Frees the slot in position i,j"""
# The value to be removed from the lines, columns and square
# presence set is found in the *board* member attribute
val, self.board[i][j] = self.board[i][j], 0
# Also update the line, column and square presence sets.
self._lines[i] = self._zero(self._lines[i], val)
self._columns[j] = self._zero(self._columns[j], val)
self._squares[(j/3)*3+i/3] = self._zero(
self._squares[(j/3)*3+i/3], val)
@contextmanager
def attempt(self, col, row, candidate):
[docs] """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."""
self.set(col, row, candidate)
yield
self.free(col, row)
def candidates(self, col, row):
[docs] """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*."""
return filter(
lambda val: all( not self._get(bf, val) for bf in (
self._lines[col],
self._columns[row],
self._squares[(row/3)*3+col/3])),
range(1,10))
def __str__(self):
# The matrix is transformed into a list of characters
l = [str(self.board[i][j]) if self.board[i][j] else ' '
for i in range(9) for j in range(9)]
l = ['\n '+e if i%9 ==0 else e for (i,e) in enumerate(l)] # 1.
l = [' '+e if i%3 ==0 else e for (i,e) in enumerate(l)] # 2.
l = ['\n'+e if i%27==0 else e for (i,e) in enumerate(l)] # 3.
# 1. New lines every 9 elements
# 2,3. Squares are represented by extra spaces and another
# newline
return ' '.join(l)
def make_generators(sudoku):
[docs] """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."""
generators = []
for i in range(9):
for j in range(9):
def gen_func(col=i,row=j):
if sudoku.board[col][row] != 0:
yield
else:
for candidate in sudoku.candidates(col, row):
with sudoku.attempt(col, row, candidate):
yield
generators.append(gen_func)
return generators
def stack_assumptions(generators, i=0):
[docs] """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:
#. 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,
#. 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."""
if i >= len(generators):
yield
else:
for _ in generators[i]():
for _ in stack_assumptions(generators, i+1):
yield
if __name__=="__main__":
data=('006007403'
'000906020'
'500304006'
'740000010'
'809000304'
'010000057'
'200603005'
'030208000'
'405700200')
sudoku = Sudoku(data)
print "The problem: %s\n" % sudoku
for _ in stack_assumptions(make_generators(sudoku)):
print "A solution: %s\n" % sudoku
# A run of this script shows the following result::
#
# ~$ 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