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).

## Where is my comment box!?

I don't do traditional comments, but you're welcome to send me an email to

`michal at muskala dot eu`

and I'll publish it at the bottom of the article as a comment.