Recently, at university, we had a class that introduced the idea of logic programming and explored a bit the Prolog language. I decided to play a bit more with it and write a Sudoku solver. Let’s see how it turned out.

What is Sudoku?

Sudoku is a logic puzzle with a purpose of filling a 9x9 diagram in a way, where each row, column and a 3x3 suqare (non-overlapping, called “a block”) has exactly one digit from 1 to 9. You’ll probably find a much better description at wikipedia.

The solution

To create the solver I decided to use Prolog - a language that literally means “logic programming” should work perfectly for solving a logic puzzle. Indeed, that’s the case and the whole program takes exactly 16 lines of a very readable code, that mostly encodes the sudoku rules outlines in the introduction above.

The program uses the clpfd library, that even though is not core of prolog, is an extremely powerful tool, that is used very often in prolog programs. The name clpfd can be expanded to “Constraint Logic Programming over Finite Domains”. Let’s explore what that means. A constraint is a simple logical relation between multiple variables (unknowns), where each can take a value out of a single domain (a set). For instance: “a circle is inside a square” gives us a constraint without giving a precise position for either square or the circle. We can add a third object, let’s say a triangle, and create another constraint - “the square is on the right side of a triangle”. A finite domain, for all intents and purposes, here means a finite set.

In SWI-Prolog the constraint programming is realised using a sequence of libraries: clp/clp_distinct, clp/simplex, clp/clpfd, clpqr.

The program

%% sudoku.pl
:- use_module(library(clpfd)).

sudoku(Puzzle) :-
    flatten(Puzzle, Tmp), Tmp ins 1..9,
    Rows = Puzzle,
    transpose(Rows, Columns),
    blocks(Rows, Blocks),
    maplist(all_distinct, Rows),
    maplist(all_distinct, Columns),
    maplist(all_distinct, Blocks),
    maplist(label, Rows).

blocks([A,B,C,D,E,F,G,H,I], Blocks) :-
    blocks(A,B,C,Block1), blocks(D,E,F,Block2), blocks(G,H,I,Block3),
    append([Block1, Block2, Block3], Blocks).

blocks([], [], [], []).
blocks([A,B,C|Bs1],[D,E,F|Bs2],[G,H,I|Bs3], [Block|Blocks]) :-
    Block = [A,B,C,D,E,F,G,H,I],
    blocks(Bs1, Bs2, Bs3, Blocks).

Let’s see what’s happening here. The game board is represented as a matrix simulated with a list of lists representing rows. The field values are represented by integers.

In the sudoku/1 predicate we introduce a constraint, that all values are to be integers from the 1 to 9 range. Next, we compute the rows, columns (by transposing rows) and blocks (using the blocks/2 predicate) of the puzzle in order to introduce a constraint that all values in a single row, column and block should be distinct. In order to do that we use the maplist/2 predicate that ensures the predicate given as first argument is satisfied for all the elements of the list given as the second argument. The all_distinct/1 predicate comes from the clpfd library and makes sure all the elements of a list are distinct. The last instruction, that’s not obvious to me, from what I understand, will make sure each free (unbound) variable field of our puzzle is assigned exactly one value.

The blocks/2 predicate is responsible for computing the blocks of the puzzle. It does so by splitting the puzzle into groups of 3 rows, computing blocks for each of the groups (using the blocks/4 predicate) and finally combining all the answers into a single response by appending the created lists. The last predicate blocks/4 is recurrently computing blocks in a single 3-row group.

Tests

I tested the program using a couple of example puzzles generated by the http://onlinesudoku.pl/ website using the “diabolical” difficulty.

We launch our program by loading the database with the sudoku/1 predicate:

$ swipl -f sudoku.pl

In all of the tests the solution was found in a matter of milliseconds, which is a completely satisfying performance suited for most uses.

