Sudoku in Prolog -- an annotated example (Bob Roos)

On the Prolog examples page there is supposedly a demonstration of a Sudoku solution in Prolog. I could not get this to work, so I played with it for a while until I figured out the problem. In the course of it I made notes on the solution, so I thought I'd go ahead and share those with you.

Here's the posted solution on that page exactly as it appears:

% permutations: one list is a reordering of the items in the other list

% perm(-List1, +List2)

perm([],[]).

perm(X,[Y|Z]):-select(X,Y,R),perm(R,Z).

sudoku(Board):-Board=[R1,R2,R3,R4],

	Board=[[X11,X12,X13,X14],[X21,X22,X23,X24],[X31,X32,X33,X34],[X41,X42,X43,X44]],

	D=[1,2,3,4], %the digits

	X11=1, X22=2,X33=3,X44=4,

	perm(R1,D), perm(R2,D), perm(R3,D),perm(R4,D),

	perm([X11,X21,X31,X41],D), %Columns

	perm([X12,X22,X32,X42],D),

	perm([X13,X23,X33,X43],D),

	perm([X14,X24,X34,X44],D),

	perm([X11,X12,X21,X22],D), %Boxes

	perm([X13,X14,X23,X24],D),

	perm([X31,X32,X41,X42],D),

	perm([X33,X34,X43,X44],D),

	write_ln(R1),

	write_ln(R2),

	write_ln(R3),

	write_ln(R4).

First, realize that this is for "4 x 4" Sudoku, not the "9 x 9" version you are used to solving. The basic idea (which is not particularly well-described in the header comments) is that the Prolog program will check each row, each column, and each corner block of four cells to see if they form a permutation of the digits from 1 to 4.

The first two rules describe how to see if one list is a permutation of another list. The base case is that an empty list is a permutation of itself:

perm([],[]).

The recursive case says that if we remove ("select") any element from the first list and make it the first element in the second list, then the tail of the second list is a permutation of whatever is left of the first list. For instance, if we select "3" from the list [1,2,3,4] and make it the first element of the second list, then the last three elements of the second list must be a permutation of [1,2,4].

FIRST ERROR:Two variables in the "select" predicate have been switched. The second rule should say:

perm(X,[Y|Z]):-select(Y,X,R),perm(R,Z).

Let's translate this into English:
"The list [Y|Z] is a permutation of X if

R is what remains after selecting Y out of the list X, and
Z is a permutation of R."

Remember Prolog's list notation: [Y|Z] is the list whose first element ("car" in LISP) is Y and whose tail ("cdr" in LISP) is Z. Thus, [3,1,2,4] = [3 | [1,2,4]] (the vertical bar "|" is like the "cons" operator in LISP).

In Prolog (or, at any rate, GProlog), "select(A,B,C)" is a built-in predicate that is true whenever B and C are lists, A is an element of B, and C is whatever remains of B when A is removed from B. Is it clear that "perm" is true whenever the second list is a permutation of the first list?

Now we move on to the main function: sudoku(Board) is true whenever Board satisfies the following conditions:

Board takes the form of a list of four elements: [R1, R2, R3, R4]
More precisely, the four elements of Board are, themselves, lists of four elements. Thus, the first element R1 of board is a list of the form [X11,X12,X13,X14], R2 is a list ... etc.
Some of the elements of the board are known in advance (these are the "filled-in" squares). For this particular puzzle, the main diagonal is filled in with the digits 1, 2, 3, 4 (i.e., X11 = 1, X22 = 2, etc.)
Each row R1, R2, R3, R4 is a permutation of the digits [1,2,3,4] (stored in a variable named "D")
Each column is a permutation of the digits [1,2,3,4]. We have to list the column elements explicitly, so, for instance, column 1 consists of the values X11, X21, X31, X41, etc.
Each corner block of four values is also a permutation of [1,2,3,4]. Again, the elements of each corner block are explicitly listed. (The comment "Boxes" refers to these corner blocks.)

Once values have been found for all the variables, each row is printed out.
Second error:For whatever reason, I can not get the "write_ln" predicate to work. However, if I substitute the word "print" for "write_ln" then this program runs. Here's the final, correct version:

% permutations: one list is a reordering of the items in the other list

% perm(-List1, +List2)

perm([],[]).

perm(X,[Y|Z]):-select(Y,X,R),perm(R,Z).

sudoku(Board):-Board=[R1,R2,R3,R4],

	Board=[[X11,X12,X13,X14],[X21,X22,X23,X24],[X31,X32,X33,X34],[X41,X42,X43,X44]],

	D=[1,2,3,4], %the digits

	X11=1, X22=2,X33=3,X44=4,

	perm(R1,D), perm(R2,D), perm(R3,D),perm(R4,D),

	perm([X11,X21,X31,X41],D), %Columns

	perm([X12,X22,X32,X42],D),

	perm([X13,X23,X33,X43],D),

	perm([X14,X24,X34,X44],D),

	perm([X11,X12,X21,X22],D), %Boxes

	perm([X13,X14,X23,X24],D),

	perm([X31,X32,X41,X42],D),

	perm([X33,X34,X43,X44],D),

	print(R1),

	print(R2),

	print(R3),

	print(R4).

This works. If you want to solve different puzzles, just replace the line beginning with "X11=1..." with your desired values.

It is easy to imitate the style of this to create a 9 x 9 Sudoku solver. I have not yet found a problem for which the program finds a solution in an acceptable amount of time (I've been running my 9x9 solver for about a half hour now and it has yet to pop up any solutions.)

Here's some sample output for the 4x4 case:

[rroos@aldenv123 ~]$ gprolog

GNU Prolog 1.2.19

By Daniel Diaz

Copyright (C) 1999-2005 Daniel Diaz

?- [sudoku].

compiling /home/cs4/rroos/sudoku.pl for byte code...
/home/cs4/rroos/sudoku.pl compiled, 25 lines read - 5128 bytes written, 10 ms

(1 ms) yes

?- sudoku(Board).

[1,4,2,3][3,2,4,1][4,1,3,2][2,3,1,4]

Board = [[1,4,2,3],[3,2,4,1],[4,1,3,2],[2,3,1,4]] ? ;
[1,3,4,2][4,2,1,3][2,4,3,1][3,1,2,4]

Board = [[1,3,4,2],[4,2,1,3],[2,4,3,1],[3,1,2,4]] ? ;

(14 ms) no

?- halt.