Sudoku

In the last week Prolog classes writing a sudoku solver was one of the exercises. Of course, this is not such a small task, so we concentrated on writing just a part of the solver. However, when I came home I felt the very strange feeling that I want to write my own sudoku solver. So here it is.

The representation I chose is a bit different from the ones I have seen in class and in the Internet. It is neither an array (Prolog emulation of an array using arg/3) of numbers, nor a plain list of numbers. It is a list of triples of the form X/Y/Value, where X and Y are the horizontal/vertical coordinates, and Value the number in the square. At first such a representation may seem a bit strange. However, it allows us (for example) to extract whole columns and rows through unification, which simplifies things a bit.

I have written the whole program with readability and conceptual simplicity in mind. This means it is not very efficient. I planned it to be as general as possible, so in principle it should be able to sort 27x27 sudoku. However, due to the lack of efficiency this may take quite a long time (provided you had a 27x27 grid partially filled with integers from 1 to 81, of course).

%
% all the elements in a column, row, 3x3 box.
%

column(X/_, Sudoku, Column) :-
 findall(X/Y/Z , (member(X/Y/Z, Sudoku), nonvar(Z)), Column).

row(_/Y, Sudoku, Row) :-
 findall(X/Y/Z, (member(X/Y/Z, Sudoku), nonvar(Z)), Row).


% believe me or not, this was the most difficult predicate to write.
box(Base, X/Y, Sudoku, Box) :- % Base: size of the puzzle
 DiffX is (X-1) mod (Base/3),
 DiffY is (Y-1) mod (Base/3),
 StartX is X - DiffX,
 StartY is Y - DiffY,
 EndX is StartX + (Base/3) - 1,
 EndY is StartY + (Base/3)-1,
 findall(X1/Y1/Z,
         (
          between(StartX,EndX,X1),
          between(StartY, EndY, Y1),
          member(X1/Y1/Z, Sudoku),
          nonvar(Z)
         ),
         Box).

%
% We can assign the value Possible to X/Y without
% violating the rules of the sudoku.
%
possible(_,X/Y/Possible, Sudoku) :-
 member(X/Y/Possible, Sudoku),
 nonvar(Possible), !.
possible(Base, X/Y/Possible, Sudoku) :-
 column(X/Y, Sudoku, Column),
 row(X/Y, Sudoku, Row),
 box(Base, X/Y, Sudoku, Box),
 between(1,Base, Possible),
 \+member(_/_/Possible, Column),
 \+member(_/_/Possible, Row),
 \+member(_/_/Possible, Box).

% solve the puzzle, iterating through each grid
solve(_,N,N,_).
solve(Base,N,K,Solution) :-
 nth1(N, Solution, X/Y/Z),
 possible(Base, X/Y/Z, Solution),
 NewN is N+1,
 solve(Base, NewN, K, Solution).
solve(Base,Solution) :-
 N is Base*Base+1,
 solve(Base,1, N, Solution).

% the main predicate
%
sudoku(Base,Constraints, Solution) :-
 findall(X/Y/_, (between(1,Base,X), between(1,Base,Y)), Solution),
 subset(Constraints, Solution),
 solve(Base,Solution).

/*

And some example puzzles to solve:

*/

s3([3/1/3, 2/2/8,
      5/1/4, 4/2/6, 6/2/3, 4/3/5,
      8/1/9, 8/3/4,
      1/4/5, 1/6/2, 3/6/7,
      4/4/9, 5/4/1, 4/5/2, 6/5/7, 5/6/8, 6/6/6,
      7/4/3, 9/4/7, 9/6/5,
      2/7/3, 2/9/5,
      4/8/7, 5/9/6, 6/7/5, 6/8/1,
      7/9/4, 8/8/5]).

% the sudoku from class
s1([1/4/2, 1/5/3, 1/9/5,
      2/2/4, 2/3/2, 2/5/9, 2/9/3,
      3/1/3, 3/6/8, 3/7/7,
      4/3/7, 4/8/5, 4/9/6,
      5/2/9, 5/4/7, 5/5/2, 5/8/1, 5/9/4,
      6/1/5, 6/4/9,
      7/1/6, 7/6/2, 7/7/8, 7/8/4, 7/9/9,
      8/3/8, 8/6/1, 8/9/7,
      9/1/2, 9/2/5, 9/6/9, 9/7/6]).

s2([4/1/2, 5/1/3, 9/1/5,
      2/2/4, 3/2/2, 5/2/9, 9/2/3,
      1/3/3, 6/3/8, 7/3/7,
      3/4/7, 8/4/5, 9/4/6,
      2/5/9, 4/5/7, 5/5/2, 8/5/1, 9/5/4,
      1/6/5, 4/6/9,
      1/7/6, 6/7/2, 7/7/8, 8/7/4, 9/7/9,
      3/8/8, 6/8/1, 9/8/7,
      1/9/2, 2/9/5, 6/9/9, 7/9/6]).

I also wrote print_su/1, a sudoku pretty-printer. It is not very interesting, and I used findall/3 to iterate through a list and print its elements (which may be considered abusive), so I decided not to publish it here :).

Now, we can use Prolog to run the following query:

?- s1(Constraints),sudoku(9,Constraints,Sudoku), print_su(Sudoku).

1  7  3 || 4  8  5 || 6  9  2
8  4  6 || 2  9  1 || 7  3  5
9  2  5 || 7  6  3 || 1  8  4
==============================
2  5  4 || 1  7  9 || 3  6  8
3  9  1 || 8  2  6 || 5  4  7
7  6  8 || 3  5  4 || 2  1  9
==============================
4  1  7 || 9  3  2 || 8  5  6
6  8  9 || 5  1  7 || 4  2  3
5  3  2 || 6  4  8 || 9  7  1

Constraints = [1/4/2, 1/5/3, 1/9/5, 2/2/4, 2/3/2, 2/5/9, 2/9/3, ... /... /3, ... /...|...]
Sudoku = [1/1/1, 1/2/8, 1/3/9, 1/4/2, 1/5/3, 1/6/7, 1/7/4, ... /... /6, ... /...|...] 

and voilà, your sudoku is ready!

(I think that it may be sensible using constraint logic programming for solving sudoku... However, I haven't reached the chapter about CLP in my book yet, so I didn't use it. ;-))