序言 : Learning by example

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

序言是对程序的另一种思考方式:您必须进行逻辑思考。

首先A :- B, C, D表示如果 B AND C AND D 为真，则 A 为真(成功)。

您发布的代码片段检查数独谜题的正确性，有以下三个条件:

元素都因行而异

元素因列而异

元素都相差 3x3 block

它是如何工作的？

数独(行)为真，如果:

length(Rows, 9) -> 行中有 9 个元素

maplist(_length(9), Rows) -> maplist检查列表中每个元素(第二个参数)的谓词(第一个参数)。这意味着每一行的长度必须为 9。

maplist(all_distinct, Rows) -> 和以前一样，但是我们检查每一行是否有不同的(不相等的成对的)元素。

transpose(Rows, Columns), maplist(all_distinct, Columns) -> 我们将行转置为列，以检查它们是否都不同，也可以通过垂直方式选择它们

Rows = [A,B,C,D,E,F,G,H,I] -> 拆分行列表并将每个行放在不同的变量 A、B、C、D 中……所以 A 将是第一行，B 是第二行，依此类推

blocks(A, B, C), blocks(D, E, F), blocks(G, H, I) -> 对于行的三元组，此谓词必须为真。

说说 blocks部分，这很有趣。我们要检查每个 3x3 block 是否包含不同的值。我们怎么能做到这一点？

假设有 3 行，对于每行的前三个元素(第一个 3x3 block )、第 4 到第 6 个元素(第二个 block )和第 7-9 个元素(第三个 block )，条件必须为真。

所以我们可以递归思考: 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 个是否不同，并使用 3 个 6 个元素的列表调用自身，再次检查并使用 3 个元素的 3 个列表调用自身，再次检查并调用本身带有三个空列表(总是成功的琐碎案例)。