Prolog's Mini Sudoku Solver stops partially through

Question

I work through Seven Languages ​​in Seven Weeks, and I'm just trying to get an example from a book. He solves the Sudoku mini-grid (4x4).

The author uses gprolog, but I use swi-prolog (I could not get gprolog to work on my VM for some reason, but swi-proog worked first).

I am running Ubuntu 10.04 on VirtualBox 4.0.4 r70112 (I hope this is not too relevant!)

Here is the code in my prologue:

:- 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:

• add use_module(library(clpfd)). up
• change fd_all_different(Head), to all_different(Head),
• change fd_domain(Puzzle, 1, 4), to Puzzle ins 1..4,

Here is the call from swipl

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

The solution is correct until it turns off, and at this point the prolog seems to determine that there is no solution. But there are:

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

I looked at the code looking for a typo or inappropriate column, but could not find the source of this. Any ideas?

Answer 1

It seems to me that you rely on the default display in SWI-Prolog to write a list representing the solution, and it is a feature of SWI-Prolog that it does not print all entries of a long list in this case, replacing the tail after nine elements with an “ellipsis” .. .

You stumbled upon this when you added write(Puzzle) to the target and thus saw the entire list. The SWI-Prolog website has frequently asked questions about this "acronym" lists .

Answer 2

You typed yourself ; , is not it? ; asks for more solutions. Since you did not use labeling for variables, Prolog only restricts them, without actually generating a complete solution (it does some distribution of constraints to get multiple values). There is only one way to put restrictions, so there is no second solution. If you place a labeling call at the end of a sudoku clause, you can loop through decisions.

(PS .: sudoku does not require two arguments, since you combine them with Solution = Puzzle .)