Archive for the 'Prolog' Category

I’ve been meaning to write this for a while. It started when I camed across this page of the shortest sudoku solvers. They all follow the basic algorithm, which is described here. I orginally thought it was a brute force algorithm, so I wanted a more elegant solution, but on closer examination it in fact uses constraints and backtracking, like a Prolog program would. Still I wanted to write one in Prolog. It turns out it’s quite simple, and here is my program:

% Sudoku Solver
%
% Author: Miles Barr
% Version: 1.0
%
% Example Usage:
%
% Board = [ [_,_,3,_,4,9,_,_,8],
%           [_,1,_,5,_,_,_,3,_],
%           [8,_,7,3,_,_,_,_,_],
%           [_,6,8,9,_,_,_,_,5],
%           [2,_,_,_,_,_,_,_,6],
%           [4,_,_,_,_,6,7,1,_],
%           [_,_,_,_,_,5,9,_,3],
%           [_,8,_,_,_,1,_,6,_],
%           [9,_,_,2,3,_,1,_,_]
%         ],
% sudoku(Board),
% print_board(Board).

:- use_module(library('clp/bounds')).
:- use_module(library('lists')).

% Our general constraint is that each set of 9 (row, column or 3x3 grid) is made
% up from the numbers 1-9, and each number is not repeated.
valid(L) :- L in 1..9, all_different(L).

% Transpose function from Worksheet 16 of 'Clause and Effect'
transpose([[]|_],[]).
transpose(R,[H|C]) :- chopcol(R,H,T), transpose(T,C).
chopcol([],[],[]).
chopcol([[H|T]|R],[H|Hs],[T|Ts]) :- chopcol(R,Hs,Ts).

% Describe 3 grids in terms of 3 rows
% TODO: There must be a better way to do this.
grids([E11,E12,E13,E14,E15,E16,E17,E18,E19],
      [E21,E22,E23,E24,E25,E26,E27,E28,E29],
      [E31,E32,E33,E34,E35,E36,E37,E38,E39],
      [E11,E12,E13,E21,E22,E23,E31,E32,E33],
      [E14,E15,E16,E24,E25,E26,E34,E35,E36],
      [E17,E18,E19,E27,E28,E29,E37,E38,E39]).

% Print a board
print_board([]).
print_board([H|T]) :- write(H), nl, print_board(T).

% Sudoku solving function. 
%
% Input is nine lists of nine integers
sudoku(Board) :-
  % Break the board down into rows
  Board = [R1, R2, R3, R4, R5, R6, R7, R8, R9],
  % Transpose the board to get the columns
  transpose(Board, [C1, C2, C3, C4, C5, C6, C7, C8, C9]),
  % Cut up the rows into 3x3 grids
  grids(R1,R2,R3,G1,G2,G3),
  grids(R4,R5,R6,G4,G5,G6),
  grids(R7,R8,R9,G7,G8,G9),
  % Each row contains unique entries
  valid(R1), valid(R2), valid(R3),
  valid(R4), valid(R5), valid(R6),
  valid(R7), valid(R8), valid(R9),
  % Each column contains unique entries
  valid(C1), valid(C2), valid(C3),
  valid(C4), valid(C5), valid(C6),
  valid(C7), valid(C8), valid(C9),
  % Each grid contains unique entries
  valid(G1), valid(G2), valid(G3),
  valid(G4), valid(G5), valid(G6),
  valid(G7), valid(G8), valid(G9),

  % Turn the board into a list of 81 variables
  flatten(Board, Elements),
  %sign a value to each variable
  label(Elements).

I used SWI Prolog, but it should be trivial to port to other versions.

The general constraint is described by the valid clause, each list must contain all the numbers 1 through 9 exactly once. The list can represent a row, column or 3×3 grid. The next bit is breaking up the board into rows, columns and 3×3 grids, and then making sure each one is valid, which is what the sudoku clause does. That’s it really, and that’s what my first version looked like. In fact my original valid clause was:

valid(L) :- permutation([1,2,3,4,5,6,7,8,9], L).

and I didn’t constraint the values and do a labelling. That didn’t work, or it might work, but it takes a very long time. I came across this Prolog solver, which reminded me of labelling, so I removed the use of permutation, the result, a near instantaneous solver. I also borrowed his printing function.

It’s much longer than the other versions, but it has the nice property that you describe the constraints, and that’s your program, you don’t need to implement backtracking. There are still improvements to be made here, the most important one would be to add in some sort of heuristic to guide the backtracking, at the moment it’s naive and problem does more work than it needs to.

But is this the best way to solve a Sudoku puzzle? One other idea I’ve started thinking about is representing the board as a graph. We have 81 squares, each with 9 values, so we start off with 729 nodes. Each node represents a possible value for that square. Each value node for that square is connected to all the other value nodes of the squares next to it. As we discover the value of certain squares we can mark arcs to other values as illegal, and not use them in our path. Once we have a legal path through one value node for each square, we’re done. Ultimately this method requires the use of the same constraints, so it probably won’t be much better than the list based solution, but it could allow multiple walkers to discover legal row, column or grid paths in parallel, eventually joining them up. This parallelisation might lead to a faster solution. But I’ll leave the implementation and analysis to another time.

I’ve been wondering what language to learn next for a while. Scala caught my eye. I really should spend more time with Ruby since Rails programming hasn’t taught me much about the dynamic aspects of the language, which is what makes it interesting. I also want to pick up Scheme at some point. So what language did I go for? Prolog.

Not the most practical language in the world, but it’s one of those languages I liked at university but haven’t played with since. It’s not the most popular language either, in fact I think they’ve dropped the advanced Prolog course from the Computing degree at Imperial, which is a shame.

Since I’ve done some Prolog programming before I avoided a beginner’s tutorial and went for Clause and Effect: Prolog Programming for the Working Programmer, which is a terse introduction and series of exercises. I’ve worked through the first two chapters, which is a refresher on lists and backtracking, and remember why I like it so much. You just state what the program is supposed to be rather than how it’s supposed to do it. I remember going from the Prolog labs to Java programming and getting annoyed that just writing a pre and post condition wasn’t enough, you actually had to manipulate your data.

I’m not sure how learning Prolog again will improve my programming, but I’m certain it will, at very least it’ll make me consider backtracking as another form of control flow.

On a slight tangent, IBM DeveloperWorks has an interesting article on how you can use continuations in Scheme to implement Prolog style backtracking. They also show how to implement Python’s generators and Java’s exceptions. I really must learn Scheme so I can understand it.