Quais são os princípios matemáticos / computacionais por trás deste jogo?

Meus filhos têm esse divertido jogo chamado Spot It! As restrições do jogo (da melhor maneira que posso descrever) são:

• É um baralho de 55 cartas
• Em cada cartão há 8 fotos únicas (ou seja, um cartão não pode ter 2 da mesma foto)
• Dadas quaisquer 2 cartas escolhidas no baralho, há 1 e apenas 1 foto correspondente .
• As imagens correspondentes podem ser dimensionadas de maneira diferente em cartões diferentes, mas isso é apenas para tornar o jogo mais difícil (por exemplo, uma pequena árvore ainda corresponde a uma árvore maior)

O princípio do jogo é: virar duas cartas e quem escolhe a imagem correspondente ganha um ponto.

Aqui está uma foto para esclarecimento:

(Exemplo: você pode ver nas 2 cartas inferiores acima que a imagem correspondente é o dinossauro verde. Entre a imagem inferior direita e a direita do meio, é a cabeça de um palhaço.)

Estou tentando entender o seguinte:

1. Qual é o número mínimo de imagens diferentes necessárias para atender a esses critérios e como você determinaria isso?

2. Usando o pseudocódigo (ou Ruby), como você geraria 55 cartões de jogo a partir de uma matriz de N imagens (onde N é o número mínimo da pergunta 1)?

Atualizar:

As imagens ocorrem mais de duas vezes por baralho (ao contrário do que alguns supuseram). Veja esta figura de 3 cartas, cada uma com um raio:

Geometrias projetivas finitas

Os axiomas da geometria projetiva (plana) são ligeiramente diferentes da geometria euclidiana:

• A cada dois pontos, há exatamente uma linha que passa por eles (é a mesma).
• A cada duas linhas se encontram exatamente em um ponto (isso é um pouco diferente de Euclides).

Agora, adicione "finito" à sopa e você terá a pergunta:

Podemos ter uma geometria com apenas 2 pontos? Com 3 pontos? Com 4? Com 7?

Ainda existem perguntas em aberto sobre esse problema, mas sabemos o seguinte:

• Se houver geometrias com Qpontos, então Q = n^2 + n + 1e né chamado orderde geometria.
• Existem n+1pontos em todas as linhas.
• De todos os pontos, passe exatamente as n+1linhas.

• O número total de linhas também é Q.

• E, finalmente, se né primo, existe uma geometria da ordem n.

O que isso tem a ver com o quebra-cabeça, alguém pode perguntar.

Coloque em cardvez de pointe em picturevez de linee os axiomas se tornam:

• Cada duas cartas têm exatamente uma imagem em comum.
• Para cada duas fotos, há exatamente um cartão que possui as duas.

Agora, vamos pegar n=7e temos a order-7geometria finita com Q = 7^2 + 7 + 1. Isso cria Q=57linhas (imagens) e Q=57pontos (cartões). Eu acho que os criadores de quebra-cabeças decidiram que 55 é um número maior que 57 e deixaram 2 cartas de fora.

Também obtemos n+1 = 8, portanto, de cada ponto (cartão), 8 linhas passam (8 figuras aparecem) e cada linha (imagem) tem 8 pontos (aparece em 8 cartões).

Aqui está uma representação do plano projetivo finito mais famoso (ordem 2) (geometria) com 7 pontos, conhecido como Fano Plane , copiado de Noelle Evans - Página de problemas de geometria finita

Eu estava pensando em criar uma imagem que explicasse como o plano de ordem 2 acima poderia ser transformado em um quebra-cabeça semelhante com 7 cartas e 7 figuras, mas depois um link da questão matemática math.exchange, exatamente como esse diagrama: Dobble-et- la-geometrie-finie

Para aqueles que têm problemas para visualizar a geometria do plano projetivo com 57 pontos, existe uma maneira muito boa e intuitiva de construir o jogo com 57 cartas e 57 símbolos (com base na resposta de Yuval Filmus para esta pergunta ):

