PROLOG中的纵横字谜求解器

Question

天堂岛的克里奥尔语有14个单词：“抛弃”、“鲍鱼”、"anagram“、”船“、”船“、”孩子“、”连接“、”优雅“、”增强“、”岛“、”男人“、”沙“、”太阳“和”女人“。

“天堂时报”()发表了这个填字游戏：

​

​

填字游戏包含14个单词中的一些，但没有其他单词。

编写Prolog程序，该程序从

word(X) :-
member(X,
[
[a,b,a,n,d,o,n], [a,b,a,l,o,n,e], [a,n,a,g,r,a,m],
[b,o,a,t], [b,o,a,t,m,a,n], [c,h,i,l,d],
[c,o,n,n,e,c,t], [e,l,e,g,a,n,t], [e,n,h,a,n,c,e],
[i,s,l,a,n,d], [m, a, n], [s,a,n,d],
[s,u,n], [w, o, m, a, n]
]).

solution(H1,H2,H3,V1,V2,V3) :-

定义谓词solution的方式是：

solution(H1,H2,H3,V1,V2,V3)

当且仅当H1、H2、H3、V1、V2和V3是天堂岛的有效单词时才成立，这些字在写入上面给出的网格时会形成有效的填字游戏。(例如，H1的第二个字母应该与V1的第二个字母重合。)

使用查询

?- solution(H1,H2,H3,V1,V2,V3).

解决填字游戏。找到填字游戏的所有解决方案。

提示:你可能想从一个较小的纵横字谜和一个不那么丰富的词汇开始。

Answer 1

只要看一看图片，文字都是用字母写的，你在图片中有所有东西，用Prolog行来解读它(我的解决方案有12行，2行为一个字)。

编辑每个人都给出了自己的解决方案，这里是我的：

solution(H1,H2,H3,V1,V2,V3) :-
    H1 = [_,A2,_,A4,_,A6,_],
    H2 = [_,B2,_,B4,_,B6,_],
    H3 = [_,C2,_,C4,_,C6,_],
    V1 = [_,A2,_,B2,_,C2,_],
    V2 = [_,A4,_,B4,_,C4,_],
    V3 = [_,A6,_,B6,_,C6,_],
    maplist(word, [H1,H2,H3,V1,V2,V3]).

我最初写的单词(H1)，单词(H2).

Answer 2

唯一域--选择select/2可以完成以下任务：

select([A|As],S):- select(A,S,S1),select(As,S1).
select([],_). 
words(X) :- X = [
    [a,b,a,n,d,o,n], [a,b,a,l,o,n,e], [a,n,a,g,r,a,m],
    [b,o,a,t],       [b,o,a,t,m,a,n], [c,h,i,l,d],
    [c,o,n,n,e,c,t], [e,l,e,g,a,n,t], [e,n,h,a,n,c,e],
    [i,s,l,a,n,d],   [m, a, n],       [s,a,n,d],
    [s,u,n],         [w, o, m, a, n]
    ].
solve(Crossword):- words(Words), 
    Crossword = [ [_,A2,_,A4,_,A6,_],
                  [_,B2,_,B4,_,B6,_],
                  [_,C2,_,C4,_,C6,_],
                  [_,A2,_,B2,_,C2,_],
                  [_,A4,_,B4,_,C4,_],
                  [_,A6,_,B6,_,C6,_] ],
    select(Crossword, Words).
solve:- solve(Crossword),
        maplist(writeln, Crossword), writeln(';'), fail 
     ;  writeln('No more solutions!').

测试：

7 ?- solve.
[a, b, a, n, d, o, n]
[e, l, e, g, a, n, t]
[e, n, h, a, n, c, e]
[a, b, a, l, o, n, e]
[a, n, a, g, r, a, m]
[c, o, n, n, e, c, t]
;
[a, b, a, l, o, n, e]
[a, n, a, g, r, a, m]
[c, o, n, n, e, c, t]
[a, b, a, n, d, o, n]
[e, l, e, g, a, n, t]
[e, n, h, a, n, c, e]
;
No more solutions!

此解决方案只允许在拼图中使用唯一的单词(不允许重复)。这可能是你想要的，也可能不是。

Answer 3

不是Prolog程序本身，而是使用约束逻辑编程的解决方案可以在哈坎·凯勒斯特兰关于CP的优秀博客中找到。它是在ECLiPSe，但很容易适应其他Prolog系统的有限域求解器。使用CLP代替纯Prolog将使搜索速度更快。