Dobble Cards Prolog

Question

I'm learning about list operations in Prolog. I thought computing a Dobble card set would be a fun exercise.

The card game Dobble (aka Spot It!) has 55 cards. There are 57 symbols. Each card has 8 different symbols. Any two cards have exactly one symbol in common.

I am using lists and numbers to represent the cards and symbols in Prolog. I wrote the predicates isCard\1 and oneMatch\2 to define what cards look like, and that two cards have exactly one symbol in common. I'm stuck at putting it together in isDobble\1. Prolog seems to calculate forever, and throws stack overflow errors. Your advice is greatly appreciated!!

My goal is to query "isDobble(X)." and magically :) receive a valid Dobble card set.


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!

Algorithm hints at https://stackoverflow.com/a/52846660/ – brebs Sep 06 '22 at 22:57 — brebs, Sep 06 '22 at 22:57

score 3 · Answer 1 · answered Sep 07 '22 at 07:08

Suppose you would have more than 2^225 of elementary computations free. Or say 2^2^225. Would this really solve the problem? Before going into any further detail and wasting one solar system after the other, I looked at a tiny part of your program, a 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]
;  ... .

By exchanging the last two goals you could solve this somewhat. That is, you would have a terminating program, but one with a lot of solutions.

With clpz/clpfd you can collapse that large search space into a single answer:

:- 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).

That is, with a single answer, you can represent all solutions compactly.

score 0 · Answer 2 · answered Sep 06 '22 at 23:48

Prolog seems to calculate forever

Indeed!

From ?- help(permutation). in SWI Prolog:

Note that a list of length N has N! permutations, and unbounded permutation generation becomes prohibitively expensive, even for rather short lists (10! = 3,628,800).

length(D, 55)
permutation(D, [DHead|DTail])

Has 55! loops to work through, which is

12696403353658275925965100847566516959580321051449436762275840000000000000

approximately 2²⁴³. Thomas Pornin's answer about breaking encryption estimates:

the total mass of the Solar system, if converted in its entirety to energy [...] implies a hard limit of about 6.32×10⁶⁸ elementary computations, which is about 2^^225.2

and that's 18 doublings less than you need; if you could perfectly efficiently use twenty entire Suns on a perfectly efficient computer, you would still need more energy because backtracking and list unification are not an elementary computations, and you have two more permutations still to do.

My goal is to query "isDobble(X)." and magically :) receive a valid Dobble card set.

But then if your goal is magic, you may need some darker arts to cut through such a large search space; e.g. clpfd, but I suspect it would help more to understand this math of the finite projective planes behind Dobble, links to this explanation and then code one and walk through it generating the cards. That links to Python - Spot it! Cards and What are the mathematical/computational principles behind this game? as well as @brebs' link to Spot it algorithm - js from their comment.

brebs · Answer 3 · 2022-09-07T20:26:53.607

Can get part of the way (22 cards instead of 55), using clpBNR:

:- use_module(library(clpBNR)).
% Provide roughly 3.5GB RAM
:- set_prolog_flag(stack_limit, 3_647_483_648).

cards(Cards) :-
    % Should be 55
    length(Cards, 22),
    cards_(Cards, [], 1),
    enumerate(Cards).

cards_([], _, _).
cards_([Card|T], Upto, CardNum) :-
    length(Card, 8),
    % Seems efficient to order the numbers in each card
    ascending_distinct_bnr(Card),
    Card::integer(0, 56),
    count_matches(Upto, Card),
    CardNum1 is CardNum + 1,
    cards_(T, [Card|Upto], CardNum1).

% Match the new card with 1 symbol on the other cards
count_matches([], _).
count_matches([H|T], Card) :-
    count_matches_lists_bnr(H, Card, 1),
    count_matches(T, Card).

count_matches_lists_bnr([], _, 0).
count_matches_lists_bnr([H|T], L, Matches) :-
    [Matches, Matches0]::integer(0, _),
    count_matches_bnr(L, H, MatchesL),
    {Matches == Matches0 + MatchesL},
    count_matches_lists_bnr(T, L, Matches0).

count_matches_bnr([], _, 0).
count_matches_bnr([H|T], E, Matches) :-
    [Matches, Matches0]::integer(0, _),
    % (H == E) is Boolean, 1 (true) or 0
    {Matches == Matches0 + (H == E)},
    count_matches_bnr(T, E, Matches0).

ascending_distinct_bnr([H|T]) :-
    [H|T]::integer,
    ascending_distinct_bnr_(T, H).

ascending_distinct_bnr_([], _).
ascending_distinct_bnr_([H|T], Prev) :-
    {H > Prev},
    ascending_distinct_bnr_(T, H).