1. Para cartões com 8 símbolos, crie uma grade 7x7 de símbolos exclusivos.
2. Adicione 8 símbolos adicionais para as "inclinações" de 0 a 6, mais um para a inclinação infinita.
3. Cada cartão é uma linha na grade (7 símbolos) mais um símbolo da inclinação definida para a inclinação da linha. As linhas têm um deslocamento (ou seja, ponto inicial à esquerda) e uma inclinação (ou seja, quantos símbolos subir para cada passo à direita). Quando a linha deixar a grade na parte superior, digite novamente na parte inferior. Veja esta figura de exemplo (fotos do boardgamegeek ) para dois desses cartões:

No exemplo, pego uma linha com inclinação zero (vermelho) e uma com inclinação 1 (verde). Eles se cruzam exatamente em um ponto comum (a coruja).

Este método garante que quaisquer duas cartas tenham exatamente um símbolo comum, porque

1. Se as inclinações forem diferentes, as linhas sempre se cruzarão exatamente em um ponto.
2. Se as inclinações forem iguais, as linhas não se cruzarão e não haverá símbolo comum na grade. Nesse caso, o símbolo da inclinação será o mesmo.

Dessa forma, podemos construir cartões 7x7 (7 compensações e 7 inclinações).

Também podemos construir sete cartões adicionais a partir de linhas verticais através da grade (ou seja, pegar cada coluna). Para esses, o ícone da inclinação infinita é usado.

Como cada carta consiste em sete símbolos da grade e exatamente um símbolo de "inclinação", podemos criar uma carta adicional, que consiste simplesmente em todos os 8 símbolos de inclinação.

Isso nos deixa com 7x8 + 1 = 57 cartões possíveis e 7 x 7 + 8 = 57 símbolos necessários.

(Naturalmente, isso funciona apenas com uma grade do tamanho de um número primo (por exemplo, n = 7). Caso contrário, as linhas de inclinação diferente podem ter zero ou mais de uma interseção se a inclinação for um divisor do tamanho da grade.)

Portanto, existem k = 55 cartões contendo m = 8 fotos cada, de um total de n fotos. Podemos reafirmar a pergunta 'Quantas figuras n precisamos, para que possamos construir um conjunto de cartões k com apenas uma imagem compartilhada entre qualquer par de cartões?' equivalentemente, perguntando:

Dado um espaço vetorial n- dimensional e o conjunto de todos os vetores, que contêm exatamente m elementos iguais a um e todos os outros zero, qual o tamanho de n deve ser, para que possamos encontrar um conjunto de vetores k , cujos produtos de pontos em pares são tudo igual a 1 ?

Existem exatamente ( n escolha m ) vetores possíveis para construir pares. Então, pelo menos, precisamos de um n grande o suficiente para que ( n escolha m )> = k . Esse é apenas um limite inferior; portanto, para cumprir a restrição de compatibilidade aos pares, é necessário um n muito maior .

Apenas para experimentar um pouco, escrevi um pequeno programa Haskell para calcular conjuntos de cartões válidos:

Edit: Acabei de perceber, depois de ver a solução de Neil e Gajet, que o algoritmo que eu uso nem sempre encontra a melhor solução possível, portanto, tudo abaixo não é necessariamente válido. Vou tentar atualizar meu código em breve.

module Main where

cardCandidates n m = cardCandidates' [] (n-m) m
cardCandidates' buildup  0  0 = [buildup]
cardCandidates' buildup zc oc
    | zc>0 && oc>0 = zerorec ++ onerec
    | zc>0         = zerorec
    | otherwise    = onerec
    where zerorec = cardCandidates' (0:buildup) (zc-1) oc
          onerec  = cardCandidates' (1:buildup) zc (oc-1)

dot x y = sum $ zipWith (*) x y
compatible x y = dot x y == 1

