强制Prolog选择唯一变量的值

Question

强制Prolog选择唯一变量的值

8

好的，我是一名新手，对Prolog不熟悉，所以如果我的问题很简单，请原谅，但我似乎找不到一个恰当而优美的答案。我正在尝试解决这个练习，它在learnprolognow.org上，练习2.4（填字游戏）。

该练习提供了以下事实：

   word(astante,  a,s,t,a,n,t,e). 
   word(astoria,  a,s,t,o,r,i,a). 
   word(baratto,  b,a,r,a,t,t,o). 
   word(cobalto,  c,o,b,a,l,t,o). 
   word(pistola,  p,i,s,t,o,l,a). 
   word(statale,  s,t,a,t,a,l,e).

我想到的解决方案，用于解决每个单词的填写位置问题是：

crossword(V1, V2, V3, H1, H2, H3) :-
   word(V1, V1a, V1bH1b, V1c, V1dH2b, V1e, V1fH3b, V1g), 
   word(V2, V2a, V2bH1d, V2c, V2dH2d, V2e, V2fH3d, V2g), 
   word(V3, V3a, V3bH1f, V3c, V3dH2f, V3e, V3fH3f, V3g), 
   word(H1, H1a, V1bH1b, H1c, V2bH1d, H1e, V3bH1f, H1g), 
   word(H2, H2a, V1dH2b, H2c, V2dH2d, H2e, V3dH2f, H2g), 
   word(H3, H3a, V1fH3b, H3c, V2fH3d, H3e, V3fH3f, H3g).

将每个单词的字符用V1a、V1b直至V1g表示，而V1bH1b到V3fH3f则表示填字游戏中不同单词之间的共同字符。

该解决方案似乎有效，但结果会产生重复值，第一个结果如下：

?- crossword(V1, V2, V3, H1, H2, H3).
V1 = astante,
V2 = baratto,
V3 = statale,
H1 = astante,
H2 = baratto,
H3 = statale .

我该如何强制 Prolog 满足 V1 \= V2 \= V3 \= H1 \= H2 \= H3 ？如果我一个一个地做，需要进行 120 种排列组合，所以一定有更快的方法。由于这是初学者练习，我必须遗漏了什么。我发现了这个类似的问题，但提供的答案看起来很复杂，我希望能有更简单的方法。我在 Ubuntu 上使用 swi-prolog，以防有影响。谢谢。

- jbx

1

dif(V1,V2) 等等 maplist(dif(V1),[V2,V3,V3]) - false

但是 div(V1, V2) 不等同于 V1 = V2，所以我仍然需要执行 120 次来确保这 6 个变量不相同吗？！ - jbx

1

请注意，dif/2 是不同于其他的谓词。使用 maplist 可以进一步简化代码。为了更进一步简化，请定义一个辅助谓词 alldif/1，如果列表中所有元素都不同，则该谓词返回 true。 - false

好的，那我该怎么做呢？请记住我还是一个刚开始学习的初学者，所以不要假设我能填写“等等”或“在此插入更多”。 - jbx

1

如果你在编程方面还处于很早的阶段，请不要试图跳过前面的步骤；一步一步地解决问题。刚开始时，你可能需要打出更加冗长的解决方案，这并没有关系。当你到达更高级的阶段时，你会更好地理解这个道理。 - Will Ness

3个回答

0

无论是@false在评论中告诉你的内容，还是我喜欢使用域名选择：

selectM([A|As],S,Z):- select(A,S,S1),selectM(As,S1,Z).
selectM([],Z,Z).

word(astante,  [a,s,t,a,n,t,e]). 
word(astoria,  [a,s,t,o,r,i,a]). 
word(baratto,  [b,a,r,a,t,t,o]). 
word(cobalto,  [c,o,b,a,l,t,o]). 
word(pistola,  [p,i,s,t,o,l,a]). 
word(statale,  [s,t,a,t,a,l,e]).

crossword(Words) :- findall(W, word(_,W), WS),
   Words = [[ _,A,_,B,_,C,_], 
            [ _,D,_,E,_,F,_], 
            [ _,G,_,H,_,I,_],
            [ _,A,_,D,_,G,_],
            [ _,B,_,E,_,H,_],
            [ _,C,_,F,_,I,_]],
   selectM( Words, WS, _).

- Will Ness

谢谢，你的方法看起来很优雅。但是你修改了练习中给出的事实列表？ - jbx

@jbx 是的，我做了。 :) 如果你不被允许这样做，那么你可以将一个转换为另一个：wordL(W):- word(_, A,B,C,D,E,F,G), W=[ 在此处插入更多 ].。然后你可以在调用findall时使用wordL代替word。 - Will Ness

好吧，不是我不被允许，而是这就是练习的方式，我正在尝试慢慢学习。插入更多内容会有什么？ - jbx

@jbx 我留给你解决。 :) 比如，对于 word(day, d, a, y) ，我们想要 W=[d,a,y]，是吗？如果你现在觉得很难，可能最好先学习一些Prolog的介绍。 - Will Ness

是的，那正是重点。这个练习是learnprolognow.org的第二章（第一章只是解释原子、简单术语等）。我在问题中明确说明了这一点，表明我是一个初学者，所以目前很难弥合差距。但还是谢谢你的答案。 - jbx

@jbx 让我们再试一次。我们使用 word(day, d, a, y) 和 word(_,A,B,C), W=[A,B,C] 将其转换为 [d,a,y]。或者如果我们有一个事实 word(month, m,o,n,t,h)，我们可以使用 word(_,A,B,C,D,E),W=[A,B,C,D,E] 进行转换。这里我们只有7个字母的单词。这有帮助吗？ - Will Ness

0

length(List, N): N 是列表的长度
sort(List, SortedList): SortedList 是 List 的排序版本（重复元素已被删除）

另一方面，如果有一个可用单词列表，并在使用一个单词时将其删除，可能会更快；不仅您不必在最后进行检查，而且还可以避免无意义的实例化（A1 = foo，A2 = foo 将立即停止而不是在最后被拒绝）。换句话说，这是分支修剪。

- Thanos Tintinidis

谢谢，但您能详细说明一下如何使用练习提供的事实来最终实现 crossword(V1, V2, V3, H1, H2, H3) 并确保它们各不相同吗？这就是这个练习的重点。 - jbx

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- false · Accepted Answer

使用如下定义的 alldif/1 ：

alldif([]).
alldif([E|Es]) :-
   maplist(dif(E), Es),
   alldif(Es).

甚至可以用于最一般的查询：

?- alldif(Es).
   Es = []
;  Es = [_A]
;  Es = [_A,_B], dif(_A,_B)
;  Es = [_A,_B,_C],
   dif(_A,_B), dif(_A,_C),
   dif(_B,_C)
;  Es = [_A,_B,_C,_D],
   dif(_A,_B), dif(_A,_C), dif(_A,_D),
   dif(_B,_C), dif(_B,_D),
   dif(_C,_D)
;  ... .

目标 maplist(dif(E),Es) 的含义最好通过查看答案来理解：

?- maplist(dif(E),Es).
   Es = []
;  Es = [_A], dif(E,_A)
;  Es = [_A,_B], dif(E,_A), dif(E,_B)
;  Es = [_A,_B,_C], dif(E,_A), dif(E,_B), dif(E,_C)
;  ... .

换言之，Es 是一个元素列表，这些元素都与 E 不同。目标是使用maplist(dif(E),[A,B,C])函数将第一个元素（在本例中为dif(E)）与列表中的每个元素组合起来。因此，有dif(E,A), dif(E,B), dif(E,C)。