数独求解器无限递归

Question

我正在编写一个数独求解器。我已经很长时间没有接触过序言了，因此我不记得有关统一、回溯等的所有内容。我认为我导致系统永远回溯（但我没有得到任何堆栈异常 - 至少没有）立即地）。这是我到目前为止所拥有的（可以在 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]。我很好奇为什么会发生这种情况。

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 也有类似的库。）