在填字游戏中回溯列表

Question

我正在创建一个程序，该程序将接受一个单词列表和一个方形填字游戏风格的空格网格，并返回唯一的解决方案，即填充的填字游戏，以便所有单词连贯地放在一起。网格的大小是任意的，但它总是一个正方形。

请参阅此处以获取我尝试执行的操作示例：http://en.wikipedia.org/wiki/Fill-In_（谜题）

我已经把程序的要点记下来了。从本质上讲，我的第一组谓词采用网格并为每个槽创建逻辑变量，忽略被涂黑的槽（#）。然后，我创建了一个可能的单词列表，这些单词的长度大于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

您对搜索算法考虑得太多了，对程序的逻辑意义考虑得太少了。在Prolog中，你必须同时做到这两件事，并且可能需要一段时间才能找到正确的平衡。

如果我理解正确的话，你只需要把一个词接一个词，试着把它放进一个槽里，然后按时间顺序回溯。这在Prolog中很容易。要对单词列表中的所有单词执行某些操作，可以使用递归。要尝试插槽列表中的插槽，请使用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：一旦您通过用析取替换if-then-else来更正bind_w/4，它本质上就变成了member/2的复杂版本。您不需要累加器对和追加，因为它们所做的只是构造插槽列表的副本（您不需要，只需使用原始列表）。您也不需要bind_w/4的第一个子句，因为您希望它在空槽列表中失败。一旦你去掉这个，你就不再需要长度测试了。

Answer 2

我真的想明白了。我不知道if-A-then-B-else-C在Prolog中抛出了任何选择点，所以没有探索A的所有排列，就像if-then-else抛出了所有其他排列一样。从bind_w中取出if-then-else，并将其替换为：

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

有效，因为存在失败条件（插槽剩余>0）和选择点（将字与当前插槽统一，或与下一个插槽统一）。如果遇到失败条件，那么Prolog将回溯并尝试不同的分支。