recursion - 数独求解器无限递归

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 方 block )。
3. 评论中 promise 的solve/1谓词没有出现，所以我无法测试你的代码； allunique/1 和 nelement/3 看起来不错。
4. 即使您完成了这个程序，我怀疑它永远不会返回答案。我见过类似的 Prolog 程序运行数小时仍未找到解决方案。查看CLP(fd)如果您想快速执行此操作(链接适用于 SWI，但 SICStus、GNU 和 ECLiPSe 具有类似的库。)