Возвращение к списку в стиле кроссворда

Question

Я создаю программу, которая возьмет список слов и квадратную сетку пробелов в стиле кроссвордов и вернет единственное решение - заполненный кроссворд, так что все слова будут согласованно соединяться. Размер сетки произвольный, но это всегда квадрат.

Смотрите здесь пример того, что я пытаюсь сделать: http://en.wikipedia.org/wiki/Fill-In_(puzzle)

У меня есть мясо программы вниз. По сути, мой первый набор предикатов берет сетку и создает логические переменные для каждого слота, игнорируя затемненные слоты (#). Затем я создаю список возможных слов длиной более 1 слота (слова длиной в одну букву недопустимы). В результате получается сетка с формой (очень простой пример):

#_#
___
#_#

Где каждая строка является элементом "списка загадок" сверху вниз, т.е.

  Row 1   Row 2   Row 3
[[#,_,#],[_,_,_],[#,_,#]]

Будут заполнены свободными логическими переменными так:

#X#
ABC
#Z#

И список будет выглядеть так (часть 0):

[[#,X,#],[A,B,C],[#,Z,#]]

Затем список слов в форме:

[['M','E','N'],['N','E','W']]

Дается с конечным решением

#M#
NEW
#N#

До сих пор я заполняю список сетки переменными, как в части 0, а также заполняю список возможными слотами для слов, которые нужно ввести ("список слотов"), где слот создается для каждой строки вертикальных и горизонтальных пробелов длиннее, чем 1 пробел в длине (для этого примера):

[[A,B,C],[X,B,Z]]

Поэтому я успешно настроил их так, что объединение слова в слот из списка слотов также объединит это слово с соответствующими переменными в списке головоломок.

Теперь все входные данные будут такими, что всегда есть только один способ упорядочить слова в сетке (в отличие от этого примера, где есть два способа, просто игнорируйте это), поэтому только одно решение будет предоставлено завершенной программой (решение является заполненной сеткой головоломки).

Алгоритм объединения слов должен быть:

1. Take a word from the word list
2. Go through the slot list and unify with the first slot that succeeds
3. If there are no successful bindings, fail and backtrack to try a new 
   set of unifications
4. Keep failing and backtracking until a solution is found such that all 
   words bind successfully

Мой код для этого объединения слов в слоты ниже:

%%% Takes a word (W) and a list of slots (S|Ss) and attempts to bind it to a slot
bind_word(W,[S|Ss],Slots):- bind_w(W,[S|Ss],[],Slots).
bind_w(_,[],Acc,Acc).
bind_w(W,[S|Ss],Acc,Slots):-
(   W = S ->                    % Does the word bind to the next slot?
    append(Acc,[S],Acc1),       % YES Add the bound slot to the accumulator 
    append(Acc1,Ss,Acc2),       % Add the rest of the slots to the accumulator
    bind_w(_,[],Acc2,Slots)     % Exit with success
;   length(Ss,0) -> fail        % NO Word doesn't bind, if there are no slots left to bind then this has failed
;   append(Acc,[S],Acc1),       % NO Word doesn't bind, but there are slots left, append this unbound slot to the accumulator
    bind_w(W,Ss,Acc1,Slots)     % Move to the next slot
).
%%%

То, что я хочу сделать, это если он ударит

length(Ss,0) -> fail

затем вернитесь к началу и попробуйте снова, но вместо того, чтобы повторить попытку с теми же привязками, рассмотрите успешные привязки как сбои и пропустите их, например:

1. Try to bind the word B,E,N to the first slot, and it works
2. Try to bind the word M,A,X to the second slot, and it doesn't 
   work and there are no slots left
3. Backtrack to (1), and instead of binding BEN to slot one (which 
   succeeded before), skip to the next slot and try unifying BEN to 
   the second slot.

К сожалению, когда он попадает

length(Ss,0) -> fail

он рассматривает все это как неудачу и не возвращается, но все терпит неудачу. Решающий предикат выглядит следующим образом:

%%% Takes a puzzle grid and a wordlist and solves the puzzle
solve_puzzle(Solution, [], Solution).
solve_puzzle(Puzzle, Wordlist, Solved):-
    fill_slots_H(Puzzle,Slots1,Puzzle1),        % Fill out the puzzle with logical variables in every blank space (results = Puzzle1), also get all the horizontal word slots (results = Slots1) 
    flip(Puzzle1,0,Puzzle1_Flipped),            % Flip the puzzle for vertical use (results = Puzzle1_Flipped)
    fill_slots_V(Puzzle1_Flipped,Slots1,Slots), % Take the vertical puzzle and append the slots for vertical words onto the end of the existing slot list SLOTS IS THE FINAL UNBOUND SLOT LIST
    flip(Puzzle1_Flipped,1,Puzzle_Final),       % Flip the puzzle back to normal PUZZLE_FINAL IS THE FINAL UNBOUND PUZZLE
    !,                                          % Make these choices final
    insert_words(Wordlist,Slots,Final_Slotlist),% Insert all the words into the slots and return the finished slot list 
    Slots = Final_Slotlist,                     % Bind all logical variables in the final slotlist to the slotlist linked to the puzzle
    solve_puzzle(Puzzle_Final, [], Solved).     % Puzzle is now filled, return it as the solution
%%%

%%% Takes a (W)ordlist, and (S)lot list and binds every word to a slot until the puzzle is finished
insert_words([],Slots,Slots).
insert_words([W|Ws], Current_Slotlist, Filled_Slotlist):- 
    bind_word(W,Current_Slotlist,Partial_Slotlist),
    insert_words(Ws, Partial_Slotlist, Filled_Slotlist).
%%%

Я заполняю головоломку, получаю список горизонтальных слотов для слов, затем переставляю головоломку и получаю список вертикальных слотов для слов (добавляя их к горизонтальному). Затем я заполняю список слотов словами, объединяю заполненный список с пустым списком слотов (который также объединяет слова в сетку головоломки), затем возвращаю готовую головоломку.

Как мне сделать так, чтобы, если ему не удалось объединить слово, он отслеживал и пропускал любые успехи и пробовал другой выбор? Я думал о попытке связать, тогда, если это не удастся, рандомизируйте список слов и попробуйте снова, но это не звучит очень логично для меня...

Заранее спасибо.

Answer 1

Вы слишком много думали об алгоритме поиска и слишком мало о логическом значении вашей программы. В Прологе вы должны сделать и то и другое, и это может занять некоторое время, чтобы найти правильный баланс.

Если я вас правильно понимаю, все, что вам нужно, это взять одно слово за другим, попытаться вставить его в слот и вернуться назад в хронологическом порядке. Это легко в Прологе. Чтобы сделать что-то для всех слов в списке слов, вы используете рекурсию. Чтобы попробовать слоты в списке слотов, вы используете member/2. Откат происходит автоматически:

solve(Ss) :-
    Ws=[[b,e,g],[w,e,b],[n,e,w],[b,e,n]],
    Ss=[[A,B,C],[D,B,F],[F,H,I],[C,H,L]],
    all_member(Ws, Ss).

all_member([], _).
all_member([W|Ws], Ss) :-
    member(W, Ss),
    all_member(Ws, Ss).

?- solve(Ss).
Ss = [[b, e, n], [w, e, b], [b, e, g], [n, e, w]]
Yes (0.00s cpu, solution 1, maybe more)
Ss = [[w, e, b], [b, e, n], [n, e, w], [b, e, g]]
Yes (0.00s cpu, solution 2, maybe more)
No (0.01s cpu)

[Я предположил, что все слова в списке слов разные]

PS: После того, как вы исправили bind_w/4, заменив if-then-else дизъюнкцией, он по сути становится сложной версией member/2. Вам не нужна пара аккумуляторов и добавлений, потому что все, что они делают - это создают копию списка слотов (который вам не нужен, просто используйте оригинальный). Вам также не нужно первое предложение bind_w/4, потому что вы хотите, чтобы оно завершалось с пустым списком слотов. Как только вы удалите это, вам больше не нужно проверять длину.

Answer 2

Я на самом деле понял это. Я не знал, что if-A-then-B-else-C отбрасывает какие-либо точки выбора в Прологе, поэтому все перестановки A не исследовались, так как if-then-else отбрасывает все другие перестановки. Вынимаем if-then-else из bind_w и заменяем его на:

must be slots remaining,
unify word ; unify next slot.

работал, так как есть условие сбоя (количество слотов остается> 0) и точка выбора (объединить слово с текущим слотом или объединить со следующим слотом). Если условие сбоя достигнуто, то Prolog откатится назад и попробует другую ветку.