數獨求解器無限遞歸

我正在寫一個數獨求解器。自從我接觸了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

數獨求解器無限遞歸

回答

相關問題