Prolog 中的迷你数独求解器在中途停止 [英] Mini sudoku solver in Prolog stops partway through

问题描述

我正在学习七周内使用七种语言"，我只是想从书中找到一个例子.它解决了一个迷你数独网格 (4x4).

作者使用的是 gprolog，但我使用的是 swi-prolog(无论出于何种原因，我都无法让 gprolog 在我的 VM 上工作，但 swi-prolog 首先尝试).

我在 VirtualBox 4.0.4 r70112 中运行 Ubuntu 10.04(希望这不是太相关！)

这是我的 prolog 文件中的代码:

:- use_module(library(clpfd)).有效的([]).有效([头|尾]):-all_different(Head), % in the book, this is 'fd_all_different'有效(尾).% 数独规则本身的开头数独(拼图，解决方案):-解决方案 = 拼图，拼图 = [S11, S12, S13, S14,S21、S22、S23、S24、S31、S32、S33、S34、S41, S42, S43, S44],拼图ins 1..4, % in the book, this is 'fd_domain'第 1 行 = [S11, S12, S13, S14],第 2 行 = [S21, S22, S23, S24],第 3 行 = [S31, S32, S33, S34],第 4 行 = [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],有效([行1，行2，行3，行4，第 1 列、第 2 列、第 3 列、第 4 列、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, _, _],解决方案).解 = [4, 1, 2, 3, 2, 3, 4, 1, 1|...] ;错误的.

解是正确的，直到它被切断，此时 prolog 似乎确定没有解.但是有:

4 1 2 32 3 4 11 2 3 43 4 1 2

我已经搜索了代码以查找拼写错误或错位的列，但一直无法找到其来源.有什么想法吗?

解决方案

在我看来，您是在依赖 SWI-Prolog 中的默认显示来编写代表解决方案的列表，这是 SWI-Prolog 的一个特性在这种情况下，它不会打印长列表的所有条目，用省略号"替换九个项目后的尾部......

当您将 write(Puzzle) 添加到目标并因此看到整个列表时，您偶然发现了这一点.SWI-Prolog 的网站有一个关于这个列表缩写"的常见问题..>

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), to all_different(Head),
• changing fd_domain(Puzzle, 1, 4), to Puzzle 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?

解决方案

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 中的迷你数独求解器在中途停止的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！