JFP 16 (6): 671–679, 2006. c© 2006 Cambridge University Press
doi:10.1017/S0956796806006058 First published online 7 July 2006 Printed in the United Kingdom
Copyright By PowCoder代写 加微信 powcoder
FUNCTIONAL PEARL
A program to solve Sudoku
RICHARD BIRD
Programming Research Group, Oxford University
, Parks Road, Oxford OX1 3QD, UK
There’s no maths involved. You solve
the puzzle with reasoning and logic.
Advice on how to play Sudoku,
The Independent Newspaper
1 Introduction
The game of Sudoku is played on a 9 by 9 board. Given is a matrix of characters,
2 . . . . 1 . 3 8
. . . . . . . . 5
. 7 . . . 6 . . .
. . . . . . . 1 3
. 9 8 1 . . 2 5 7
3 1 . . . . 8 . .
9 . . 8 . . . 2 .
. 5 . . 6 9 7 8 4
4 . . 2 5 . . . .
The idea is to fill in the dots with the digits 1 to 9 so that each row, each column
and each of the component 3 by 3 boxes contains the digits 1 to 9 exactly once.
In general there may be one, none or many solutions, though in a good Sudoku
puzzle there is always a unique solution. Our aim in this pearl is to derive a Haskell
program to solve Sudoku puzzles. Specifically, we will define a function
sudoku :: Board → [Board ]
for computing all the ways a given board may be filled. If we want only one solution
we can take the head of the list. Lazy evaluation means that only the first result will
then be computed.
We do not want our program to depend on the board size, as long as it is of the
form (N 2 × N 2) for positive N , nor on the precise characters chosen for the entries.
Instead, the program is parameterized by three constants, boardsize, boxsize and
cellvals , and one test blank :: Char → Bool for determining whether a given entry
672 R. Bird
is blank. For concreteness, we can take
boardsize = 9
boxsize = 3
cellvals = “123456789”
blank = (= ‘.’)
Changing cell values, e.g. to “TONYBLAIR” is easy.
2 Specification
The first aim is to write down the simplest and clearest specification of Sudoku
without regard to how efficient the result might be. Such a specification will help us
focus ideas on how a more efficient solution might be obtained, as well as being a
starting point for program manipulation.
One possibility is first to construct a list of all correctly completed boards, and
then to test the given board against these boards to identify those whose entries
match the given ones. Another possibility, and the one we will take, is to start with
the given board and to generate all possible completions. Each completed board is
then tested to see if it is correct, that is, does not contain duplicate entries in each
row, column or box.
A board is a matrix of characters:
type Matrix a = [[a]]
type Board = Matrix Char
Strictly speaking a given board should first be checked to see that every non-blank
entry is an element of cellvals . Invalid boards should be rejected. However, for
simplicity we will assume that the given board does satisfy the basic requirements.
The function correct tests whether a filled board, that is, one containing no blank
characters, has different entries in each row, column and box:
correct :: Board → Bool
correct b = all nodups (rows b) ∧
all nodups (cols b) ∧
all nodups (boxs b)
The function nodups can be defined by
nodups :: Eq a ⇒ [a] → Bool
nodups [ ] = True
nodups (x : xs) = notElem x xs ∧ nodups xs
2.1 Rows, columns and boxes
If a matrix is given by a list of its rows, the function rows is just the identity function
on matrices:
rows :: Matrix a → Matrix a
We have, trivially, that rows · rows = id .
Functional pearl 673
The function cols computes the transpose of a matrix. One possible definition is:
cols :: Matrix a → Matrix a
cols [xs] = [[x ] | x ← xs]
cols (xs : xss) = zipWith (:) xs (cols xss)
We also have cols · cols = id .
The boxes of a matrix can be computed by:
boxs :: Matrix a → Matrix a
boxs = map ungroup · ungroup · map cols · group · map group
The function group groups a list into component lists of length boxsize, and ungroup
takes a grouped list and ungroups it:
group :: [a] → [[a]]
group = groupBy boxsize
ungroup :: [[a]] → [a]
ungroup = concat
We omit the definition of groupBy . Using ungroup ·group = id and group ·ungroup =
id , it is easy to show that boxs · boxs = id by simple equational reasoning.
2.2 Generating choices and matrix cartesian product
The function choices replaces blank entries in a board with all possible choices for
that entry. Using Choices as a synonym for [Char], we have
choices :: Board → Matrix Choices
choices = map (map choose)
choose e = if blank e then cellvals else [e]
Of course, not every possible choice is valid for each cell, and we will return to this
point later on.
The function mcp (matrix cartesian product) generates a list of all possible boards
from a given matrix of choices:
mcp :: Matrix [a] → [Matrix a]
mcp = cp · map cp
The function cp computes the cartesian product of a list of lists:
cp :: [[a]] → [[a]]
cp [ ] = [[ ]]
cp (xs : xss) = [x : ys | x ← xs , ys ← cp xss]
Note that cp xss returns an empty list if xss contains an empty list. Thus mcp cm
returns an empty list if any entry of cm is the empty list.
674 R. Bird
2.3 Specification
The function sudoku can now be defined by
sudoku :: Board → [Board ]
sudoku = filter correct · mcp · choices
However, this specification is executable in principle only. Assuming about a half of
the 81 entries are fixed initially, there are about 940, or
147808829414345923316083210206383297601
boards to check! We therefore need a better approach.
3 Pruning the choices
Obviously, not every possible choice is valid for each cell. A better choice for a blank
entry in row r , column c and box b is any cell value that does not appear among
the fixed entries in row r , column c or box b. An entry in a matrix of choices is fixed
if it is a singleton list. The fixed entries in a given row, column or box, are given by
fixed :: [Choices] → Choices
fixed = concat · filter single
where single :: [a] → Bool tests whether the argument is a singleton list. The fixed
entries can be removed from a list of choices by
reduce :: [Choices] → [Choices]
reduce css = map (remove (fixed css)) css
remove fs cs = if single cs then cs else delete fs cs
We leave the definition of delete to the reader.
Now, how shall we prune the matrix of choices? The aim is to define a function
prune :: Matrix Choices → Matrix Choices
satisfying the equation
filter correct · mcp = filter correct · mcp · prune
The function prune removes the fixed choices from each row, column or box. The
question is a good test of one’s programming ability for it seems easy to get into a
mess. So, it is worthwhile adding a small pause at this point, to see if the reader can
come up with a short definition that meets the requirement.
The calculational programmer would calculate a definition, and that is precisely
what we are going to do.
The first step is to rewrite filter correct in the form
filter correct = filter (all nodups · boxs) ·
filter (all nodups · cols) ·
filter (all nodups · rows)
The order of the component filters is unimportant.
Functional pearl 675
Now we send these filters one by one into battle with mcp. We will need some
weapons, the first of which is the law
filter (p · f ) = map f · filter p · map f
which is valid provided f · f = id . In particular, the law is valid if f is one of rows ,
cols , or boxs .
Another useful law is the following one:
filter (all p) · cp = cp · map (filter p)
In words, if we want only those lists all of whose elements satisfy p from a cartesian
product, then we can obtain them by taking the cartesian product of the elements
satisfying p of the component lists.
We will also need the following facts:
map rows · mcp = mcp · rows
map cols · mcp = mcp · cols
map boxs · mcp = mcp · boxs
These laws are intuitively clear and we will not verify them formally.
We need one final law: the crucial property of the function reduce defined above
filter nodups · cp = filter nodups · cp · reduce
Here is the calculation. Let f be one of rows , cols or boxs:
filter (all nodups · f ) · mcp
= {since filter (p · f ) = map f · filter p · map f if f · f = id}
map f · filter (all nodups) · map f · mcp
= {since map f · mcp = mcp · f if f ∈ {boxs , cols , rows}}
map f · filter (all nodups) · mcp · f
= {definition of mcp}
map f · filter (all nodups) · cp · map cp · f
= {since filter (all p) · cp = cp · map (filter p)}
map f · cp · map (filter nodups · cp) · f
= {property of reduce}
map f · cp · map (filter nodups · cp · reduce) · f
= {since filter (all p) · cp = cp · map (filter p) }
map f · filter (all nodups) · cp · map (cp · reduce) · f
= {since map f · filter p = filter (p · f ) · map f if f · f = id}
filter (all nodups · f ) · map f · mcp · map reduce · f
= {since map f · mcp = mcp · f if f ∈ {boxs , cols , rows}}
filter (all nodups · f ) · mcp · f · map reduce · f
= {definition of pruneBy f ; see below}
filter (all nodups · f ) · mcp · pruneBy f
676 R. Bird
The definition of pruneBy is
pruneBy :: (MatrixChoices → MatrixChoices) →
(MatrixChoices → MatrixChoices)
pruneBy f = f · map reduce · f
We have shown that, provided f is one of rows , cols or boxs ,
filter (all nodups · f ) · mcp = filter (all nodups · f ) · mcp · pruneBy f
For the final step we need one more law, the fact that we can interchange the order
of two filter operations:
filter p · filter q = filter q · filter p
This law is not generally valid in Haskell without qualification on the boolean
functions p and q , but provided p and q are total functions, as is the case here, the
law is OK. Indeed we implicitly made use of it when claiming that the order of the
component filters in the expansion of filter correct was unimportant.
Now we can calculate, abbreviating nodups to nd to keep the expressions short:
filter correct · mcp
= {rewriting filter correct as three filters}
filter (all nd · boxs) · filter (all nd · cols) · filter (all nd · rows) · mcp
= {calculation above}
filter (all nd · boxs) · filter (all nd · cols) · filter (all nd · rows) · mcp ·
pruneBy rows
= {interchanging the order of the filters}
filter (all nd · rows) · filter (all nd · boxs) · filter (all nd · cols) · mcp ·
pruneBy rows
= {using the calculation above again}
filter (all nd · rows) · filter (all nd · boxs) · filter (all nd · cols) · mcp ·
pruneBy cols · pruneBy rows
= {repeating the last two steps one more time}
filter (all nd · rows) · filter (all nd · boxs) · filter (all nd · cols) · mcp ·
pruneBy boxs · pruneBy cols · pruneBy rows
= {definition of filter correct}
filter correct · mcp · pruneBy boxs · pruneBy cols · pruneBy rows
Hence, we can define prune by
prune :: MatrixChoices → MatrixChoices
prune = pruneBy boxs · pruneBy cols · pruneBy rows
Readers who gave this solution (or a similar one in which the three components
appear in any other order) can award themselves full marks.
Functional pearl 677
The revised definition of sudoku now reads
sudoku :: Board → [Board ]
sudoku = filter correct · mcp · prune · choices
However, this version remains non-executable in practice. Again, assuming about
a half of the 81 entries are fixed and an average of 3 choices/cell is generated by
refining choices, there are still 340, or 12157665459056928801 boards to check. We
still need something better.
4 One choice at a time
Humans employ a number of devices for filling in entries when solving Sudoku
problems. For example, after pruning a matrix of choices, one or more entries that
were previously blank may become fixed. In such a case, we can always prune again
to see if more entries are filled in. The calculation above shows that we can have
the composition of as many prune functions as we like. This is the way the simplest
puzzles are solved.
There are also other strategies. For example, again after pruning the choice matrix
it may turn out that a single row (or column or box) contains, for example, three
entries such as 12, 12 and 123. It is clear that the third entry has to receive 3; if it
receives 1 or 2, the first two entries cannot be filled in.
Repeatedly pruning the choice matrix is sensible, but we can combine it with
another basic strategy. Rather than applying mcp when pruning fails to produce
anything new, we can focus on one cell that has at least two choices, and generate
a list of matrices in which this cell alone is expanded to each of its possible fixed
Suppose we define a function
expand :: Matrix Choices → [Matrix Choices]
that installs the fixed choices for one cell. This function satisfies the property that
mcp ≈ concat · map mcp · expand
where ≈ means equality up to a permutation of the answer. After applying prune,
we can apply expand and then apply prune again to each of the results. Provided we
discard any matrix that becomes blocked (see below), this process can be continued
until we are left with a list of matrices, all of whose choices are fixed choices.
4.1 Blocked matrices
A matrix of choices can be blocked in that:
• One or more cells may contain zero choices. In such a case mcp will return an
empty list;
• The same fixed choice may occur in two or more positions in the same row,
column or box. In such a case mcp will still compute all the completed boards,
but the correctness test will throw all of them away.
678 R. Bird
Blocked matrices can never lead to a solution. In following the strategy of repeatedly
pruning and expanding the matrix of choices, we can identify and discard any
blocked matrix. Provided we do this, any remaining matrix that consists solely of
fixed choices will be a solution to the puzzle.
Formally, we define blocked by
blocked :: Matrix Choices → Bool
blocked cm = void cm ∨ not (safe cm)
void :: Matrix Choices → Bool
void = any (any null )
safe :: Matrix Choices → Bool
safe cm = all (nodups · fixed ) (rows cm) ∧
all (nodups · fixed ) (cols cm) ∧
all (nodups · fixed ) (boxs cm)
4.2 Smallest number of choices
A good choice of cell on which to perform expansion is one with the smallest
number of choices (greater than one of course). We will need a function that breaks
up a matrix on the first entry with the smallest number of choices. A matrix that is
not blocked is broken into five pieces:
cm = rows1 ++ [row1 ++ cs : row2] ++ rows2
The smallest-choice entry is cs . The definition of expand is
expand cm = [rows1 ++ [row1 ++ [c] : row2] ++ rows3 | c ← cs]
where (rows1, row : rows2) = break (any best) cm
(row1, cs : row2) = break best row
best cs = (length cs = n)
n = minchoice cm
The definition of minchoice is
minchoice = minimum · filter (> 1) · concat · map (map length)
The number of choices in each cell is computed twice in the above definition, and
it may be more efficient to avoid this duplication of effort. Also, we could probably
make minchoice more efficient since once we have found an entry with two choices
there is no point in looking further. Observe that expand returns ⊥ if there is no
entry with at least two choices, for then n is undefined.
With this definition of expand we have
mcp ≈ concat · map mcp · expand
filter correct · mcp
≈ {above law of expand}
filter correct · concat · map mcp · expand
= {since filter p · concat = concat · map (filter p)}
Functional pearl 679
concat · map (filter correct · mcp) · expand
= {property of prune}
concat · map (filter correct · mcp · prune) · expand
Writing search = filter correct · mcp we therefore have
search = concat · map (search · prune) · expand
This equation can be used as the basis of a definition of search provided we trap
the terminal cases:
search :: Matrix Choices → [Matrix Choices]
| blocked cm = [ ]
| all (all single) cm = [cm]
| otherwise = (concat · map(search · prune) · expand ) cm
4.3 Final version
Now we can write down our final definition of sudoku:
sudoku :: Board → [Board ]
sudoku = map (map head ) · search · prune · choices
The function map (map head ) converts a matrix of singleton choices into a board.
The program is quite fast, rarely taking more than a second or two to solve a puzzle.
5 Conclusions
The Sudoku problem provides an ideal classroom example with which to illustrate
manipulations of arrays as well as manipulation of programs. Indeed, the pearl
is more or less a straightforward transcription of two lectures I gave to first-year
undergraduates, omitting most of the calculations. There is a temptation to identify
array elements by their cartesian coordinates, and to think of the rows, columns
and boxes of an array in terms of operations on these coordinates. Instead, and this
is the pedagogic value of the exercise, we have gone for wholemeal programming,
identifying these structures as complete entities in themselves. There are other
Sudoku solvers out there, but the present one certainly seems one of the clearest
and simplest.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com