Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 40 ยท Projects and Practice

Project: A Sudoku Solver with CLP(FD)

Build a complete Sudoku solver in Prolog with library(clpfd). Model rows, columns and boxes with all_distinct, add a printer and a uniqueness check, then run the same model on a Python stand-in.

Sudoku is the ideal first constraint project: the rules fit in a sentence, a human solves it by elimination, and a CLP(FD) program does exactly the same thing, only faster. In this project you will build a solver, a pretty printer, and a checker that tells you whether a puzzle has exactly one solution. The whole solver is about twenty lines.

Prolog is not available on this site, so the Prolog program is read-only; it is standard library(clpfd) code. The same model also runs below on the Python stand-in solver from the CLP(FD) lessons so you can try it on real puzzles.

The rules as constraints

A Sudoku board has 81 cells, each holding 1 to 9. In every row, every column and every 3 by 3 box, all nine values must be different. That is the entire problem:

  1. 81 variables with the domain 1..9.
  2. 27 all_distinct constraints (9 rows, 9 columns, 9 boxes).
  3. The given digits fix some variables.

Represent the board as a list of rows, each row a list of nine variables. An empty cell is just an unbound Prolog variable, which makes the puzzle itself a valid Prolog term:

PROLOG
problem(1, [[5,3,_,_,7,_,_,_,_],
            [6,_,_,1,9,5,_,_,_],
            [_,9,8,_,_,_,_,6,_],
            [8,_,_,_,6,_,_,_,3],
            [4,_,_,8,_,3,_,_,1],
            [7,_,_,_,2,_,_,_,6],
            [_,6,_,_,_,_,2,8,_],
            [_,_,_,4,1,9,_,_,5],
            [_,_,_,_,8,_,_,7,9]]).

The model

PROLOG
:- use_module(library(clpfd)).

sudoku(Rows) :-
    length(Rows, 9),
    maplist(same_length(Rows), Rows),        % a 9 x 9 grid
    append(Rows, Vs),
    Vs ins 1..9,
    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),                      % boxes: three rows at a time
    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).

Read it top to bottom:

  • maplist(same_length(Rows), Rows) makes every row as long as there are rows, so together with length(Rows, 9) it builds a 9 by 9 grid of fresh variables (when given a puzzle, it just checks the shape).
  • append(Rows, Vs) flattens the grid into one list so ins can set every domain in a single call.
  • transpose/2 turns rows into columns, so the same all_distinct constraint serves both.
  • blocks/3 takes three rows at once and peels off three cells from each, forming a box, then recurses on the rest of the rows. Three calls cover all nine boxes.

Solving and printing

PROLOG
?- problem(1, Rows), sudoku(Rows), maplist(labeling([ff]), Rows),
   maplist(portray_clause, Rows).
[5, 3, 4, 6, 7, 8, 9, 1, 2].
[6, 7, 2, 1, 9, 5, 3, 4, 8].
[1, 9, 8, 3, 4, 2, 5, 6, 7].
[8, 5, 9, 7, 6, 1, 4, 2, 3].
[4, 2, 6, 8, 5, 3, 7, 9, 1].
[7, 1, 3, 9, 2, 4, 8, 5, 6].
[9, 6, 1, 5, 3, 7, 2, 8, 4].
[2, 8, 7, 4, 1, 9, 6, 3, 5].
[3, 4, 5, 2, 8, 6, 1, 7, 9].

For an easy puzzle like this one, propagation by all_distinct can determine most or all of the cells before labeling starts; harder puzzles need real search. labeling([ff]) fills the cell with the fewest candidates first, which is the same instinct a human has. Calling sudoku(Rows) before labeling, as in the query, is the rule of CLP(FD): post constraints first, search last.

The stand-in runs the same model: 81 variables, 27 all_different groups, then a labeling search with ff. Its propagation is weaker than all_distinct, but this puzzle yields all the same.

Python Sudoku solver (Python stand-in solver)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Is the puzzle valid? Counting solutions

A good Sudoku has exactly one solution. You can check that with the same model by asking for more than one. In SWI-Prolog use limit/2 from library(solution_sequences) to stop after two:

PROLOG
unique(Rows) :-
    findall(Rows, limit(2, (sudoku(Rows), maplist(labeling([ff]), Rows))), Solutions),
    length(Solutions, 1).

If Solutions has length 0 the puzzle is impossible, 1 means it is a proper puzzle, and 2 means it is ambiguous. The stand-in does the same by taking at most a few solutions from its labeling generator:

Python How many solutions? (Python stand-in solver)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Extensions to try

  1. Read puzzles from text. Parse a string of 81 characters where . or 0 is empty, using string_chars/2 and char_code/2, and build the grid with maplist. The atoms and strings lesson has the tools.
  2. Prettier output. Print a box separator after every third row and column with format/2 and nth0/3.
  3. Generate puzzles. Solve an empty grid with randomized labeling (shuffle the candidate order with random_permutation/2), then remove clues one at a time as long as unique/1 still holds.
  4. Other variants. Diagonal Sudoku (two more all_distinct constraints), Killer Sudoku (sum/3 over cages), 4 by 4 mini-Sudoku, or a Latin square (rows and columns only).
  5. Compare propagation. Replace all_distinct with all_different and time a hard puzzle with time/1. You will see why the stronger constraint is worth its cost.

Common mistakes

  • Calling labeling before posting the constraints. The search then has no pruning at all.
  • Forgetting transpose/2 (it lives in library(clpfd)) and constraining only the rows.
  • Using all_different and expecting hard puzzles to be solved without search; use all_distinct.
  • Writing the puzzle with 0 for blanks. A 0 is outside the domain 1..9, so the solver says there is no solution; use unbound variables.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many all_distinct constraints does the standard Sudoku model post?

    Nine rows, nine columns and nine boxes.
  2. 2. Why is transpose(Rows, Columns) used?

    The columns of the grid are the rows of its transpose, so maplist(all_distinct, Columns) constrains every column.
  3. 3. What does it mean if findall(S, limit(2, solve(S)), L) gives a list of length 2?

    limit(2, ...) stops after two solutions; getting two means the puzzle is ambiguous.
  4. 4. In the Prolog model, how is an empty cell represented?

    An unbound variable is later constrained to 1..9 by Vs ins 1..9.

Summary

  • Sudoku is 81 variables in 1..9 plus 27 all_distinct constraints; the model is about twenty lines of Prolog.
  • Represent the board as rows of variables, use transpose/2 for columns and blocks/3 for boxes.
  • Post constraints first, then labeling([ff]); strong propagation often solves easy puzzles with no search.
  • Counting up to two solutions checks that a puzzle is valid.

Next: Project: A Text Adventure Game