追溯纵横字谜拼图中的列表

Question

我正在创建一个程序，它将采用单词列表以及方格，纵横填字格式的空格网格，并返回唯一的解决方案，即填充填字游戏，使所有言语融贯一致。网格的大小是任意的，但它总是一个正方形。

在这里看到的是什么，我试图做一个例子： 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]] 

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

现在，所有的输入将是这样的，总是只有一种方法来安排网格中的单词（不像这个例子中有两种方式，只是忽略），所以只有一个解决方案将由完成的程序（解决方案是填充的拼图网格）。

字，统一的算法应该是：

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 ，它基本上变成了成员/ 2的复杂版本。你不需要累加器对和追加，因为他们所做的只是构造一个槽列表副本（你不需要，只需要使用原来的副本）。您也不需要bind_w/4的第一个子句，因为您希望它以空插槽列表失败。一旦你删除了这个，你就不再需要长度测试了。

Answer 2

我其实已经想通了。我不知道如果-A-then-B-else-C在Prolog中抛出任何选择点，所以A的所有排列都没有被探索，因为if-then-else抛出所有其他排列。取出如果 - 则 - 否则从bind_w并用替换它：

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

工作，因为有（时隙剩余> 0）失败状态和一个选择点（统一字与当前时隙，或与统一下一个插槽）。如果失败情况被击中，则Prolog将回溯并尝试不同的分支。