0

我正在创建一个程序，它将获取一个单词列表和一个方形的填字游戏样式的空格网格，并返回唯一的解决方案，即填充的填字游戏，使所有单词连贯地组合在一起。网格的大小是任意的，但它始终是正方形。

请参阅此处以获取我正在尝试做的示例： http://en.wikipedia.org/wiki/Fill-In_(puzzle)

我已经把程序的内容放下了。基本上我的第一组谓词采用网格并为每个插槽创建逻辑变量，忽略涂黑的插槽（#s）。然后，我创建了一个大于 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]]

所以我成功地设置了这些，这样将一个单词统一到插槽列表的一个插槽也会将该单词统一到拼图列表中的匹配变量。

现在，所有的输入都会使得在网格中排列单词的方式总是只有一种（不像这个有两种方式的例子，忽略它），所以完成的程序只会提供一个解决方案（a解决方案是填充的拼图网格）。

单词统一算法应该是：

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).
%%%

我填写拼图，获取水平单词槽列表，然后转置拼图并获取垂直单词槽列表（将它们附加到水平单词槽）。然后，我用单词填充槽列表，将填充列表与空槽列表统一（这也将单词统一到拼图网格），然后返回完成的拼图。

如果它无法统一一个单词，我该如何做到这一点，它会回溯并跳过任何成功并尝试另一个选择？我曾想过尝试绑定，然后如果失败，将单词列表随机化并重试，但这对我来说听起来不太符合逻辑......

提前致谢。

4

2 回答 2

3

您对搜索算法考虑得太多，而对程序的逻辑含义考虑得太少。在 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 的第一个子句，因为您希望它以空槽列表失败。一旦你删除它，你就不再需要长度测试了。

于 2014-10-08T23:01:10.473 回答
0

I actually figured it out. I didn't know that if-A-then-B-else-C throws out any choicepoints in Prolog, so all permutations of A were not being explored, as the if-then-else throws out all other permutations. Taking out the if-then-else from bind_w and replacing it with:

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

worked, as there is a fail condition (slots remaining > 0) and a choicepoint (unify word with current slot, or unify with the next slot). If the fail condition is hit, then Prolog will backtrack and try a different branch.

于 2014-10-09T04:47:41.133 回答