compatibleCards = compatibleCards' []
compatibleCards' valid     [] = valid
compatibleCards' valid (c:cs)
  | all (compatible c) valid = compatibleCards' (c:valid) cs
  |                otherwise = compatibleCards'    valid  cs

legalCardSet n m = compatibleCards $ cardCandidates n m

main = mapM_ print [(n, length $ legalCardSet n m) | n<-[m..]]
  where m = 8

O número máximo resultante de cartões compatíveis para m = 8 fotos por cartão para um número diferente de fotos para escolher n para os primeiros n é assim:

Esse método de força bruta não chega muito longe por causa da explosão combinatória. Mas eu pensei que ainda poderia ser interessante.

Curiosamente, parece que, para m dado k , aumenta com n apenas até um certo n , após o que permanece constante.

Isso significa que, para todo número de fotos por cartão, há um certo número de fotos para escolher, o que resulta no número máximo possível de cartões legais. Adicionar mais fotos para escolher do passado, esse número ideal não aumenta ainda mais o número de cartões legais.

Os primeiros poucos k 's ideais são:

Outros descreveram a estrutura geral do projeto (plano projetivo finito) e mostraram como gerar planos projetivos finitos de ordem primordial. Gostaria apenas de preencher algumas lacunas.

Planos projetivos finitos podem ser gerados para muitos pedidos diferentes, mas são mais diretos no caso de ordem primordial p. Então o módulo inteiro pforma um campo finito que pode ser usado para descrever coordenadas para os pontos e linhas no plano. Existem 3 tipos diferentes de coordenadas para pontos: (1,x,y), (0,1,x)e (0,0,1), onde xe ypode assumir valores de 0a p-1. Os três tipos diferentes de pontos explicam a fórmula p^2+p+1para o número de pontos no sistema. Nós também pode descrever as linhas com os mesmos 3 tipos diferentes de coordenadas [1,x,y], [0,1,x]e [0,0,1].

Calculamos se um ponto e uma linha são incidentes, se o produto escalar de suas coordenadas é igual a 0 mod p. Assim, por exemplo, o ponto (1,2,5)e a linha [0,1,1]são incidentes p=7desde então 1*0+2*1+5*1 = 7 == 0 mod 7, mas o ponto (1,3,3)e a linha [1,2,6]não são incidentes desde então 1*1+3*2+3*6 = 25 != 0 mod 7.

Ao traduzir para o idioma dos cartões e figuras, significa que o cartão com coordenadas (1,2,5)contém a imagem com coordenadas [0,1,1], mas o cartão com coordenadas (1,3,3)não contém a imagem com coordenadas [1,2,6]. Podemos usar este procedimento para desenvolver uma lista completa de cartões e as imagens que eles contêm.

A propósito, acho que é mais fácil pensar em imagens como pontos e cartões como linhas, mas há uma dualidade na geometria projetiva entre pontos e linhas, por isso realmente não importa. No entanto, a seguir, usarei pontos para fotos e linhas para cartões.

A mesma construção funciona para qualquer campo finito. Sabemos que existe um campo finito de ordem, qse e somente se q=p^k, uma potência principal. É chamado o campo GF(p^k)que significa "campo de Galois". Os campos não são tão fáceis de construir no caso de potência principal quanto no caso de potência principal.

Felizmente, o trabalho duro já foi feito e implementado em software livre, o Sage . Para obter um design de plano projetivo da ordem 4, por exemplo, basta digitar

print designs.ProjectiveGeometryDesign(2,1,GF(4,'z'))

e você obterá uma saída que se parece

ProjectiveGeometryDesign<points=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20], blocks=[[0, 1, 2, 3, 20], [0,
4, 8, 12, 16], [0, 5, 10, 15, 19], [0, 6, 11, 13, 17], [0, 7, 9, 14,
18], [1, 4, 11, 14, 19], [1, 5, 9, 13, 16], [1, 6, 8, 15, 18], [1, 7,
10, 12, 17], [2, 4, 9, 15, 17], [2, 5, 11, 12, 18], [2, 6, 10, 14, 16],
[2, 7, 8, 13, 19], [3, 4, 10, 13, 18], [3, 5, 8, 14, 17], [3, 6, 9, 12,
19], [3, 7, 11, 15, 16], [4, 5, 6, 7, 20], [8, 9, 10, 11, 20], [12, 13,
14, 15, 20], [16, 17, 18, 19, 20]]>

