Prolog : Learning by example

Question

I am trying to learn a little bit about swi-prolog (beyond the basic, useless programs).

Can anyone explain (perhaps in pseudocode) what this sudoku solver and the related functions are doing? If you need more reference it is found in the CLP(FD) package of swi-prolog.

Thanks!

 :- use_module(library(clpfd)).
 sudoku(Rows) :-                                                   
         length(Rows, 9), maplist(length_(9), Rows),                
         append(Rows, Vs), Vs ins 1..9,                             
         maplist(all_distinct, Rows),                               
         transpose(Rows, Columns), maplist(all_distinct, Columns),  
         Rows = [A,B,C,D,E,F,G,H,I],                                
         blocks(A, B, C), blocks(D, E, F), blocks(G, H, I).         


 length_(L, Ls) :- length(Ls, L).                                   

 blocks([], [], []).                                                
 blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-                   
         all_distinct([A,B,C,D,E,F,G,H,I]),                         
         blocks(Bs1, Bs2, Bs3).                                     


 problem(1, [[_,_,_,_,_,_,_,_,_],                                   
             [_,_,_,_,_,3,_,8,5],                                   
             [_,_,1,_,2,_,_,_,_],                                   
             [_,_,_,5,_,7,_,_,_],                                   
             [_,_,4,_,_,_,1,_,_],                                   
             [_,9,_,_,_,_,_,_,_],                                  
             [5,_,_,_,_,_,_,7,3],                                  
             [_,_,2,_,1,_,_,_,_],                                   
             [_,_,_,_,4,_,_,_,9]]).

Answer 1

Prolog is a different way of thinking about programs: you have to think logically.

First of all A :- B, C, D means A is true (succeds) if B AND C AND D are true.

The snippet of code you posted checks for the correctness of a Sudoku puzzle, there are three condition:

• elements are all different by rows
• elements are all different by columns
• elements are all different by 3x3 blocks

How does it work?

sudoku(Rows) is true if:

1. length(Rows, 9) -> there are 9 elements in rows
2. maplist(_length(9), Rows) -> maplist checks the predicate (first parameter) on every element of the list (second parameter). This means that every row must be of length 9.
3. maplist(all_distinct, Rows) -> same as before, but we check if every row has distinct (not equal pairwise) elements.
4. transpose(Rows, Columns), maplist(all_distinct, Columns) -> we transpose the rows into columns to check if they are all distinct also by selecting them in the vertical way
5. Rows = [A,B,C,D,E,F,G,H,I] -> splits rows list and place every one in a different variable A, B, C, D ... so A will be first row, B second one and so on
6. blocks(A, B, C), blocks(D, E, F), blocks(G, H, I) -> this predicate must be true for the triplets of rows.

Let's talk about the blocks part, that is quite funny to understand. We want to check that every 3x3 block contains distinct values. How can we do that?

Suppose to have 3 rows, the condition must be true for first three elements of every row (first 3x3 block), for elements 4th to 6th (second block) and 7th-9th (third block).

So we can think recursively: blocks([],[],[]) is trivially true, we've got empty lists.

The case blocks([A,B,C|Bs1],[D,E,F|Bs2],[G,H,I|Bs3]) is chosen when you call blocks predicate with parameters that are list with AT LEAST 3 elements. So we can check if A,B,C,D,E,F,G,H,I are all distinct, then we call blocks recursively using as parameters the remainder lists (without the first three elements). This is what Prolog is about!

So blocks will be called first with three rows of 9 elements, it will check that first 3 of every row are distinct and call itself with 3 lists of 6 elements, check it again and call itself with 3 lists of 3 elements, check it again and call itself with three empty lists (the trival case that always succeds).