¿Cuáles son los principios matemáticos / computacionales detrás de este juego?

¡Mis hijos tienen este divertido juego llamado Spot It! Las restricciones del juego (como mejor puedo describir) son:

• Es un mazo de 55 cartas.
• En cada tarjeta hay 8 imágenes únicas (es decir, una tarjeta no puede tener 2 de la misma imagen)
• Dadas las 2 cartas elegidas del mazo, hay 1 y solo 1 imagen coincidente .
• Las imágenes coincidentes se pueden escalar de manera diferente en diferentes tarjetas, pero eso es solo para hacer que el juego sea más difícil (es decir, un árbol pequeño todavía coincide con un árbol más grande)

El principio del juego es: voltear 2 cartas y quien primero elija la imagen correspondiente obtendrá un punto.

Aquí hay una imagen para aclarar:

(Ejemplo: puedes ver en las 2 cartas inferiores de arriba que la imagen correspondiente es el dinosaurio verde. Entre la imagen inferior derecha y la derecha central, es la cabeza de un payaso).

Estoy tratando de entender lo siguiente:

1. ¿Cuál es el número mínimo de imágenes diferentes requeridas para cumplir con estos criterios y cómo lo determinaría?

2. Usando pseudocódigo (o Ruby), ¿cómo generaría 55 tarjetas de juego a partir de una serie de N imágenes (donde N es el número mínimo de la pregunta 1)?

Actualizar:

Las imágenes ocurren más de dos veces por cubierta (al contrario de lo que algunos han supuesto). Vea esta imagen de 3 cartas, cada una con un rayo:

Geometrías proyectivas finitas

Los axiomas de la geometría proyectiva (plana) son ligeramente diferentes de la geometría euclidiana:

• Cada dos puntos tienen exactamente una línea que los atraviesa (esto es lo mismo).
• Cada dos líneas se encuentran exactamente en un punto (esto es un poco diferente de Euclides).

Ahora, agregue "finito" en la sopa y tiene la pregunta:

¿Podemos tener una geometría con solo 2 puntos? Con 3 puntos? Con 4? Con 7?

Todavía hay preguntas abiertas sobre este problema, pero lo sabemos:

• Si hay geometrías con Qpuntos, entonces Q = n^2 + n + 1y nse llama el orderde la geometría.
• Hay n+1puntos en cada línea.
• Desde cada punto, pase exactamente las n+1líneas.

• Número total de líneas también Q.

• Y finalmente, si nes primo, existe una geometría de orden n.

¿Qué tiene que ver eso con el rompecabezas?

Poner en cardlugar de pointy en picturelugar de liney los axiomas se convierten en:

• Cada dos cartas tienen exactamente una imagen en común.
• Por cada dos imágenes hay exactamente una tarjeta que tiene ambas.

Ahora, tomemos n=7y tenemos la order-7geometría finita con Q = 7^2 + 7 + 1. Eso hace Q=57líneas (imágenes) y Q=57puntos (tarjetas). Supongo que los fabricantes de rompecabezas decidieron que 55 es más número redondo que 57 y dejaron 2 cartas.

También obtenemos n+1 = 8, así que desde cada punto (tarjeta), pasan 8 líneas (aparecen 8 imágenes) y cada línea (imagen) tiene 8 puntos (aparece en 8 tarjetas).

Aquí hay una representación del plano proyectivo finito más famoso (orden 2) (geometría) con 7 puntos, conocido como Plano Fano , copiado de Noelle Evans - Página del problema de geometría finita

Estaba pensando en crear una imagen que explicara cómo el plano de orden 2 anterior podría convertirse en un rompecabezas similar con 7 cartas y 7 imágenes, pero luego un enlace de la pregunta gemela matemática de intercambio tiene exactamente ese diagrama: Dobble-et- la-geometrie-finie

Para aquellos que tienen problemas para imaginar la geometría del plano proyectivo con 57 puntos, hay una forma realmente agradable e intuitiva de construir el juego con 57 cartas y 57 símbolos (basado en la respuesta de Yuval Filmus para esta pregunta ):

1. Para tarjetas con 8 símbolos, cree una cuadrícula de 7x7 de símbolos únicos.
2. Agregue 8 símbolos adicionales para las "pendientes" de 0 a 6, más uno para la pendiente infinita.
3. Cada carta es una línea en la cuadrícula (7 símbolos) más un símbolo de la pendiente establecida para la pendiente de la línea. Las líneas tienen un desplazamiento (es decir, un punto de partida a la izquierda) y una pendiente (es decir, cuántos símbolos subir para cada paso a la derecha). Cuando la línea sale de la cuadrícula en la parte superior, vuelva a ingresar en la parte inferior. Vea esta figura de ejemplo (imágenes de boardgamegeek ) para dos de esas tarjetas:

En el ejemplo, tomo una línea con pendiente cero (rojo) y otra con pendiente 1 (verde). Se cruzan exactamente en un punto común (el búho).

Este método asegura que dos cartas tengan exactamente un símbolo común, porque

1. Si las pendientes son diferentes, entonces las líneas siempre se intersecarán exactamente en un punto.
2. Si las pendientes son las mismas, las líneas no se intersectarán y no habrá un símbolo común de la cuadrícula. En este caso, el símbolo de pendiente será el mismo.

De esta manera, podemos construir tarjetas 7x7 (7 compensaciones y 7 pendientes).

También podemos construir siete cartas adicionales a partir de líneas verticales a través de la cuadrícula (es decir, tomar cada columna). Para ellos, se usa el icono de pendiente infinita.

Debido a que cada tarjeta consta de siete símbolos de la cuadrícula y exactamente un símbolo de "pendiente", podemos crear una tarjeta adicional, que simplemente consta de los 8 símbolos de pendiente.

Esto nos deja con 7x8 + 1 = 57 cartas posibles, y 7 x 7 + 8 = 57 símbolos requeridos.

(Naturalmente, esto solo funciona con una cuadrícula del tamaño de un número primo (por ejemplo, n = 7). De lo contrario, las líneas de pendiente diferente podrían tener cero o más de una intersección si la pendiente es un divisor del tamaño de la cuadrícula).

Entonces, hay k = 55 tarjetas que contienen m = 8 imágenes cada una de un grupo de n imágenes en total. Podemos reformular la pregunta "¿Cuántas imágenes n necesitamos para poder construir un conjunto de k tarjetas con una sola imagen compartida entre cualquier par de tarjetas?" equivalentemente preguntando:

Dado un espacio vectorial n- dimensional y el conjunto de todos los vectores, que contienen exactamente m elementos iguales a uno y todos los demás cero, qué tan grande tiene que ser n , de modo que podamos encontrar un conjunto de k vectores, cuyos productos de puntos por pares son todos iguales a 1 ?

Hay exactamente ( n elegir m ) posibles vectores para construir pares. Entonces, al menos necesitamos un n lo suficientemente grande como para que ( n elija m )> = k . Esto es solo un límite inferior, por lo que para cumplir con la restricción de compatibilidad por pares posiblemente necesitemos una n mucho más alta .

Solo por experimentar un poco, escribí un pequeño programa Haskell para calcular conjuntos de tarjetas válidos:

Editar: Acabo de darme cuenta después de ver la solución de Neil y Gajet, que el algoritmo que uso no siempre encuentra la mejor solución posible, por lo que todo lo siguiente no es necesariamente válido. Intentaré actualizar mi código pronto.

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

El número máximo resultante de tarjetas compatibles para m = 8 imágenes por tarjeta para un número diferente de imágenes para elegir n para los primeros n se ve así:

Sin embargo, este método de fuerza bruta no llega muy lejos debido a la explosión combinatoria. Pero pensé que aún podría ser interesante.

Curiosamente, parece que para m dado , k aumenta con n solo hasta cierto n , después de lo cual se mantiene constante.

Esto significa que, por cada número de imágenes por tarjeta, hay un cierto número de imágenes para elegir, lo que da como resultado el máximo número posible de tarjetas legales. Agregar más fotos para elegir del pasado ese número óptimo ya no aumenta el número de tarjetas legales.

Las primeras k óptimas son:

Otros han descrito el marco general para el diseño (plano proyectivo finito) y han mostrado cómo generar planos proyectivos finitos de primer orden. Solo me gustaría llenar algunos vacíos.

Se pueden generar planos proyectivos finitos para muchos órdenes diferentes, pero son más directos en el caso del orden primario p. Luego, el módulo de números enteros pforma un campo finito que puede usarse para describir coordenadas para los puntos y líneas en el plano. Hay 3 tipos diferentes de coordenadas de puntos: (1,x,y), (0,1,x)y (0,0,1), donde xy ypueden tomar valores de 0a p-1. Los 3 tipos diferentes de puntos explican la fórmula p^2+p+1para el número de puntos en el sistema. También podemos describir líneas con las mismas 3 diferentes tipos de coordenadas: [1,x,y], [0,1,x], y [0,0,1].

Calculamos si un punto y una línea son incidentes si el producto escalar de sus coordenadas es igual a 0 mod p. Entonces, por ejemplo, el punto (1,2,5)y la línea [0,1,1]son incidentes cuando p=7desde entonces 1*0+2*1+5*1 = 7 == 0 mod 7, pero el punto (1,3,3)y la línea [1,2,6]no son incidentes desde entonces 1*1+3*2+3*6 = 25 != 0 mod 7.

Traduciendo al lenguaje de tarjetas e imágenes, eso significa que la tarjeta con coordenadas (1,2,5)contiene la imagen con coordenadas [0,1,1], pero la tarjeta con coordenadas (1,3,3)no contiene la imagen con coordenadas [1,2,6]. Podemos utilizar este procedimiento para desarrollar una lista completa de tarjetas y las imágenes que contienen.