Interpreto o exposto da seguinte maneira: existem 21 figuras rotuladas de 0 a 20. Cada um dos blocos (linha na geometria projetiva) me diz quais figuras aparecem em um cartão. Por exemplo, o primeiro cartão terá as figuras 0, 1, 2, 3 e 20; o segundo cartão terá as figuras 0, 4, 8, 12 e 16; e assim por diante.

O sistema da ordem 7 pode ser gerado por

print designs.ProjectiveGeometryDesign(2,1,GF(7)) 

que gera a saída

ProjectiveGeometryDesign<points=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28,
29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46,
47, 48, 49, 50, 51, 52, 53, 54, 55, 56], blocks=[[0, 1, 2, 3, 4, 5, 6,
56], [0, 7, 14, 21, 28, 35, 42, 49], [0, 8, 16, 24, 32, 40, 48, 50], [0,
9, 18, 27, 29, 38, 47, 51], [0, 10, 20, 23, 33, 36, 46, 52], [0, 11, 15,
26, 30, 41, 45, 53], [0, 12, 17, 22, 34, 39, 44, 54], [0, 13, 19, 25,
31, 37, 43, 55], [1, 7, 20, 26, 32, 38, 44, 55], [1, 8, 15, 22, 29, 36,
43, 49], [1, 9, 17, 25, 33, 41, 42, 50], [1, 10, 19, 21, 30, 39, 48,
51], [1, 11, 14, 24, 34, 37, 47, 52], [1, 12, 16, 27, 31, 35, 46, 53],
[1, 13, 18, 23, 28, 40, 45, 54], [2, 7, 19, 24, 29, 41, 46, 54], [2, 8,
14, 27, 33, 39, 45, 55], [2, 9, 16, 23, 30, 37, 44, 49], [2, 10, 18, 26,
34, 35, 43, 50], [2, 11, 20, 22, 31, 40, 42, 51], [2, 12, 15, 25, 28,
38, 48, 52], [2, 13, 17, 21, 32, 36, 47, 53], [3, 7, 18, 22, 33, 37, 48,
53], [3, 8, 20, 25, 30, 35, 47, 54], [3, 9, 15, 21, 34, 40, 46, 55], [3,
10, 17, 24, 31, 38, 45, 49], [3, 11, 19, 27, 28, 36, 44, 50], [3, 12,
14, 23, 32, 41, 43, 51], [3, 13, 16, 26, 29, 39, 42, 52], [4, 7, 17, 27,
30, 40, 43, 52], [4, 8, 19, 23, 34, 38, 42, 53], [4, 9, 14, 26, 31, 36,
48, 54], [4, 10, 16, 22, 28, 41, 47, 55], [4, 11, 18, 25, 32, 39, 46,
49], [4, 12, 20, 21, 29, 37, 45, 50], [4, 13, 15, 24, 33, 35, 44, 51],
[5, 7, 16, 25, 34, 36, 45, 51], [5, 8, 18, 21, 31, 41, 44, 52], [5, 9,
20, 24, 28, 39, 43, 53], [5, 10, 15, 27, 32, 37, 42, 54], [5, 11, 17,
23, 29, 35, 48, 55], [5, 12, 19, 26, 33, 40, 47, 49], [5, 13, 14, 22,
30, 38, 46, 50], [6, 7, 15, 23, 31, 39, 47, 50], [6, 8, 17, 26, 28, 37,
46, 51], [6, 9, 19, 22, 32, 35, 45, 52], [6, 10, 14, 25, 29, 40, 44,
53], [6, 11, 16, 21, 33, 38, 43, 54], [6, 12, 18, 24, 30, 36, 42, 55],
[6, 13, 20, 27, 34, 41, 48, 49], [7, 8, 9, 10, 11, 12, 13, 56], [14, 15,
16, 17, 18, 19, 20, 56], [21, 22, 23, 24, 25, 26, 27, 56], [28, 29, 30,
31, 32, 33, 34, 56], [35, 36, 37, 38, 39, 40, 41, 56], [42, 43, 44, 45,
46, 47, 48, 56], [49, 50, 51, 52, 53, 54, 55, 56]]>

