8

我正在尝试学习一些关于 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]]).
4

3 回答 3

11

Prolog是一种不同的程序思考方式：你必须进行逻辑思考。

首先，如果 B AND C AND D 为真，则A :- B, C, D意味着A 为真（成功）。

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

  • 元素都按行不同
  • 元素都按列不同
  • 元素都相差 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)-> 对于行的三元组，此谓词必须为真。

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

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

所以我们可以递归地思考：blocks([],[],[])这是平凡的，我们有空列表。

当您使用包含至少 3 个元素的列表参数调用谓词blocks([A,B,C|Bs1],[D,E,F|Bs2],[G,H,I|Bs3])时，将选择这种情况。blocks所以我们可以检查 A、B、C、D、E、F、G、H、I 是否都是不同的，然后我们blocks使用余数列表作为参数递归调用（没有前三个元素）。这就是 Prolog 的意义所在！

所以blocks将首先用三行 9 个元素调用，它将检查每行的前 3 个是否不同，并用 3 个 6 个元素的列表调用自己，再次检查它并用 3 个 3 个元素的列表调用自己，再次检查它并用三个空列表调用自己（总是成功的琐碎案例）。

于 2009-11-21T16:14:49.323 回答
3

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

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

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

于 2009-11-20T18:31:37.013 回答
2

关于“追加（行，Vs），Vs ins 1..9”

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

这意味着列表列表的所有元素都必须在域中1..9。

于 2011-07-22T17:29:23.063 回答