судоку решатель бесконечная рекурсия - PullRequest
Новая
       17

судоку решатель бесконечная рекурсия

3 голосов
/ 11 февраля 2011

Я пишу решатель судоку. Прошло много времени с тех пор, как я коснулся пролога, поэтому я не помню всего, что касается унификации, возврата назад и т. Д. Я думаю, что я заставляю систему возвращаться назад навсегда (но я не получаю никаких стековых исключений - по крайней мере, нет немедленно). Это то, что у меня есть (загадку можно найти по адресу 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 в первое пустое поле 1-го столбца и никогда не меняет его (или, по крайней мере, не в ближайшем будущем). Пример списка C1: [5, 6, 7, 8, 4, 7, 9, 8, 6]. Мне любопытно узнать, почему это происходит.

1 Ответ

4 голосов
/ 11 февраля 2011
  1. Ваш пример списка [5, 6, 7, 8, 4, 7, 9, 8, 6] не удовлетворяет allunique, поскольку он содержит 8 дважды.
  2. solve/3 неверно, поскольку он проверяет все строки, но только один столбец и нет"регион" (квадраты 3х3).
  3. Предикат solve/1, обещанный в комментариях, не появляется, поэтому я не могу проверить ваш код;allunique/1 и nelement/3 кажутся нормальными.
  4. Даже если вы закончите эту программу, я сомневаюсь, что она когда-нибудь даст ответ.Я видел подобные программы Prolog, которые запускались часами, но не нашли решения.Проверьте CLP (fd) , если вы хотите сделать это быстро (ссылка для SWI, но SICStus, GNU и ECLiPSe имеют похожие библиотеки.)
...