Prolog:通过实例学习

Question

我正在尝试学习一些swi-prolog(超出基本的,无用的程序).

任何人都可以解释(可能是伪代码)这个数独求解器和相关函数正在做什么？如果您需要更多参考,可以在swi-prolog的CLP(FD)包中找到.

谢谢!

 :- 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是一种不同的程序思考方式:你必须从逻辑上思考.

首先,A :- B, C, D装置A是真的(succeds)如果B和C以及d是真实的.

你发布的代码片段检查数独谜题的正确性,有三个条件:

• 元素都是按行不同的
• 元素都是不同的列
• 3x3块的元素都不同

它是如何工作的？

如果满足以下条件,则数独(行)为真:

1. length(Rows, 9) - >行中有9个元素
2. maplist(_length(9), Rows)- > maplist检查列表中每个元素的谓词(第一个参数)(第二个参数).这意味着每行的长度必须为9.
3. maplist(all_distinct, Rows) - >和以前一样,但是我们检查每一行是否有不同的(不相等的成对)元素.
4. transpose(Rows, Columns), maplist(all_distinct, Columns) - >我们将行转换为列,通过以垂直方式选择它们来检查它们是否都是不同的
5. Rows = [A,B,C,D,E,F,G,H,I] - >拆分行列表并将每一个放在不同的变量A,B,C,D ......所以A将是第一行,B是第二行,依此类推
6. blocks(A, B, C), blocks(D, E, F), blocks(G, H, I) - >对于行的三元组,此谓词必须为true.

让我们谈谈这个blocks部分,这很有趣.我们想检查每个3x3块是否包含不同的值.我们怎么做？

假设有3行,对于第4至第6(第二块)和第7至第9块(第三块)的元素,条件必须为每行的前三个元素(第一个3x3块)为真.

所以我们可以递归blocks([],[],[])地思考:很简单,我们有空列表.

blocks([A,B,C|Bs1],[D,E,F|Bs2],[G,H,I|Bs3])当您blocks使用具有至少3个元素的列表参数调用谓词时,将选择该案例.因此我们可以检查A,B,C,D,E,F,G,H,I是否都是不同的,然后我们blocks使用余数列表作为参数递归调用(没有前三个元素).这就是Prolog的意思!

因此blocks将首先调用三行9个元素,它将检查每行的前三个是不同的,并使用3个6个元素的列表调用自身,再次检查并使用3个元素的3个列表调用自身,再次检查它用三个空列表调用自己(总是成功的trival案例).

Answer 2

sudoku/1 基本上描述了数独解决方案必须满足的约束，其中棋盘表示为由九个长度为 9 的列表组成的列表。Problem/2 将部分实例化的板分配给问题编号。要使用它你应该这样做

？- 问题（1，棋盘），数独（棋盘）。

您应该阅读文档中使用的谓词。