Acabei de encontrar uma maneira de fazer isso com 57 ou 58 fotos, mas agora estou com uma dor de cabeça muito forte; postarei o código ruby ​​em 8 a 10 horas depois de dormir bem! apenas uma sugestão minha solução a cada 7 cartões compartilham a mesma marca e um total de 56 cartões pode ser construído usando a minha solução.

Aqui está o código que gera todos os 57 cartões que o ypercube estava falando. ele usa exatamente 57 imagens e, desculpe, eu escrevi o código C ++ real, mas sabendo que vector <something>é uma matriz que contém valores do tipo something, é fácil entender o que esse código faz. e esse código gera P^2+P+1cartões usando P^2+P+1imagens, cada uma contendo P+1imagem e compartilhando apenas uma imagem em comum, para cada valor P principal. o que significa que podemos ter 7 cartões usando 7 fotos, cada um com 3 fotos (para p = 2), 13 cartões usando 13 fotos (para p = 3), 31 cartões usando 31 fotos (para p = 5), 57 cartões para 57 fotos (para p = 7) e assim por diante ...

#include <iostream>
#include <vector>

using namespace std;

vector <vector<int> > cards;

void createcards(int p)
{
    cards.resize(0);
    for (int i=0;i<p;i++)
    {
        cards.resize(cards.size()+1);
        for(int j=0;j<p;j++)
        {
            cards.back().push_back(i*p+j);
        }
        cards.back().push_back(p*p+1);
    }

    for (int i=0;i<p;i++)
    {
        for(int j=0;j<p;j++)
        {
            cards.resize(cards.size()+1);
            for(int k=0;k<p;k++)
            {
                cards.back().push_back(k*p+(j+i*k)%p);
            }
            cards.back().push_back(p*p+2+i);
        }
    }

    cards.resize(cards.size()+1);

    for (int i=0;i<p+1;i++)
        cards.back().push_back(p*p+1+i);
}

void checkCards()
{
    cout << "---------------------\n";
    for(unsigned i=0;i<cards.size();i++)
    {
        for(unsigned j=0;j<cards[i].size();j++)
        {
            printf("%3d",cards[i][j]);
        }
        cout << "\n";
    }
    cout << "---------------------\n";
    for(unsigned i=0;i<cards.size();i++)
    {
        for(unsigned j=i+1;j<cards.size();j++)
        {
            int sim = 0;
            for(unsigned k=0;k<cards[i].size();k++)
                for(unsigned l=0;l<cards[j].size();l++)
                    if (cards[i][k] == cards[j][l])
                        sim ++;
            if (sim != 1)
                cout << "there is a problem between cards : " << i << " " << j << "\n";

        }
    }
}

int main()
{
    int p;
    for(cin >> p; p!=0;cin>> p)
    {
        createcards(p);
        checkCards();
    }
}

desculpe novamente pelo código atrasado.

Aqui está a solução da Gajet em Python, pois acho o Python mais legível. Eu o modifiquei para que também funcione com números não primos. Usei o Thies insight para gerar um código de exibição mais fácil de entender.

from __future__ import print_function
from itertools import *

def create_cards(p):
    for min_factor in range(2, 1 + int(p ** 0.5)):
        if p % min_factor == 0:
            break
    else:
        min_factor = p
    cards = []
    for i in range(p):
        cards.append(set([i * p + j for j in range(p)] + [p * p]))
    for i in range(min_factor):
        for j in range(p):
            cards.append(set([k * p + (j + i * k) % p
                              for k in range(p)] + [p * p + 1 + i]))

    cards.append(set([p * p + i for i in range(min_factor + 1)]))
    return cards, p * p + p + 1

