3

我正在写一个数独求解器。自从我接触 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]. 我很想知道为什么会这样。

4

1 回答 1

4
  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 具有类似的库。）
于 2011-02-11T20:48:11.543 回答