Using Python and CSPs to Solve Sudoku
This post introduces Constraint Satisfaction Problems (CSPs) and shows how to use a CSP solver to easily solve instances of Sudoku problems. It assumes familiarity with Sudoku and Python.
Constraint Satisfaction Problems (or CSPs) are problems that involve a set of variables that can each take on some number of values. The possible values of each variable may depend on other variables in the set. A well-written overview of CSPs is available here.
A CSP can be represented as:
- A set of variables
- For each variable, a set of possible values that the variable can taken on (also called the domain)
- A set of constraints. Each constraints limits the values some subset of the variables can taken on.
A CSP solver searches over the variables' possible values and produces a mapping from variables to values that satisfy the constraints of the problem.
Certain programming languages, like Prolog, naturally lend themselves to solving CSPs (here's an example of a Prolog program that solves the N-Queens problem). We could use Prolog to solve CSPs, but that would require learning Prolog (which can be difficult for those not familiar with declarative langauges) and would possibly make other integration difficult (for example, a Sudoku solver may be part of a larger web site, not written in Prolog).
Solving Sudoku (and other CSPs) with Python
To solve Sudoku we're going to use the python-constraint library. (Note for Debian/Ubuntu users: This is not the library installed when typing apt-get install python-constraint. You will need to download and install this package manually.)
We will be creating a function called SolveSudoku. It will be called as follows:
m = [ [0,2,0,0,3,0,9,0,7], [0,1,0,0,0,0,0,0,0], [4,0,7,0,0,0,2,0,8], [0,0,5,2,0,0,0,9,0], [0,0,0,1,8,0,7,0,0], [0,4,0,0,0,3,0,0,0], [0,0,0,0,6,0,0,7,1], [0,7,0,0,0,0,0,0,0], [9,0,3,0,2,0,6,0,5], ] print SolveSudoku(m)
...which represents the puzzle:
Step 1
Let's define the function:
def SolveSudoku(m, N = 9):
p = Problem()
...
# TODO: setup variables and constraints
...
solution = p.getSolution()
...
# TODO: format and return solution
Problem() defines a new constraint problem. p.getSolution() searches for a solution. Since we haven't added any variables yet, it returns None.
Step 2
Now we need to define the CSP variables. I've decided to name the variables 0 through 81, where the top-left box is 0 and the bottom right box is 1. The first row consists of the variables [0,1,2,3,4,5,6,7,8], etc. To help with manipulation, we "flatten" the Sudoku board m.
from constraint import *
def SolveSudoku(m, N = 9):
p = Problem()
# flatten list
mList = []
for r in m:
for c in r:
mList.append(c)
...
# TODO: setup variables and constraints
...
solution = p.getSolution()
...
# TODO: format and return solution
Given the above example problem, mList becomes:
[0, 2, 0, 0, 3, 0, 9, 0, 7, 0, 1, 0, 0, 0, 0, 0, 0, 0, 4, 0, 7, 0, 0, 0, 2, 0, 8, 0, 0, 5, 2, 0, 0, 0, 9, 0, 0, 0, 0, 1, 8, 0, 7, 0, 0, 0, 4, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 7, 1, 0, 7, 0, 0, 0, 0, 0, 0, 0, 9, 0, 3, 0, 2, 0, 6, 0, 5]
Step 3
To setup the variables, we loop over each item in mList. If the value is 0 (our placeholder for an unknown value), we call p.addVariable(i, range(1, N+1)), which says "The variable i can be any value from 1 through 10". If the value isn't 0, we add a variable whose only value can be the value specified.
from constraint import *
def SolveSudoku(m, N = 9):
p = Problem()
# flatten list
mList = []
for r in m:
for c in r:
mList.append(c)
# add variables
for i in xrange(N*N):
if mList[i] == 0:
p.addVariable(i, range(1, N+1))
else:
p.addVariable(i, [mList[i]])
# TODO: setup constraints
...
solution = p.getSolution()
...
# TODO: format and return solution
Step 4
To add the row constraints, we can loop over each row and for each row, generate a list of numbers representing the variables in that row and then add the constraint to that list of variables. To add a constraint, we call p.addConstraint(constraint, variableList), where constraint is the constraint placed on the list of variables variableList. Conveniently, python-constraint provides the constraint AllDifferentConstraint for us, which simply says that every value in the list variables we provide must be different.
from constraint import *
def SolveSudoku(m, N = 9):
p = Problem()
# flatten list
mList = []
for r in m:
for c in r:
mList.append(c)
# add variables
for i in xrange(N*N):
if mList[i] == 0:
p.addVariable(i, range(1, N+1))
else:
p.addVariable(i, [mList[i]])
# row constraints
for r in xrange(N):
l = list(xrange(r*N,(r+1)*N))
p.addConstraint(AllDifferentConstraint(),l)
# TODO: setup constraints
...
solution = p.getSolution()
...
# TODO: format and return solution
At each iteration of the loop, l is:
[0, 1, 2, 3, 4, 5, 6, 7, 8] [9, 10, 11, 12, 13, 14, 15, 16, 17] [18, 19, 20, 21, 22, 23, 24, 25, 26] ...
Running this code will produce a solution that has our initial values and unique values for each row. All that's left is adding the column constraints.
Step 5
Similarly, we add column constraints by generating a list of numbers representing each column:
from constraint import *
def SolveSudoku(m, N = 9):
p = Problem()
# flatten list
mList = []
for r in m:
for c in r:
mList.append(c)
# add variables
for i in xrange(N*N):
if mList[i] == 0:
p.addVariable(i, range(1, N+1))
else:
p.addVariable(i, [mList[i]])
# row constraints
for r in xrange(N):
l = list(xrange(r*N,(r+1)*N))
p.addConstraint(AllDifferentConstraint(),l)
# column constraints
for c in xrange(N):
l = list(xrange(c,N*N, N))
p.addConstraint(AllDifferentConstraint(), l)
# TODO: setup constraints
...
solution = p.getSolution()
...
# TODO: format and return solution
Step 6
Adding constraints for the 3x3 grids is slightly more complicated, but still involves generating 9 lists representing the variables in each grid:
from constraint import *
def SolveSudoku(m, N = 9):
p = Problem()
# flatten list
mList = []
for r in m:
for c in r:
mList.append(c)
# add variables
for i in xrange(N*N):
if mList[i] == 0:
p.addVariable(i, range(1, N+1))
else:
p.addVariable(i, [mList[i]])
# row constraints
for r in xrange(N):
l = list(xrange(r*N,(r+1)*N))
p.addConstraint(AllDifferentConstraint(),l)
# column constraints
for c in xrange(N):
l = list(xrange(c,N*N, N))
p.addConstraint(AllDifferentConstraint(), l)
# grid constraints
for i in xrange(9):
grid = []
startingRow = (i%3)*3
startingCol = i/3*3
for r in xrange(3):
for c in xrange(3):
grid.append((startingRow+r)*N+startingCol+c)
p.addConstraint(AllDifferentConstraint(),grid)
solution = p.getSolution()
...
# TODO: format and return solution
Step 7
And finally, we can format the solution nicely by putting each row on its own line:
from constraint import *
def SolveSudoku(m, N = 9):
p = Problem()
# flatten list
mList = []
for r in m:
for c in r:
mList.append(c)
# add variables
for i in xrange(N*N):
if mList[i] == 0:
p.addVariable(i, range(1, N+1))
else:
p.addVariable(i, [mList[i]])
# row constraints
for r in xrange(N):
l = list(xrange(r*N,(r+1)*N))
p.addConstraint(AllDifferentConstraint(),l)
# column constraints
for c in xrange(N):
l = list(xrange(c,N*N, N))
p.addConstraint(AllDifferentConstraint(), l)
# grid constraints
for i in xrange(9):
grid = []
startingRow = (i%3)*3
startingCol = i/3*3
for r in xrange(3):
for c in xrange(3):
grid.append((startingRow+r)*N+startingCol+c)
p.addConstraint(AllDifferentConstraint(),grid)
solution = p.getSolution()
if solution is not None:
m = []
i = 0
for r in xrange(N):
row = []
for c in xrange(N):
row.append(str(solution[i]))
i+=1
rowStr = ' '.join(row)
m.append(rowStr)
return '\n'.join(m)
else:
return None
And we have a Sudoku solver! The example program outputs:
6 2 8 5 3 4 9 1 7 5 1 9 8 7 2 4 3 6 4 3 7 9 1 6 2 5 8 8 6 5 2 4 7 1 9 3 3 9 2 1 8 5 7 6 4 7 4 1 6 9 3 5 8 2 2 5 4 3 6 9 8 7 1 1 7 6 4 5 8 3 2 9 9 8 3 7 2 1 6 4 5
Making it Succinct
We can make this program shorter by abusing both Python's syntax and readability:
from constraint import *
def SolveSudoku(m, N = 9):
p = Problem()
l = sum(m,[]) # flatten list
[p.addVariable(i, [l[i]] if l[i] > 0 else range(1,N+1)) for i in xrange(N*N)] # load variables
[p.addConstraint(AllDifferentConstraint(),list(xrange(r*N,(r+1)*N))) for r in xrange(N)] # row constraints
[p.addConstraint(AllDifferentConstraint(),list(xrange(c,N*N, N))) for c in xrange(N)] # column constraints
[p.addConstraint(AllDifferentConstraint(),filter(lambda x: (i%3)*3 <= x/N < (i%3+1)*3 and (i/3)*3 <= x%N < (i/3+1)*3, xrange(N*N))) for i in xrange(N)] # grid constraints
s = p.getSolution()
return '\n'.join([' '.join([str(s[j]) for j in list(xrange(i*N,i*N+N))]) for i in xrange(N)]) if s is not None else None
Conclusion
While we could have solved Sudoku directly, transforming Sudoku into a CSP allowed us to use an existing CSP solver to do the difficult work for us. If you come across problems in your work that appear to be CSPs, give a CSP solver a chance before reinventing the wheel.
Coming Soon: Sudoku's constraints can all be described using the built in AllDifferentConstraint(). A future post will describe how to define your own constraint classes in order to solve the logic puzzle KenKen.