def display_using_stars(cards, num_pictures):
    for pictures_for_card in cards:
        print("".join('*' if picture in pictures_for_card else ' '
                      for picture in range(num_pictures)))

def check_cards(cards):
    for card, other_card in combinations(cards, 2):
        if len(card & other_card) != 1:
            print("Cards", sorted(card), "and", sorted(other_card),
                  "have intersection", sorted(card & other_card))

cards, num_pictures = create_cards(7)
display_using_stars(cards, num_pictures)
check_cards(cards)

Com saída:

***      *   
   ***   *   
      ****   
*  *  *   *  
 *  *  *  *  
  *  *  * *  
*   *   *  * 
 *   **    * 
  **   *   * 
*    * *    *
 * *    *   *
  * * *     *
         ****

Usando o z3provador de teoremas

Let PSer o número de símbolos por cartão. De acordo com este artigo e ypercubeᵀᴹa resposta, existem N = P**2 - P + 1cartões e símbolos, respectivamente. Um baralho de cartas pode ser representado com sua matriz de incidência, que possui uma linha para cada carta e uma coluna para cada símbolo possível. Seu (i,j)elemento é 1se o cartão itiver um símbolo j. Só precisamos preencher essa matriz com essas restrições em mente:

• cada elemento é zero ou um
• a soma de cada linha é exatamente P
• a soma de cada coluna é exatamente P
• quaisquer duas linhas devem ter exatamente um símbolo em comum

Isso significa N**2variáveis ​​e N**2 + 2*N + (N choose 2)restrições. Parece ser gerenciável em um período não muito longo com z3pequenas entradas.

edit : Infelizmente, P = 8 parece ser muito grande para este método. Eu matei o processo após 14 horas de tempo de computação.

from z3 import *
from itertools import combinations

def is_prime_exponent(K):
    return K > 1 and K not in 6  # next non-prime exponent is 10, 
                                 # but that is too big anyway

def transposed(rows):
    return zip(*rows)

def spotit_z3(symbols_per_card):
    K = symbols_per_card - 1
    N = symbols_per_card ** 2 - symbols_per_card + 1
    if not is_prime_exponent(K):
        raise TypeError("Symbols per card must be a prime exponent plus one.")

    constraints = []

    # the rows of the incidence matrix
    s = N.bit_length()
    rows = [[BitVec("r%dc%d" % (r, c), s) for c in range(N)] for r in range(N)]

    # every element must be either 1 or 0
    constraints += [Or([elem == 1, elem == 0]) for row in rows for elem in row]

    # sum of rows and cols must be exactly symbols_per_card
    constraints += [Sum(row) == symbols_per_card for row in rows]
    constraints += [Sum(col) == symbols_per_card for col in transposed(rows)]

    # Any two rows must have exactly one symbol in common, in other words they
    # differ in (symbols_per_card - 1) symbols, so their element-wise XOR will
    # have 2 * (symbols_per_card - 1) ones.
    D = 2 * (symbols_per_card - 1)
    for row_a, row_b in combinations(rows, 2):
        constraints += [Sum([a ^ b for a, b in zip(row_a, row_b)]) == D]

    solver = Solver()
    solver.add(constraints)

    if solver.check() == unsat:
        raise RuntimeError("Could not solve it :(")

    # create the incidence matrix
    model = solver.model()
    return [[model[elem].as_long() for elem in row] for row in rows]


if __name__ == "__main__":
    import sys
    symbols_per_card = int(sys.argv[1])
    incidence_matrix = spotit_z3(symbols_per_card)
    for row in incidence_matrix:
        print(row)

Resultados

