list - Dobble 卡片序言

Question

我正在学习 Prolog 中的列表操作。我认为计算 Dobble 卡片集会是一项有趣的练习。

纸牌游戏 Dobble(又名 Spot It!)有 55 张牌。有 57 个符号。每张卡片有 8 个不同的符号。任意两张牌只有一个相同的符号。

我使用列表和数字来表示 Prolog 中的卡片和符号。我编写了谓词 isCard\1 和 oneMatch\2 来定义卡片的外观，并且两张卡片只有一个相同的符号。我一直坚持将它放在 isDobble\1 中。 Prolog 似乎永远计算，并抛出堆栈溢出错误。非常感谢您的建议!!

我的目标是查询“isDobble(X)”。 并神奇地 :) 收到一套有效的 Dobble 卡片。

isCard(C) :-                            % Card C has the right amount of allowed symbols if..
  length(C, 8),                         % card C has 8 symbols, and
  sublist(C, Sym),                      % symbols are a subset of allowed symbols, and
  findall(S, between(1, 57, S), Sym).   % allowed symbols range from 1 to 57.

oneMatch(A,B) :-                        % Card A and B have exactly one matching Symbol if..
  permutation(A, [AHead|ATail]),        % card A can be permutated, and
  permutation(B, [BHead|BTail]),        % card B can be permutated, such that
  AHead = BHead,                        % the first symbol of card A and B match, while
  ATail \= BTail.                       % any other symbol of card A and B do not match.

isDobble(D) :-                          % It's a Dobble card set D if..
  length(D, 55),                        % the number of cards is 55, and
  permutation(D, [DHead|DTail]),        % any card of the set
  maplist(oneMatch(DHead), DTail),      % matches exactly one symbol of any other card, and
  maplist(isCard, D).                   % any card has the right amount of allowed symbols.

isDobble(X).                            % Show me a Dobble card set X!

Answer 1

假设您有超过 2^225 的免费基本计算。或者说 2^2^225。这真的能解决问题吗？在进入任何进一步的细节并一个接一个地浪费一个太阳系之前，我查看了你程序的一小部分，failure-slice。 :

isCard(C) :-  length(C, 8),  sublist(C, Sym), false,  findall(S, between(1, 57, S), Sym).?- isCard(C).   loops.

This already does not terminate. To see this, take (using that definition for sublist/2):

?- length(C,8), sublist(C,Sym). 
   C = [_A,_B,_C,_D,_E,_F,_G,_H], Sym = [_A,_B,_C,_D,_E,_F,_G,_H]
;  C = [_A,_B,_C,_D,_E,_F,_G,_H], Sym = [_A,_B,_C,_D,_E,_F,_G,_H,_I]
;  C = [_A,_B,_C,_D,_E,_F,_G,_H], Sym = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J]
;  C = [_A,_B,_C,_D,_E,_F,_G,_H], Sym = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K]
;  C = [_A,_B,_C,_D,_E,_F,_G,_H], Sym = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L]
;  C = [_A,_B,_C,_D,_E,_F,_G,_H], Sym = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M]
;  ... .

通过交换最后两个目标，您可以稍微解决这个问题。也就是说，您将有一个终止程序，但有很多解决方案。

使用 clpz/clpfd，您可以将庞大的搜索空间压缩为一个答案:

:- use_module(library(clpz)).

isCard2(C) :-
   length(C, 8),
   C ins 1..57,
   chain(#<, C).

?- isCard2(C).
   C=[_A,_B,_C,_D,_E,_F,_G,_H],
   clpz:(_A#=<_B+ -1), clpz:(_B#=<_C+ -1), clpz:(_C#=<_D+ -1),
   clpz:(_D#=<_E+ -1), clpz:(_E#=<_F+ -1), clpz:(_F#=<_G+ -1),
   clpz:(_G#=<_H+ -1),
   clpz:(_A in 1..50),
   clpz:(_B in 2..51),
   clpz:(_C in 3..52),
   clpz:(_D in 4..53),
   clpz:(_E in 5..54),
   clpz:(_F in 6..55),
   clpz:(_G in 7..56),
   clpz:(_H in 8..57).

也就是说，只需一个答案，您就可以紧凑地表示所有解决方案。