Por cierto, creo que es más fácil pensar en las imágenes como puntos y tarjetas como líneas, pero hay una dualidad en la geometría proyectiva entre puntos y líneas, por lo que realmente no importa. Sin embargo, en lo que sigue usaré puntos para imágenes y líneas para tarjetas.

La misma construcción funciona para cualquier campo finito. Sabemos que hay un campo finito de orden qsi y solo si q=p^k, una potencia principal. El campo se llama GF(p^k)que significa "campo de Galois". Los campos no son tan fáciles de construir en el primer caso de poder como en el primer caso.

Afortunadamente, el trabajo duro ya se ha realizado e implementado en software libre, a saber, Sage . Para obtener un diseño de plano proyectivo de orden 4, por ejemplo, simplemente escriba

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

y obtendrás una salida que se parece a

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 lo anterior de la siguiente manera: hay 21 imágenes etiquetadas de 0 a 20. Cada uno de los bloques (línea en geometría proyectiva) me dice qué imágenes aparecen en una tarjeta. Por ejemplo, la primera tarjeta tendrá imágenes 0, 1, 2, 3 y 20; la segunda tarjeta tendrá imágenes 0, 4, 8, 12 y 16; y así.

El sistema de orden 7 puede ser generado por

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

que genera la salida

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]]>

Acabo de encontrar una manera de hacerlo con 57 o 58 imágenes, pero ahora tengo un dolor de cabeza muy fuerte, ¡publicaré el código ruby ​​en 8-10 horas después de haber dormido bien! solo una pista: mi solución cada 7 tarjetas comparten la misma marca y se pueden construir un total de 56 tarjetas utilizando mi solución.

Aquí está el código que genera las 57 tarjetas de las que hablaba Ypercube. utiliza exactamente 57 imágenes, y lo siento, he escrito un código C ++ real, pero sabiendo que vector <something>es una matriz que contiene valores de tipo something, es fácil entender lo que hace este código. y este código genera P^2+P+1tarjetas que usan P^2+P+1imágenes que contienen P+1imágenes y comparten solo 1 imagen en común, por cada valor P principal. lo que significa que podemos tener 7 tarjetas con 7 imágenes, cada una con 3 imágenes (para p = 2), 13 tarjetas con 13 imágenes (para p = 3), 31 tarjetas con 31 imágenes (para p = 5), 57 tarjetas para 57 imágenes (para p = 7) y así sucesivamente ...

#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();
    }
}

Nuevamente, perdón por el código retrasado.

Aquí está la solución de Gajet en Python, ya que encuentro Python más legible. Lo he modificado para que también funcione con números no primos. He utilizado la información de Thies para generar un código de visualización más 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)

Con salida:

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

Usando el z3probador de teoremas

Deje Pser el número de símbolos por tarjeta. Según este artículo y ypercubeᵀᴹsu respuesta, hay N = P**2 - P + 1tarjetas y símbolos, respectivamente. Se puede representar un mazo de cartas con su matriz de incidencia que tiene una fila para cada carta y una columna para cada símbolo posible. Su (i,j)elemento es 1si la tarjeta itiene un símbolo j. Solo necesitamos llenar esta matriz con estas restricciones en mente:

• cada elemento es cero o uno
• la suma de cada fila es exactamente P
• la suma de cada columna es exactamente P
• dos filas deben tener exactamente un símbolo en común

Eso significa N**2variables y N**2 + 2*N + (N choose 2)restricciones. Parece ser manejable en poco tiempo con z3entradas pequeñas.

editar : Desafortunadamente P = 8 parece ser demasiado grande para este método. Maté el proceso después de 14 horas de tiempo de cálculo.

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

Me gusta mucho este hilo. Construyo este proyecto de Github Python con partes de este código aquí para dibujar tarjetas personalizadas como png (para que uno pueda pedir juegos de cartas personalizados en Internet).

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

Escribí un artículo sobre cómo generar este tipo de mazos, con código en Perl. El código no está optimizado, pero al menos es capaz de generar mazos de órdenes "razonables" ... y algo más.

Aquí hay un ejemplo con el orden 8, que tiene que considerar una matemática subyacente un poco más complicada, porque 8 no es primo, aunque es un orden válido para generar este tipo de mazos. Consulte más arriba o el artículo para obtener una explicación más detallada, más abajo si solo desea generar un Spot-It un poco más 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 72puede leerse como un identificador de tarjeta y como un identificador de imagen. Por ejemplo, la última fila significa que:

• la tarjeta 72contiene imágenes 2, 13, 22, ..., 59, 68, Y
• la imagen 72aparece en las tarjetas 2, 13, 22, ..., 59, y 68.