3

私は数独ソルバーを書いています。プロローグに触れてから長い時間が経ったので、統合、バックトラックなどに関するすべてを覚えているわけではありません。システムを永遠にバックトラックさせたと思います（ただし、スタック例外は発生しません-少なくともすぐに）。これは私がこれまでに持っているものです (パズルは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)が問題の原因です。システムは 1 列目の最初の空のボックスに 7 を入れ、それを変更しないようです (少なくとも近い将来には変更しません)。C1 リストの例は次のとおりです[5, 6, 7, 8, 4, 7, 9, 8, 6]。なぜこれが起こっているのか知りたいです。

4

1 に答える 1

4
  1. あなたの例のリストは、2回含まれている[5, 6, 7, 8, 4, 7, 9, 8, 6]ため満足していません。allunique8
  2. solve/3すべての行をチェックしますが、1 つの列のみをチェックし、「領域」(3x3 の正方形) をチェックしないため、正しくありません。
  3. コメントで約束されたsolve/1述語が表示されないため、コードをテストできません。allunique/1そしてnelement/3元気そうです。
  4. このプログラムを完了したとしても、答えが返ってくるとは思えません。同様の Prolog プログラムが何時間も実行されても解決策が見つからないのを見てきました。これを高速に実行したい場合は、CLP(fd)を調べてください(リンクは SWI 用ですが、SICStus、GNU、および ECLiPSe には同様のライブラリがあります)。
于 2011-02-11T20:48:11.543 に答える