$python spotit_z3.py 3
[0, 0, 1, 1, 0, 1, 0]
[0, 0, 0, 0, 1, 1, 1]
[0, 1, 0, 1, 0, 0, 1]
[1, 1, 0, 0, 0, 1, 0]
[0, 1, 1, 0, 1, 0, 0]
[1, 0, 0, 1, 1, 0, 0]
[1, 0, 1, 0, 0, 0, 1]
python spotit_z3.py 3  1.12s user 0.06s system 96% cpu 1.225 total

$ time python3 spotit_z3.py 4
[0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0]
[0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0]
[0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0]        
[0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1]
[0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1]
[0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1]
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0]
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]
[1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0]
python spotit_z3.py 4  664.62s user 0.15s system 99% cpu 11:04.88 total

$ time python3 spotit_z3.py 5
[1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1]
[0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1]
[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
[1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0]
python spotit_z3.py 5  1162.72s user 20.34s system 99% cpu 19:43.39 total

$ time python3 spotit_z3.py 8
<I killed it after 14 hours of run time.>

Eu gosto muito deste tópico. Eu construo este projeto python no github com partes deste código aqui para desenhar cartões personalizados como png (para que você possa solicitar jogos de cartas personalizados na internet).

https://github.com/plagtag/ProjectiveGeometry-Game

Escrevi um artigo sobre como gerar esse tipo de decks, com código em Perl. O código não é otimizado, mas é pelo menos capaz de gerar decks de pedidos "razoáveis" ... e um pouco mais.

Aqui está um exemplo da ordem 8, que deve considerar uma matemática subjacente um pouco mais complicada, porque 8 não é primo, embora seja uma ordem válida para gerar esse tipo de deck. Veja acima ou o artigo para obter uma explicação mais detalhada, abaixo, se você deseja gerar um Spot-It um pouco mais difícil :-)