?- Puzzle = [
    [2,_,_,_,9,_,_,_,1],
    [3,_,9,_,_,7,_,_,_],
    [_,_,1,_,4,_,_,7,_],
    [_,6,_,_,_,_,_,_,_],
    [_,_,_,_,_,3,_,_,_],
    [_,_,8,6,_,_,7,9,_],
    [6,_,_,7,_,_,8,_,_],
    [1,2,3,_,_,8,_,_,_],
    [_,8,7,_,_,4,3,_,_]], Puzzle = [A,B,C,D,E,F,G,H,I], sudoku(Puzzle).
Puzzle = [...],
A = [2, 7, 6, 8, 9, 5, 4, 3, 1],
B = [3, 4, 9, 1, 2, 7, 5, 6, 8],
C = [8, 5, 1, 3, 4, 6, 2, 7, 9],
D = [7, 6, 2, 4, 8, 9, 1, 5, 3],
E = [9, 1, 5, 2, 7, 3, 6, 8, 4],
F = [4, 3, 8, 6, 5, 1, 7, 9, 2],
G = [6, 9, 4, 7, 3, 2, 8, 1, 5],
H = [1, 2, 3, 5, 6, 8, 9, 4, 7],
I = [5, 8, 7, 9, 1, 4, 3, 2, 6].

?- Puzzle = [
    [_,9,_,_,_,3,2,8,_],
    [5,_,_,_,_,_,3,9,_],
    [_,_,6,_,_,_,_,_,_],
    [6,_,_,8,_,_,4,_,5],
    [_,5,_,7,_,_,_,3,_],
    [_,_,9,_,4,6,_,_,_],
    [_,_,_,_,2,_,5,_,_],
    [_,8,_,6,_,_,_,_,_],
    [_,_,_,_,_,_,_,2,8]], Puzzle = [A,B,C,D,E,F,G,H,I], sudoku(Puzzle).
Puzzle = [...],
A = [4, 9, 7, 1, 5, 3, 2, 8, 6],
B = [5, 1, 8, 2, 6, 7, 3, 9, 4],
C = [3, 2, 6, 9, 8, 4, 7, 5, 1],
D = [6, 7, 2, 8, 3, 9, 4, 1, 5],
E = [8, 5, 4, 7, 1, 2, 6, 3, 9],
F = [1, 3, 9, 5, 4, 6, 8, 7, 2],
G = [9, 4, 1, 3, 2, 8, 5, 6, 7],
H = [2, 8, 5, 6, 7, 1, 9, 4, 3],
I = [7, 6, 3, 4, 9, 5, 1, 2, 8].

?- Puzzle = [
    [_,_,6,_,_,_,9,_,_],
    [_,_,_,6,_,_,_,7,5],
    [_,5,8,_,_,7,_,1,4],
    [_,6,_,_,1,_,_,5,7],
    [_,_,_,7,5,_,_,6,_],
    [_,_,_,_,_,_,3,_,_],
    [_,_,_,1,_,_,7,8,3],
    [_,1,_,_,_,3,_,4,_],
    [_,_,_,_,6,_,5,_,_]], Puzzle = [A,B,C,D,E,F,G,H,I], sudoku(Puzzle).
Puzzle = [...],
A = [7, 4, 6, 5, 8, 1, 9, 3, 2],
B = [1, 3, 2, 6, 4, 9, 8, 7, 5],
C = [9, 5, 8, 2, 3, 7, 6, 1, 4],
D = [2, 6, 9, 3, 1, 8, 4, 5, 7],
E = [4, 8, 3, 7, 5, 2, 1, 6, 9],
F = [5, 7, 1, 4, 9, 6, 3, 2, 8],
G = [6, 9, 4, 1, 2, 5, 7, 8, 3],
H = [8, 1, 5, 9, 7, 3, 2, 4, 6],
I = [3, 2, 7, 8, 6, 4, 5, 9, 1].

Conclusions

Prolog is a language, that is extremely well suited for solving logic puzzles, like sudoku. It allows realising complex argorithms using simple and short programs, giving satisfying performance (the presented program was in no way optimised - the presented version is the first created).