Solving Sudoku with Prolog
Prolog is extremely well suited for
tasks like Sudoku.
For example, using CLP(ℤ) constraints, a
valid Sudoku board can be concisely expressed like this:
Like all pure Prolog programs,
this predicate can be used in all directions. You can
use it to:
append(Rows, Vs), Vs ins 1..9,
Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
blocks(As, Bs, Cs),
blocks(Ds, Es, Fs),
blocks(Gs, Hs, Is).
blocks(, , ).
blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
blocks(Ns1, Ns2, Ns3).
For example, we can use the code to generate valid
- complete partial squares
- test complete squares
- generate all Sudoku Latin squares.
?- sudoku(Rows), maplist(label, Rows), maplist(portray_clause, Rows).
Rows = [[1,2,3,4,5,6,7,8,9]|...]
A partial instantiation of the rows turns this into
a completion task, which is what we commonly
understand as a Sudoku puzzle.
Prolog source file: sudoku.pl
The source file contains:
You can try it with Scryer Prolog:
- the Prolog formulation of Sudoku puzzles which is shown above
- PostScript instructions for
showing animations of
the search process
- sample Sudoku instances, available is problem/2.
$ scryer-prolog sudoku.pl
Sample query and answer:
?- problem(1, Rows),
Rows = [[1,5,6,8,9,4,3,2,7]|...]
If you have the PostScript viewer "gs" installed, you can view an
animation of the constraint solving process.
Sample PostScript file, a self-contained saved animation
for a Sudoku puzzle (open it with "gv" or "gs" to view
Here is a shell command that you can try,
using show/2 to animate the search:
$ scryer-prolog -g 'problem(1,Rows),show([ff],Rows)' sudoku.pl | \
gs -dNOPROMPT -g680x680 -dGraphicsAlphaBits=2 -r150 -q
The arguments of show/2 are:
As a side-effect, you see an animation of the constraint solving
process. To make the search more interesting, you can
replace all_distinct/1 with the weaker
constraint all_different/1 in the source file.
- a list of labeling options
- a list of 9 rows that are to be
completed to a Sudoku Latin square. Each row is a list of 9
variables, which can also be already instantiated to integers to
fill in initial elements.
Here's an intermediate state:
And here is a picture of a finished animation:
Solutions with Viewers.
More CLP(ℤ) examples: https://github.com/triska/clpz
More about Prolog: The Power of Prolog