Capstone: solve a Sudoku: Prolog tutorial

A Sudoku is a perfect constraint problem: 81 cells, each 1–9, and every row, column and 3×3 block must contain all-different digits. With CLP(FD) you say exactly that, no algorithm for solving it is written down at all.

We represent the board as a list of 9 rows, each a list of 9 cells. Unknown cells are unbound variables.

:- use_module(library(clpfd)).

sudoku(Rows) :-
    length(Rows, 9),
    maplist(same_length(Rows), Rows),          % 9 rows of 9 cells
    append(Rows, Vs), Vs ins 1..9,             % every cell is a digit
    maplist(all_distinct, Rows),               % rows
    transpose(Rows, Columns),
    maplist(all_distinct, Columns),            % columns
    Rows = [As, Bs, Cs, Ds, Es, Fs, Gs, Hs, Is],
    blocks(As, Bs, Cs),                        % 3x3 blocks
    blocks(Ds, Es, Fs),
    blocks(Gs, Hs, Is).

blocks([], [], []).
blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
    all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
    blocks(Ns1, Ns2, Ns3).

That is the whole solver. Now a puzzle (underscores are the blanks):

problem(1, [[_,_,_, _,_,_, _,_,_],
            [_,_,_, _,_,3, _,8,5],
            [_,_,1, _,2,_, _,_,_],

            [_,_,_, 5,_,7, _,_,_],
            [_,_,4, _,_,_, 1,_,_],
            [_,9,_, _,_,_, _,_,_],

            [5,_,_, _,_,_, _,7,3],
            [_,_,2, _,1,_, _,_,_],
            [_,_,_, _,4,_, _,_,9]]).

print_board([]).
print_board([Row|Rows]) :-
    format("~w ~w ~w | ~w ~w ~w | ~w ~w ~w~n", Row),
    print_board(Rows).

?- problem(1, Rows), sudoku(Rows), print_board(Rows)

No labeling call at all, and the board comes back solved: for this puzzle, propagation alone fills in every cell, because all_distinct/1 propagates strongly enough that there is nothing left to guess. (The same program is in the Constraints in practice lesson, which also shows a harder grid.)

Not every puzzle is so kind. Here is a second one, for which propagation does not finish: sudoku(Rows) alone leaves residual constraints, and you must add labelling (ff: first the most constrained cell):

problem(2, [[1,_,_, _,_,7, _,9,_],
            [_,3,_, _,2,_, _,_,8],
            [_,_,9, 6,_,_, 5,_,_],

            [_,_,5, 3,_,_, 9,_,_],
            [_,1,_, _,8,_, _,_,2],
            [6,_,_, _,_,4, _,_,_],

            [3,_,_, _,_,_, _,1,_],
            [_,4,_, _,_,_, _,_,7],
            [_,_,7, _,_,_, 3,_,_]]).

?- \+ (problem(2, Rows), sudoku(Rows), ground(Rows))

?- problem(2, Rows), sudoku(Rows), maplist(labeling([ff]), Rows), print_board(Rows)

Constraint propagation does the bulk of the work, and a little search finishes the job.

What you've learned

You can now read and write the core of Prolog:

facts, rules, queries and how unification and backtracking evaluate them;
recursion over lists and trees, with accumulators;
control: cut, if-then-else, negation, exceptions;
all-solutions predicates and the dynamic database;
higher-order programming with maplist, foldl and lambdas;
DCGs for parsing, difference lists, meta-interpreters;
constraint solving for puzzles and planning.

Where next? Install SWI-Prolog and read its manual. Try a project: a type checker, a scheduler, a rule-based assistant. The 99 Prolog problems are a great exercise set, and Markus Triska's Power of Prolog goes far deeper.

The Playground in the sidebar is yours to experiment in.

Exercise: A 4×4 mini Sudoku

Write mini(Rows): a solver for 4×4 boards where each row, column and each of the four 2×2 blocks contains 1–4 exactly once. Use CLP(FD) as above. Remember transpose/2 from library(clpfd).