Пролог - решатель дзигоку - время выполнения
Я новичок в Прологе (как в: я только что сделал главу Пролог на 7 языках за 7 недель), поэтому общие комментарии к любому из приведенного ниже кода очень приветствуются.
Прежде всего: что такое дзигоку? Это похоже на судоку, за исключением того, что вы получаете пустую сетку, и в каждом блоке 3х3 даются неравенства между соседними слотами. Пример здесь: http://krazydad.com/jigoku/books/KD_Jigoku_CH_8_v18.pdf. Вам все еще нужно заполнить сетку так, чтобы каждая строка, столбец и блок содержали числа 1-9.
Я пытался реализовать решатель на основе этого решения судоку: http://programmablelife.blogspot.co.uk/2012/07/prolog-sudoku-solver-explained.html. По причинам отладки я начал с примера 4x4, который работает очень хорошо:
:- use_module(library(clpfd)).
small_jidoku(Rows, RowIneqs, ColIneqs) :-
Rows = [A,B,C,D],
append(Rows, Vs), Vs ins 1..4,
maplist(all_distinct, Rows),
transpose(Rows, Columns),
maplist(all_distinct, Columns),
blocks(A, B), blocks(C,D),
maplist(label, Rows),
fake_check_ineqs(Rows, RowIneqs),
fake_check_ineqs(Columns, ColIneqs),
pretty_print([A,B,C,D]).
blocks([], []).
blocks([A,B|Bs1], [D,E|Bs2]) :-
all_distinct([A,B,D,E]),
blocks(Bs1, Bs2).
fake_check_ineqs([],[]).
fake_check_ineqs([Head|Tail], [Ineq1|TailIneqs]) :-
Head = [A,B,C,D],
atom_chars(Ineq1, [X1,X2]),
call(X1, A, B),
call(X2, C, D),
fake_check_ineqs(Tail, TailIneqs).
pretty_print([]).
pretty_print([Head | Tail]) :-
print(Head),
print('\n'),
pretty_print(Tail).
Затем я решаю следующий пример:
time(small_jidoku([[A1,A2,A3,A4],[B1,B2,B3,B4],[C1,C2,C3,C4],[D1,D2,D3,D4]],[><,<>,<<,<<],[><,<<,<>,>>])).
Это работает примерно за 0,5 секунды. Тем не менее, я также пытался решить это с
time(small_jidoku([A,B,C,D],[><,<>,<<,<<],[><,<<,<>,>>])).
и это, кажется, занимает много времени. Может кто-нибудь объяснить, почему решатель занимает гораздо больше времени, когда я не указываю, что каждая строка имеет 4 элемента? Мой наивный ответ на этот вопрос заключается в том, что Пролог, если не сказать фактический формат моих строк, также попытается исследовать меньшие / большие строки, следовательно, тратить время, например, на строки длиной 5, но так ли это на самом деле?
Мой второй вопрос касается версии 9x9, которая очень похожа на версию 4x4, за исключением того, что блоки, конечно, больше и что при проверке неравенств нужно проводить больше испытаний. Код ниже:
:- use_module(library(clpfd)).
jidoku(Rows, RowIneqs, ColIneqs) :-
Rows = [A,B,C,D,E,F,G,H,I],
append(Rows, Vs), Vs ins 1..9,
maplist(all_distinct, Rows),
transpose(Rows, Columns),
maplist(all_distinct, Columns),
blocks(A, B, C), blocks(D, E, F), blocks(G, H, I),
maplist(label, Rows),
check_ineqs(Rows, RowIneqs),
check_ineqs(Columns, ColIneqs),
pretty_print([A,B,C,D,E,F,G,H,I]).
blocks([], [], []).
blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-
all_distinct([A,B,C,D,E,F,G,H,I]),
blocks(Bs1, Bs2, Bs3).
check_ineqs([],[]).
check_ineqs([Head|Tail], [Ineq1|TailIneqs]) :-
Head = [A,B,C,D,E,F,G,H,I],
atom_chars(Ineq1, [X1, X2, X3, X4, X5, X6]),
call(X1, A, B),
call(X2, B, C),
call(X3, D, E),
call(X4, E, F),
call(X5, G, H),
call(X6, H, I),
check_ineqs(Tail, TailIneqs).
Тестовый пример:
time(jidoku([[A1,A2,A3,A4,A5,A6,A7,A8,A9],
[B1,B2,B3,B4,B5,B6,B7,B8,B9],
[C1,C2,C3,C4,C5,C6,C7,C8,C9],
[D1,D2,D3,D4,D5,D6,D7,D8,D9],
[E1,E2,E3,E4,E5,E6,E7,E8,E9],
[F1,F2,F3,F4,F5,F6,F7,F8,F9],
[G1,G2,G3,G4,G5,G6,G7,G8,G9],
[H1,H2,H3,H4,H5,H6,H7,H8,H9],
[I1,I2,I3,I4,I5,I6,I7,I8,I9]],
[<>>><>,<<<>><,<<<><>,<><<><,>>><><,><>><>,<>>><>,<>><><,><<>>>],
[<<<><>,><<>>>,<><<><,><<<>>,><><<<,<><><>,<>>>><,><><><,<>><>>])).
и этот работал всю ночь, не придя к какому-либо заключению, и на данный момент я понятия не имею, что происходит не так. Я ожидал некоторых проблем с масштабированием, но не этой пропорции!
Было бы здорово, если бы кто-то, кто действительно знает, что они делают, мог пролить свет на это! Уже спасибо!
1 ответ
Вот версия вашего кода, которую я имел в виду (другие предикаты остались без изменений):
ineqs(Cells, Ineq) :-
atom_chars(Ineq, Cs),
maplist(primitive_declarative, Cs, Ds),
ineqs_(Ds, Cells).
ineqs_([], _).
ineqs_([Op1,Op2|Ops], [A,B,C|Cells]) :-
call(Op1, A, B),
call(Op2, B, C),
ineqs_(Ops, Cells).
primitive_declarative(<, #<).
primitive_declarative(>, #>).
Обратите внимание, что это не делает общность кодекса справедливым, чтобы назвать предикат " check_... ", потому что предикат утверждает, что имеет место и может использоваться в нескольких направлениях: Да, его можно использовать для проверки того, выполнены ли ограничения, но его также можно использовать для указания того, что ограничения должны выполняться для некоторых переменных. Поэтому я избегаю императивов и использовать больше декларативных имен.
Ты используешь ineqs/2 в jidoku/3 с: maplist(ineqs, Rows, RowsIneqs) и т.п.
Ваш пример и результат с новой версией, используя SWI 7.3.2:
?- length(Rows, 9), maplist(same_length(Rows), Rows),
time(jidoku(Rows,
[<>>><>,<<<>><,<<<><>,<><<><,>>><><,><>><>,<>>><>,<>><><,><<>>>],
[<<<><>,><<>>>,<><<><,><<<>>,><><<<,<><><>,<>>>><,><><><,<>><>>])),
maplist(writeln, Rows).
% 2,745,471 inferences, 0.426 CPU in 0.432 seconds (99% CPU, 6442046 Lips)
[1,5,4,8,7,2,6,9,3]
[2,3,9,1,6,5,7,4,8]
[6,7,8,3,9,4,2,5,1]
[3,4,1,2,5,6,8,7,9]
[9,6,5,7,1,8,3,2,4]
[8,2,7,9,4,3,1,6,5]
[4,9,3,6,2,1,5,8,7]
[7,8,2,5,3,9,4,1,6]
[5,1,6,4,8,7,9,3,2]
Rows = [[1, 5, 4, 8, 7, 2, 6, 9|...], ...].
На самом деле, обратите внимание, что для вычисления уникального решения в данном конкретном случае вообще не требуется никакой маркировки, поскольку решатель ограничений достаточно силен, чтобы свести все домены к одноэлементным наборам.
В вашей предыдущей версии все время было излишне потрачено впустую, наивно создавая перестановки, которые в конечном итоге считались непоследовательными. С новой версией решатель ограничений имеет шанс применить эти знания ранее.
Поэтому рекомендуется сначала указать все ограничения и только потом вызывать labeling/2 искать конкретные решения, как описано в руководстве CLP(FD).