$ time pg2 8
elements in field: 8
  0. (1, 9, 17, 25, 33, 41, 49, 57, 65)
  1. (0, 9, 10, 11, 12, 13, 14, 15, 16)
  2. (2, 9, 18, 27, 36, 45, 54, 63, 72)
  3. (6, 9, 22, 26, 37, 43, 56, 60, 71)
  4. (7, 9, 23, 32, 34, 46, 52, 59, 69)
  5. (8, 9, 24, 30, 35, 42, 55, 61, 68)
  6. (3, 9, 19, 29, 39, 44, 50, 64, 70)
  7. (4, 9, 20, 31, 38, 48, 53, 58, 67)
  8. (5, 9, 21, 28, 40, 47, 51, 62, 66)
  9. (0, 1, 2, 3, 4, 5, 6, 7, 8)
 10. (1, 10, 18, 26, 34, 42, 50, 58, 66)
 11. (1, 14, 22, 30, 38, 46, 54, 62, 70)
 12. (1, 15, 23, 31, 39, 47, 55, 63, 71)
 13. (1, 16, 24, 32, 40, 48, 56, 64, 72)
 14. (1, 11, 19, 27, 35, 43, 51, 59, 67)
 15. (1, 12, 20, 28, 36, 44, 52, 60, 68)
 16. (1, 13, 21, 29, 37, 45, 53, 61, 69)
 17. (0, 17, 18, 19, 20, 21, 22, 23, 24)
 18. (2, 10, 17, 28, 35, 46, 53, 64, 71)
 19. (6, 14, 17, 29, 34, 48, 51, 63, 68)
 20. (7, 15, 17, 26, 40, 44, 54, 61, 67)
 21. (8, 16, 17, 27, 38, 47, 50, 60, 69)
 22. (3, 11, 17, 31, 37, 42, 52, 62, 72)
 23. (4, 12, 17, 30, 39, 45, 56, 59, 66)
 24. (5, 13, 17, 32, 36, 43, 55, 58, 70)
 25. (0, 49, 50, 51, 52, 53, 54, 55, 56)
 26. (3, 10, 20, 30, 40, 43, 49, 63, 69)
 27. (2, 14, 21, 32, 39, 42, 49, 60, 67)
 28. (8, 15, 18, 28, 37, 48, 49, 59, 70)
 29. (6, 16, 19, 31, 36, 46, 49, 61, 66)
 30. (5, 11, 23, 26, 38, 45, 49, 64, 68)
 31. (7, 12, 22, 29, 35, 47, 49, 58, 72)
 32. (4, 13, 24, 27, 34, 44, 49, 62, 71)
 33. (0, 57, 58, 59, 60, 61, 62, 63, 64)
 34. (4, 10, 19, 32, 37, 47, 54, 57, 68)
 35. (5, 14, 18, 31, 35, 44, 56, 57, 69)
 36. (2, 15, 24, 29, 38, 43, 52, 57, 66)
 37. (3, 16, 22, 28, 34, 45, 55, 57, 67)
 38. (7, 11, 21, 30, 36, 48, 50, 57, 71)
 39. (6, 12, 23, 27, 40, 42, 53, 57, 70)
 40. (8, 13, 20, 26, 39, 46, 51, 57, 72)
 41. (0, 65, 66, 67, 68, 69, 70, 71, 72)
 42. (5, 10, 22, 27, 39, 48, 52, 61, 65)
 43. (3, 14, 24, 26, 36, 47, 53, 59, 65)
 44. (6, 15, 20, 32, 35, 45, 50, 62, 65)
 45. (2, 16, 23, 30, 37, 44, 51, 58, 65)
 46. (4, 11, 18, 29, 40, 46, 55, 60, 65)
 47. (8, 12, 21, 31, 34, 43, 54, 64, 65)
 48. (7, 13, 19, 28, 38, 42, 56, 63, 65)
 49. (0, 25, 26, 27, 28, 29, 30, 31, 32)
 50. (6, 10, 21, 25, 38, 44, 55, 59, 72)
 51. (8, 14, 19, 25, 40, 45, 52, 58, 71)
 52. (4, 15, 22, 25, 36, 42, 51, 64, 69)
 53. (7, 16, 18, 25, 39, 43, 53, 62, 68)
 54. (2, 11, 20, 25, 34, 47, 56, 61, 70)
 55. (5, 12, 24, 25, 37, 46, 50, 63, 67)
 56. (3, 13, 23, 25, 35, 48, 54, 60, 66)
 57. (0, 33, 34, 35, 36, 37, 38, 39, 40)
 58. (7, 10, 24, 31, 33, 45, 51, 60, 70)
 59. (4, 14, 23, 28, 33, 43, 50, 61, 72)
 60. (3, 15, 21, 27, 33, 46, 56, 58, 68)
 61. (5, 16, 20, 29, 33, 42, 54, 59, 71)
 62. (8, 11, 22, 32, 33, 44, 53, 63, 66)
 63. (2, 12, 19, 26, 33, 48, 55, 62, 69)
 64. (6, 13, 18, 30, 33, 47, 52, 64, 67)
 65. (0, 41, 42, 43, 44, 45, 46, 47, 48)
 66. (8, 10, 23, 29, 36, 41, 56, 62, 67)
 67. (7, 14, 20, 27, 37, 41, 55, 64, 66)
 68. (5, 15, 19, 30, 34, 41, 53, 60, 72)
 69. (4, 16, 21, 26, 35, 41, 52, 63, 70)
 70. (6, 11, 24, 28, 39, 41, 54, 58, 69)
 71. (3, 12, 18, 32, 38, 41, 51, 61, 71)
 72. (2, 13, 22, 31, 40, 41, 50, 59, 68)
errors in check: 0

real    0m0.303s
user    0m0.200s
sys 0m0.016s

Cada identificador de 0a 72pode ser lido tanto como identificador de cartão quanto como identificador de imagem. Por exemplo, a última linha significa que:

• cartão 72contém imagens 2, 13, 22, ..., 59, 68, E
• imagem 72aparece em cartões 2, 13, 22, ..., 59, e 68.