Solving Sudoku with CLP(FD) in SWI-Prolog: A Practical Constraint Modeling Guide

You want a Sudoku solver that you describe rather than program: state the rules — digits 1–9, no repeats per row, column, or 3×3 block — and let the constraint engine find the grid. SWI-Prolog's CLP(FD) library (Constraint Logic Programming over Finite Domains) does exactly this. The whole solver fits in about 30 lines, and the same modeling pattern transfers to scheduling, allocation, and other constraint satisfaction problems.

What CLP(FD) gives you

Plain Prolog searches by unification and backtracking, which means you write the search yourself. CLP(FD) instead lets you declare domains (the set of values a variable may take) and constraints (relations that must hold). The solver propagates constraints to shrink domains before and during search, so it prunes huge parts of the search space that a naïve generate-and-test approach would explore. The trade-off: you must separate the modeling phase (posting constraints) from the search phase (labeling/2), and the choice of search strategy matters a lot for performance.

Prerequisites

• SWI-Prolog 8.0 or newer. CLP(FD) ships with the standard installation; check your version with swipl --version. Older releases lack some global constraints mentioned below.
• Basic Prolog familiarity: facts, rules, unification, and the use_module/1 directive.
• A text editor and a shell. No extra packs are needed.

Modeling the puzzle

Create a file sudoku.pl. The model has four parts: load the library, build the 9×9 grid of variables, post the constraints, then label.

:- use_module(library(clpfd)).

sudoku(Rows) :-
    % 1. Rows is a list of 9 lists, each with 9 variables.
    length(Rows, 9),
    maplist(same_length(Rows), Rows),
    append(Rows, Cells),
    % 2. Every cell is in the domain 1..9.
    Cells ins 1..9,
    % 3. Row and column constraints.
    maplist(all_distinct, Rows),
    transpose(Rows, Cols),
    maplist(all_distinct, Cols),
    % 4. Block constraints.
    Rows = [A,B,C,D,E,F,G,H,I],
    blocks(A,B,C), blocks(D,E,F), blocks(G,H,I),
    % 5. Search.
    labeling([ff], Cells).

blocks([], [], []).
blocks([A,B,C|R1], [D,E,F|R2], [G,H,I|R3]) :-
    all_distinct([A,B,C,D,E,F,G,H,I]),
    blocks(R1, R2, R3).

Key pieces:

• Cells ins 1..9 restricts every cell variable to the finite domain 1–9. This is a CLP(FD) operator, not plain unification.
• all_distinct/1 is a global constraint: every element of the list must take a different value. It propagates much more effectively than posting pairwise disequalities.
• blocks/3 peels three cells at a time from three consecutive rows to form each 3×3 sub-square.
• labeling([ff], Cells) triggers the search. The ff (first-fail) heuristic picks the variable with the smallest remaining domain first, which usually finds failures early and is dramatically faster than left-to-right labeling on harder puzzles.

Adding clues and running it

Represent a puzzle as a list of lists with variables for blanks and integers for givens. Unifying a cell with an integer simply narrows its domain to that single value, so no special handling is needed:

puzzle(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]]).

Run it from the shell (no special permissions needed):

$ swipl -s sudoku.pl
?- puzzle(1, Rows), sudoku(Rows), maplist(writeln, Rows).

Expected result: the query succeeds and prints nine rows of digits. The well-known puzzle above has the unique solution starting [5,3,4,6,7,8,9,1,2], so the first printed row should match that. If the query fails instead, either the clues are contradictory or a constraint was posted incorrectly.

Checking the result

Because labeling/2 only succeeds when all constraints hold, a returned ground grid is valid by construction. Still, two cheap sanity checks are worthwhile:

• Re-verify distinctness on the ground grid: ?- puzzle(1, R), sudoku(R), transpose(R, C), maplist(all_distinct, R), maplist(all_distinct, C). This must succeed (it re-runs the constraints on now-ground values).
• Confirm the givens were respected by comparing against the original puzzle before solving: since clues are unified into the same variables, any mismatch would have caused failure rather than a wrong answer.

When labeling is slow or fails

• Try a different strategy. labeling([ff, down], Cells) or [min, up] changes variable/value ordering. Performance differences between strategies can be enormous; naïve left-to-right labeling can blow up exponentially on hard instances.
• Interrupt safely. Press Ctrl+C at the SWI-Prolog prompt and choose a (abort) to return to the top level; nothing is written to disk, so there is no state to roll back.
• Unsatisfiable input. If sudoku/1 fails immediately, re-check the clues: two equal digits in one row, column, or block make the problem unsatisfiable, and CLP(FD) typically detects this during constraint posting, before search even starts.

Limitations

This approach is ideal for puzzles with a unique or few solutions. Enumerating all solutions of a nearly empty grid is infeasible (there are roughly 6.7×10²¹ completed grids), so don't call findall/3 over sudoku/1 without givens. Also note that constraint propagation behavior and available global constraints vary slightly across SWI-Prolog versions; the code above assumes 8.x semantics. Verify on your installation before relying on additional global constraints such as global_cardinality/2.