Prolog 中的迷你数独求解器中途停止
我正在学习《七周七种语言》，我只是想从书中找到一个例子。它解决迷你数独网格 (4x4)。
作者使用的是 gprolog，但我使用的是 swi-prolog（无论出于何种原因，我都无法让 gprolog 在我的虚拟机上工作，但 swi-prolog 第一次尝试就可以工作）。
我在 VirtualBox 4.0.4 r70112 中运行 Ubuntu 10.04（希望这不太相关！）
这是我的 prolog 文件中的代码：
:- use_module(library(clpfd)).
valid([]).
valid([Head|Tail]) :-
all_different(Head), % in the book, this is 'fd_all_different'
valid(Tail).
% beginning of sudoku rule itself
sudoku(Puzzle, Solution) :-
Solution = Puzzle,
Puzzle = [S11, S12, S13, S14,
S21, S22, S23, S24,
S31, S32, S33, S34,
S41, S42, S43, S44],
Puzzle ins 1..4, % in the book, this is 'fd_domain'
Row1 = [S11, S12, S13, S14],
Row2 = [S21, S22, S23, S24],
Row3 = [S31, S32, S33, S34],
Row4 = [S41, S42, S43, S44],
Col1 = [S11, S21, S31, S41],
Col2 = [S12, S22, S32, S42],
Col3 = [S13, S23, S33, S43],
Col4 = [S14, S24, S34, S44],
Square1 = [S11, S12, S21, S22],
Square2 = [S13, S14, S23, S24],
Square3 = [S31, S32, S41, S42],
Square4 = [S33, S34, S43, S44],
valid([Row1, Row2, Row3, Row4,
Col1, Col2, Col3, Col4,
Square1, Square2, Square3, Square4]).
我（有意）更改的唯一部分是：
- 添加
use_module(library(clpfd)) .顶部的 fd_all_ Different(Head),更改为all_ Different(Head),- 将
fd_domain(Puzzle, 1, 4),更改为Puzzle ins 1..4,
以下是 swipl 的调用
?- sudoku([_, _, 2, 3,
_, _, _, _,
_, _, _, _,
3, 4, _, _],
Solution).
Solution = [4, 1, 2, 3, 2, 3, 4, 1, 1|...] ;
false.
该解在它中断之前都是正确的，此时序言似乎确定没有解。但有一个问题：
4 1 2 3
2 3 4 1
1 2 3 4
3 4 1 2
我已经搜索了代码以查找拼写错误或放错位置的列，但无法找到其来源。有什么想法吗？
I'm working through 'Seven Languages in Seven Weeks', and I'm just trying to get an example from the book working. It solves a mini sudoku grid (4x4).
The author is using gprolog, but I am using swi-prolog (I couldn't get gprolog to work on my VM for whatever reason, but swi-prolog worked first try).
I am running Ubuntu 10.04 in VirtualBox 4.0.4 r70112 (hopefully that's not too relevant!)
Here is the code in my prolog file:
:- use_module(library(clpfd)).
valid([]).
valid([Head|Tail]) :-
all_different(Head), % in the book, this is 'fd_all_different'
valid(Tail).
% beginning of sudoku rule itself
sudoku(Puzzle, Solution) :-
Solution = Puzzle,
Puzzle = [S11, S12, S13, S14,
S21, S22, S23, S24,
S31, S32, S33, S34,
S41, S42, S43, S44],
Puzzle ins 1..4, % in the book, this is 'fd_domain'
Row1 = [S11, S12, S13, S14],
Row2 = [S21, S22, S23, S24],
Row3 = [S31, S32, S33, S34],
Row4 = [S41, S42, S43, S44],
Col1 = [S11, S21, S31, S41],
Col2 = [S12, S22, S32, S42],
Col3 = [S13, S23, S33, S43],
Col4 = [S14, S24, S34, S44],
Square1 = [S11, S12, S21, S22],
Square2 = [S13, S14, S23, S24],
Square3 = [S31, S32, S41, S42],
Square4 = [S33, S34, S43, S44],
valid([Row1, Row2, Row3, Row4,
Col1, Col2, Col3, Col4,
Square1, Square2, Square3, Square4]).
The only parts that I (intentionally) changed were:
- adding
use_module(library(clpfd)).at the top - changing
fd_all_different(Head),toall_different(Head), - changing
fd_domain(Puzzle, 1, 4),toPuzzle ins 1..4,
Here is the invocation from swipl
?- sudoku([_, _, 2, 3,
_, _, _, _,
_, _, _, _,
3, 4, _, _],
Solution).
Solution = [4, 1, 2, 3, 2, 3, 4, 1, 1|...] ;
false.
The solution is correct right up until it cuts off, at which point prolog seems to determine that there is no solution. But there is:
4 1 2 3
2 3 4 1
1 2 3 4
3 4 1 2
I've scoured the code looking for a typo or misplaced column, but have been unable to find the source of this. Any ideas?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
在我看来，您似乎依赖 SWI-Prolog 中的默认显示来编写代表解决方案的列表，这是 SWI-Prolog 的一个功能，在这种情况下，它不会打印长列表的所有条目，而是将九个项目后面带有“省略号”的尾部...
当您将
write(Puzzle)添加到目标并因此看到整个列表时，您偶然发现了这一点。 SWI-Prolog 的网站有关于此列表“缩写”的常见问题解答。It seems to me you are relying on the default display in SWI-Prolog to write the list that represents the solution, and it's a feature of SWI-Prolog that it doesn't print all the entries of a long list in this case, replacing the tail after nine items with the "ellipsis" ...
You stumbled onto this when you added
write(Puzzle)to the goal and thus saw the entire list. SWI-Prolog's site has a FAQ about this "abbreviation" of lists.您自己输入了
;，不是吗？;寻求更多解决方案。由于您没有在变量上使用标签，Prolog 仅约束它们，而没有实际生成完整的解决方案（它做了一些约束传播以导出一些值）。只有一种方法可以施加约束，因此没有第二种解决方案。如果您在sudoku子句末尾调用labeling，则可以循环浏览解决方案。（PS：
sudoku不需要两个参数，因为您可以使用Solution = Puzzle将它们统一起来。）You typed in the
;yourself, didn't you?;asks for more solutions. Since you didn't uselabelingon the variables, Prolog only constrains them without actually generating a complete solution (it does some constraint propagation to derive a few of the values). There's only one way to put the constraints, so there's no second solution. If you put a call tolabelingat the end of thesudokuclause, you can cycle through the solutions.(PS.:
sudokudoesn't need two arguments, since you unify them withSolution = Puzzle.)