数独求解器无限递归

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

来源

2011-02-11 ierax

您的示例列表[5, 6, 7, 8, 4, 7, 9, 8, 6]不满足allunique，因为它包含8两次。
solve/3不正确，因为它检查所有的行，但只有一列，没有“区域”（3×3方块）。
在注释中承诺的谓词solve/1没有出现，所以我无法测试你的代码; allunique/1和nelement/3看起来不错。
即使你完成这个程序，我怀疑它会一直回答一个答案。我见过类似的Prolog程序运行几个小时而没有找到解决方案。如果您想快速完成此操作，请查看（链接用于SWI，但SICStus，GNU和ECLiPSe具有相似的库。）

来源

2011-02-11 20:48:11

您可以使用该代码。解决/ 1还没有实现，因为我有一个问题。现在仅供演示解决/ 3 - 你熟悉prolog吗？只需执行solve（X，Y，Z）即可查看结果。我的“示例”是系统尝试执行的操作，因为列1的第三个值不是由我设置的。我非常肯定，如果不使用CLP或者甚至像cut操作符那样的优化，就可以找到有效的解决方案。已经在网上，但我不喜欢复制粘贴编程... – ierax 2011-02-11 21:01:03

数独求解器无限递归

回答

相关问题