数独求解器无限递归

Question

我正在编写一个数独求解器。我已经很久没有接触过Prolog了，因此我不记得有关统一、回溯等方面的所有内容。我认为我可能会导致系统永远回溯（但我没有立即收到任何堆栈异常）。这是我目前的代码（可以在http://en.wikipedia.org/wiki/File:Sudoku-by-L2G-20050714.svg找到谜题）：

% representation of the example puzzle
puzzle([5, 3, _, _, 7, _, _, _, _],
       [6, _, _, 1, 9, 5, _, _, _],
       [_, 9, 8, _, _, _, _, 6, _],
       [8, _, _, _, 6, _, _, _, 3],
       [4, _, _, 8, _, 3, _, _, 1],
       [7, _, _, _, 2, _, _, _, 6],
       [_, 6, _, _, _, _, 2, 8, _],
       [_, _, _, 4, 1, 9, _, _, 5],
       [_, _, _, _, 8, _, _, 7, 9]).

% solve(S)
% the starting point of the program
% saves the solution in the variable S
solve(R1, R2, C1) :-
    % save the rows into variables
    puzzle(R1, R2, R3, R4, R5, R6, R7, R8, R9),
    % solve for each row
    allunique(R1), allunique(R2), allunique(R3),
    allunique(R4), allunique(R5), allunique(R6),
    allunique(R7), allunique(R8), allunique(R9),
    % the columns must be created first
    nelement(R1, 1, C11), nelement(R2, 1, C21), nelement(R3, 1, C31),
    nelement(R4, 1, C41), nelement(R5, 1, C51), nelement(R6, 1, C61),
    nelement(R7, 1, C71), nelement(R8, 1, C81), nelement(R9, 1, C91),
    C1 = [C11, C21, C31, C41, C51, C61, C71, C81, C91],
    allunique(C1).

% allunique(List)
% Succeeds if all the numbers of List are between 1-9
% and each number exists only once
allunique([]). % Recursion stops when the list is empty

% A member should be between 1-9 and not a member of the tail
allunique([H|T]) :-
    allunique(T),
    member(H, [1, 2, 3, 4, 5, 6, 7, 8, 9]),
    not(member(H, T)).

% nelement(List, N-th, X)
% Saves the nth element of a list in variable X
nelement([H|_], 1, H). % The first element is the head

% All other elements will be found in the tail
nelement([_|T], N, X) :-
    N > 1,
    N1 is N-1,
    nelement(T, N1, X).

allunique(C1)这一行代码引起了问题。看起来系统将7放在第一列的第一个空格中，并且从未更改它（或者至少在不久的将来不会更改）。一个示例C1列表是[5, 6, 7, 8, 4, 7, 9, 8, 6]。我很好奇为什么会出现这种情况。

- sakisk

Answer 1

1. 你的示例列表[5, 6, 7, 8, 4, 7, 9, 8, 6]不符合allunique，因为它包含了两个8。
2. solve/3是错误的，因为它只检查所有行，但只检查了一列和没有“区域”（3x3方格）。
3. 在注释中承诺的solve/1谓词没有出现，所以我无法测试您的代码；allunique/1和nelement/3看起来很好。
4. 即使您完成此程序，我怀疑它永远不会返回答案。我曾见过类似的Prolog程序运行数小时而未找到解决方案。如果想快速完成，请查看CLP(fd)（链接适用于SWI，但SICStus，GNU和ECLiPSe有类似的库）。

- Fred Foo

---

你可以使用这段代码。solve/1还没有实现，因为我遇到了一个问题。目前只是为了演示而使用solve/3 - 你熟悉Prolog吗？只需执行solve(X,Y,Z)即可查看结果。我的“示例”是系统正在尝试完成的内容，因为第一列的第三个值不是由我设置的。我相信可以找到一种有效的解决方案，而无需使用CLP甚至像cut操作符这样的优化。虽然已经有类似的解决方案在网上，但我不喜欢复制粘贴编程... - sakisk

@faif，你的allunique/3对于正确的列表是可以证明正确的（尽管其描述不正确）。我没有得到你的输出示例。问题在于，在solve/3中，你正在循环遍历2.4e23个可能性，以找到列也匹配的可能性。（剪枝也无济于事。如果你想要解决数独问题，你需要一个不同于朴素回溯的算法。） - Fred Foo

你关于性能的看法是正确的。问题出在allunique谓词上。当我使用clpfd并将其替换为all_different时，立即找到了解决方案。感谢你的提示。我希望可以在不使用任何额外库的情况下找到解决方案，但似乎不行（至少在使用简单方法时）...要获得示例的结果，您需要注释掉最后一个allunique调用，因为它不会终止 :) - sakisk

我已经做了。请注意，代码还有一个问题，我刚刚注意到。nelement/3 应该调用自身，而不是 element/3 谓词。但由于这不是问题的核心，我已经在提供的代码中更新了它。 - sakisk