English 中文(简体)
Prolog : Learning by example
原标题:
  • 时间:2009-11-20 04:05:10
  •  标签:
  • prolog
  • clpfd

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]]).
问题回答

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).

sudoku/1 basically describes the constraints a Sudoku solution must satisfy, where the board is represented as a list of nine lists of length nine. problem/2 assigns a partially instantiated board to a problem number. To use it you should do

?- problem(1, Board), sudoku(Board).

You should read up on the predicates used in the documentation.

about "append(Rows, Vs), Vs ins 1..9"

http://www.swi-prolog.org/pldoc/man?predicate=append%2F2

It means that all elements of the list of lists must be in the domain 1..9.





相关问题
Prolog : Learning by example

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

Working with lists in Prolog

First off let me state that this is part of a class exercise given as homework. But, the entire assignment is much more involved than the subject of this question. So.. I am searching through two ...

SWI-Prolog conditional statements

I m trying to write a function that will test to see if the word hello is contained in a list. If it is contained, i don t want it to say "true", i want it to say : "yes, the word hello is contained ...

prolog cut off in method

I have a question I would like to ask you something about a code snippet: insert_pq(State, [], [State]) :- !. insert_pq(State, [H|Tail], [State, H|Tail]) :- precedes(State, H). insert_pq(State, [...

Max out of values defined by prolog clauses

I know how to iterate over lists in Prolog to find the maximum, but what if each thing is a separate clause? For example if I had a bunch of felines and their ages, how would I find the oldest kitty? ...

热门标签