Мини-решатель судоку в Прологе останавливается на полпути - PullRequest
Новая
       13

Мини-решатель судоку в Прологе останавливается на полпути

4 голосов
/ 11 апреля 2011

Я работаю над «Семью языками за семь недель» и просто пытаюсь получить пример из работы с книгой.Он решает мини-сетку судоку (4x4).

Автор использует gprolog, но я использую swi-prolog (по какой-то причине я не смог заставить gprolog работать на моей виртуальной машине, но swi-prolog сработалпервая попытка).

Я запускаю Ubuntu 10.04 в VirtualBox 4.0.4 r70112 (надеюсь, это не слишком актуально!)

Вот код в моем файле пролога: 

:- use_module(library(clpfd)).

valid([]).
valid([Head|Tail]) :-
    all_different(Head),    % in the book, this is 'fd_all_different'
    valid(Tail).

 % beginning of sudoku rule itself
sudoku(Puzzle, Solution) :- 
Solution = Puzzle,
Puzzle = [S11, S12, S13, S14,
          S21, S22, S23, S24,
          S31, S32, S33, S34,
          S41, S42, S43, S44],
Puzzle ins 1..4,    % in the book, this is 'fd_domain'

Row1 = [S11, S12, S13, S14],
Row2 = [S21, S22, S23, S24],
Row3 = [S31, S32, S33, S34],
Row4 = [S41, S42, S43, S44],

Col1 = [S11, S21, S31, S41],
Col2 = [S12, S22, S32, S42],
Col3 = [S13, S23, S33, S43],
Col4 = [S14, S24, S34, S44],

Square1 = [S11, S12, S21, S22],
Square2 = [S13, S14, S23, S24],
Square3 = [S31, S32, S41, S42],
Square4 = [S33, S34, S43, S44],

valid([Row1, Row2, Row3, Row4,
       Col1, Col2, Col3, Col4,
       Square1, Square2, Square3, Square4]).

Единственными частями, которые я (намеренно) изменил, были:

  • , добавив use_module(library(clpfd)). вверху
  • , изменив fd_all_different(Head), на all_different(Head),
  • изменение fd_domain(Puzzle, 1, 4), на Puzzle ins 1..4,

Вот вызов swipl 

?- sudoku([_, _, 2, 3,
           _, _, _, _,
           _, _, _, _,
           3, 4, _, _],
Solution).
Solution = [4, 1, 2, 3, 2, 3, 4, 1, 1|...] ;
false.

Решение является правильным вплоть до его обрезания, и в этот момент пролог, кажется, определяетчто нет решения.Но есть: 

4 1 2 3
2 3 4 1
1 2 3 4
3 4 1 2

Я искал код для поиска опечатки или неуместного столбца, но не смог найти источник этого.Есть идеи?

Ответы [ 2 ]

4 голосов
/ 11 апреля 2011

Мне кажется, что вы полагаетесь на отображение по умолчанию в SWI-Prolog, чтобы написать список, представляющий решение, и особенность SWI-Prolog заключается в том, что он не печатает все записи длинного списка в этомслучай, заменив хвост после девяти предметов на «многоточие» ...

Вы наткнулись на это, когда добавили write(Puzzle) к цели и таким образом увидели весь список.Сайт SWI-Prolog содержит часто задаваемые вопросы об этой «аббревиатуре» списков .

2 голосов
/ 11 апреля 2011

Вы сами набрали ;, не так ли? ; просит больше решений. Поскольку вы не использовали labeling для переменных, Prolog только ограничивает их, фактически не генерируя полное решение (для получения нескольких значений выполняется некоторое распространение ограничения ). Есть только один способ наложить ограничения, поэтому второго решения нет. Если вы поставите вызов на labeling в конце предложения sudoku, вы можете переключаться между решениями.

(PS .: sudoku не нужно два аргумента, поскольку вы объединяете их с помощью Solution = Puzzle.)

...