Result in swi-prolog:

% 23,849,152 inferences, 2.880 CPU in 2.886 seconds (100% CPU, 8280501 Lips)
C = [[0,1,2,3,4,5,6,7],[0,8,9,10,11,12,13,14],[0,15,16,17,18,19,20,21],[0,22,23,24,25,26,27,28],[0,29,30,31,32,33,34,35],[0,36,37,38,39,40,41,42],[0,43,44,45,46,47,48,49],[0,50,51,52,53,54,55,56],[1,8,15,22,29,36,43,50],[1,9,16,23,30,37,44,51],[1,10,17,24,31,38,45,52],[1,11,18,25,32,39,46,53],[1,12,19,26,33,40,47,54],[1,13,20,27,34,41,48,55],[1,14,21,28,35,42,49,56],[2,8,16,24,32,40,48,56],[2,9,15,25,31,41,49,54],[2,10,18,22,30,42,47,55],[2,11,19,27,35,36,44,52],[2,12,17,28,34,37,43,53],[2,13,21,23,33,38,46,50],[2,14,20,26,29,39,45,51]] ;

This could of course be converted to use clpfd.

I added CardNum for future usage.

I found salvi site which links to code, and its third (small) Prolog program results in:

?- time(dobble(8, C)).
% 4,862 inferences, 0.001 CPU in 0.001 seconds (99% CPU, 5412536 Lips)
C = [[0,1,2,3,4,5,6,7],[0,8,9,10,11,12,13,14],[0,15,16,17,18,19,20,21],[0,22,23,24,25,26,27,28],[0,29,30,31,32,33,34,35],[0,36,37,38,39,40,41,42],[0,43,44,45,46,47,48,49],[0,50,51,52,53,54,55,56],[1,8,15,22,29,36,43,50],[1,9,16,23,30,37,44,51],[1,10,17,24,31,38,45,52],[1,11,18,25,32,39,46,53],[1,12,19,26,33,40,47,54],[1,13,20,27,34,41,48,55],[1,14,21,28,35,42,49,56],[2,8,16,24,32,40,48,56],[2,9,17,25,33,41,49,50],[2,10,18,26,34,42,43,51],[2,11,19,27,35,36,44,52],[2,12,20,28,29,37,45,53],[2,13,21,22,30,38,46,54],[2,14,15,23,31,39,47,55],[3,8,17,26,35,37,46,55],[3,9,18,27,29,38,47,56],[3,10,19,28,30,39,48,50],[3,11,20,22,31,40,49,51],[3,12,21,23,32,41,43,52],[3,13,15,24,33,42,44,53],[3,14,16,25,34,36,45,54],[4,8,18,28,31,41,44,54],[4,9,19,22,32,42,45,55],[4,10,20,23,33,36,46,56],[4,11,21,24,34,37,47,50],[4,12,15,25,35,38,48,51],[4,13,16,26,29,39,49,52],[4,14,17,27,30,40,43,53],[5,8,19,23,34,38,49,53],[5,9,20,24,35,39,43,54],[5,10,21,25,29,40,44,55],[5,11,15,26,30,41,45,56],[5,12,16,27,31,42,46,50],[5,13,17,28,32,36,47,51],[5,14,18,22,33,37,48,52],[6,8,20,25,30,42,47,52],[6,9,21,26,31,36,48,53],[6,10,15,27,32,37,49,54],[6,11,16,28,33,38,43,55],[6,12,17,22,34,39,44,56],[6,13,18,23,35,40,45,50],[6,14,19,24,29,41,46,51],[7,8,21,27,33,39,45,51],[7,9,15,28,34,40,46,52],[7,10,16,22,35,41,47,53],[7,11,17,23,29,42,48,54],[7,12,18,24,30,36,49,55],[7,13,19,25,31,37,43,56],[7,14,20,26,32,38,44,50]].

The above is 57 cards, so I removed the last 2 cards, and checked it works in my code (by setting Cards in my cards/1 to the 55 8-number lists):

?- time(cards(C)).
% 39,438,078 inferences, 3.855 CPU in 3.860 seconds (100% CPU, 10230841 Lips)

Nice.

@repeat I don't know about better phrasing... find a woke person around you and ask them. — TA_intern, Sep 13 '22 at 12:04
`% Provide roughly 3.5GB RAM` isn't something I would want to write in my code. — repeat, Sep 13 '22 at 16:58
@TA_intern. I'm sorry, there aren't any. I tried again. Hopefully, I wrote something that offends nobody. — repeat, Sep 13 '22 at 17:00

Dobble Cards Prolog

3 Answers3