我正面临这个困难的练习，我已经看过其他关于填字游戏的练习（即“p-99：九十九个序言程序”的最后一个练习，或者 Bratko 在“人工智能的序言编程”中报告的那个），但是这个是不同的，更难，因为这里我们没有任何模板要填写。
文字：
编写一个 Prolog 程序来生成一个填字游戏。假设你有一个这样的事实字典：w(Word,Lentgth)。写一个谓词填字游戏（C，W，H）来实例化C，到字典的所有可能的列表（填字游戏行）列表（填字游戏），其中黑色单元格由星号表示。
例子：
w(online,6).
w(prolog,6).
w(perl,5).
w(emacs,5).
w(linux,5).
w(gnu,3).
w(mac,3).
w(nfs,3).
w(sql,3).
w(web,3).
w(xml,3).
w(a,1).
w(b,1).
w(e,1).
w(i,1).
w(l,1).
w(m,1).
w(n,1).
w(o,1).
w(q,1).
w(r,1).
w(s,1).
w(t,1).
w(u,1).
w(w,1).
?- crossword(C,9,6).
C=[[p,r,o,l,o,g,*,*,e],
[e,*,n,*,*,n,*,*,m],
[r,*,l,i,n,u,x,*,a],
[l,*,i,*,f,*,m,a,c],
[*,*,n,*,s,q,l,*,s],
[*,w,e,b,*,*,*,*,*]]
给定提示
1）您可以将这些“黑色”单词添加到字典中：
black(*,1).
black(**,2).
black(***,3).
black(****,4).
black(*****,5).
2）每一行是“白色”词（普通词）和“黑色”词交错的序列，并且该序列可以以两者开始/结束。
3）我建议你用 2 个不同的子句来管理前一点的 2 种可能性。
4）填字游戏是一个字符矩阵，所以它的转置仍然是一个填字游戏。
5）转置填字游戏已经实例化，所以你只需要用字典检查它的可行性。
这就是我想到的：创建一个 H（填字游戏的高度，行）列表（填字游戏的行），对于每个列表（行）我尝试从字典中插入单词，然后是“黑色”单词和然后又是一个词，直到行满，或者同样的东西从一个“黑色”开始。当填字游戏已满时，我将其转置并检查转置是否也是有效的填字游戏：包含的每个单词都是字典中的有效单词。我知道这是一种非常低效的方法，我尝试用一个小字典来生成 2x2 填字游戏，它正确地生成了前两个，但似乎需要数年才能生成第三个。我不知道我的代码是否有问题，也许它卡在某个地方。您是否知道解决此问题的更有效方法，或者您在我的代码中看到了需要改进的地方？
crossword(C,W,H):- create(C,H),
insert_words(C,W,[],_),
clpfd:transpose(C,Traspose),
isok(Traspose).
insert_words([],_,U,U).
insert_words([H|T],W,Uacc,U):-
(add_white(H,[],C,[],Uacc,Udef);
add_black(H,[],C,[],Uacc,Udef)),
insert_words(T,C,Udef,U).
create(Puzzle,H) :- length(Puzzle,H).
add_white(P,P,0,_,U,U).
add_white(P,Row,R,Used,Uacc,Udef):-
R\=0,
w(Word,L),
\+member(Word,Used),
\+member(Word,Uacc),
R2 is R-L,
R2 >= 0,
atom_chars(Word,Word2),
append(Row,Word2,Row2),
append(Used,[Word],Used2),
append(Uacc,[Word],Uacc2),
add_black(P,Row2,R2,Used2,Uacc2,Udef).
add_white(P,Row,R,Used,Uacc,Udef):-
R\=0,
w(Word,L),
\+member(Word,Used),
R2 is R-L,
R2 < 0,
append(Used,[Word],Used2),
add_white(P,Row,R,Used2,Uacc,Udef).
add_white(P,Row,R,Used,Uacc,Udef):-
R\=0,
w(Word,_),
member(Word,Used),
add_white(P,Row,R,Used,Uacc,Udef).
add_black(P,P,0,_,U,U).
add_black(P,Row,R,Used,Uacc,Udef):-
R\=0,
black(Black,L),
R2 is R-L,
R2 >= 0,
atom_chars(Black,Black2),
append(Row,Black2,Row2),
add_white(P,Row2,R2,Used,Uacc,Udef).
add_black(P,Row,R,Used,Uacc,Udef):-
R\=0,
black(_,L),
R2 is R-L,
R2 < 0,
add_black(P,Row,R,Used,Uacc,Udef).
isok([]).
isok([H|T]):-split(H,*,R),
check(R),
isok(T).
split(L,C,R):-split2(L,C,X),trim(X,R).
split2(In, Sep, [Left|Rest]) :-
append(Left, [Sep|Right], In), !, split2(Right, Sep, Rest).
split2(In, _Sep, [In]).
trim([],[]).
trim([H|T],[H|T2]):-H\=[],trim(T,T2).
trim([H|T],Y):-H=[],trim(T,Y).
check([]).
check([H|T]):-
atom_chars(X,H),
w(X,_),
check(T).
我正在使用这本小字典而不是原始字典来测试我的程序并生成简单的 2x2 填字游戏，但正如我之前所说，在正确找到 2 个解决方案后它似乎卡住了。
w(ci,2).
w(ca,2).
w(i,1).
w(a,1).
black(*,1).