Search code examples
prologsudokuclpfd

Mini sudoku solver in Prolog stops partway through

I'm working through 'Seven Languages in Seven Weeks', and I'm just trying to get an example from the book working. It solves a mini sudoku grid (4x4).

The author is using gprolog, but I am using swi-prolog (I couldn't get gprolog to work on my VM for whatever reason, but swi-prolog worked first try).

I am running Ubuntu 10.04 in VirtualBox 4.0.4 r70112 (hopefully that's not too relevant!)

Here is the code in my prolog file:

:- use_module(library(clpfd)).

valid([]).
valid([Head|Tail]) :-
    all_different(Head),    % in the book, this is 'fd_all_different'
    valid(Tail).

 % beginning of sudoku rule itself
sudoku(Puzzle, Solution) :- 
Solution = Puzzle,
Puzzle = [S11, S12, S13, S14,
          S21, S22, S23, S24,
          S31, S32, S33, S34,
          S41, S42, S43, S44],
Puzzle ins 1..4,    % in the book, this is 'fd_domain'

Row1 = [S11, S12, S13, S14],
Row2 = [S21, S22, S23, S24],
Row3 = [S31, S32, S33, S34],
Row4 = [S41, S42, S43, S44],

Col1 = [S11, S21, S31, S41],
Col2 = [S12, S22, S32, S42],
Col3 = [S13, S23, S33, S43],
Col4 = [S14, S24, S34, S44],

Square1 = [S11, S12, S21, S22],
Square2 = [S13, S14, S23, S24],
Square3 = [S31, S32, S41, S42],
Square4 = [S33, S34, S43, S44],

valid([Row1, Row2, Row3, Row4,
       Col1, Col2, Col3, Col4,
       Square1, Square2, Square3, Square4]).

The only parts that I (intentionally) changed were:

  • adding use_module(library(clpfd)). at the top
  • changing fd_all_different(Head), to all_different(Head),
  • changing fd_domain(Puzzle, 1, 4), to Puzzle ins 1..4,

Here is the invocation from swipl

?- sudoku([_, _, 2, 3,
           _, _, _, _,
           _, _, _, _,
           3, 4, _, _],
Solution).
Solution = [4, 1, 2, 3, 2, 3, 4, 1, 1|...] ;
false.

The solution is correct right up until it cuts off, at which point prolog seems to determine that there is no solution. But there is:

4 1 2 3
2 3 4 1
1 2 3 4
3 4 1 2

I've scoured the code looking for a typo or misplaced column, but have been unable to find the source of this. Any ideas?

Solution

  • It seems to me you are relying on the default display in SWI-Prolog to write the list that represents the solution, and it's a feature of SWI-Prolog that it doesn't print all the entries of a long list in this case, replacing the tail after nine items with the "ellipsis" ...

    You stumbled onto this when you added write(Puzzle) to the goal and thus saw the entire list. SWI-Prolog's site has a FAQ about this "abbreviation" of lists.