Quels sont les principes mathématiques / informatiques derrière ce jeu?

Mes enfants ont ce jeu amusant appelé Spot It! Les contraintes du jeu (du mieux que je puisse décrire) sont:

• C'est un jeu de 55 cartes
• Sur chaque carte se trouvent 8 images uniques (c'est-à-dire qu'une carte ne peut pas avoir 2 images identiques)
• Étant donné 2 cartes choisies dans le jeu, il y a 1 et 1 seule image correspondante .
• Les images correspondantes peuvent être mises à l'échelle différemment sur différentes cartes, mais cela ne fait que rendre le jeu plus difficile (c'est-à-dire qu'un petit arbre correspond toujours à un plus grand arbre)

Le principe du jeu est le suivant: retournez 2 cartes et celui qui choisit en premier l'image correspondante obtient un point.

Voici une image pour clarification:

(Exemple: vous pouvez voir sur les 2 cartes du bas ci-dessus que l'image correspondante est le dinosaure vert. Entre l'image en bas à droite et au milieu à droite, c'est la tête d'un clown.)

J'essaie de comprendre ce qui suit:

1. Quel est le nombre minimum de photos différentes requis pour répondre à ces critères et comment le détermineriez-vous?

2. En utilisant un pseudocode (ou Ruby), comment généreriez-vous 55 cartes de jeu à partir d'un tableau de N images (où N est le nombre minimum de la question 1)?

Mettre à jour:

Les images se produisent plus de deux fois par jeu (contrairement à ce que certains ont supposé). Voir cette image de 3 cartes, chacune avec un éclair:

Géométries projectives finies

Les axiomes de la géométrie projective (plane) sont légèrement différents de la géométrie euclidienne:

• Tous les deux points ont exactement une ligne qui les traverse (c'est la même chose).
• Toutes les deux lignes se rencontrent en un seul point (c'est un peu différent d'Euclide).

Maintenant, ajoutez "fini" dans la soupe et vous avez la question:

Peut-on avoir une géométrie avec seulement 2 points? Avec 3 points? Avec 4? Avec 7?

Il y a encore des questions ouvertes concernant ce problème mais nous le savons:

• S'il existe des géométries avec des Qpoints, alors Q = n^2 + n + 1et nest appelé le orderde la géométrie.
• Il y a des n+1points sur chaque ligne.
• De chaque point, passez exactement les n+1lignes.

• Le nombre total de lignes est également Q.

• Et enfin, si nest premier, alors il existe bien une géométrie d'ordre n.

Qu'est-ce que cela a à voir avec le puzzle, peut-on se demander.

Mettez cardau lieu de pointet pictureau lieu de lineet les axiomes deviennent:

• Toutes les deux cartes ont exactement une image en commun.
• Pour deux images, il y a exactement une carte qui contient les deux.

Maintenant, prenons n=7et nous avons la order-7géométrie finie avec Q = 7^2 + 7 + 1. Cela fait des Q=57lignes (images) et des Q=57points (cartes). Je suppose que les fabricants de puzzles ont décidé que 55 était plus rond que 57 et ont laissé 2 cartes.

Nous obtenons également n+1 = 8, donc de chaque point (carte), 8 lignes passent (8 images apparaissent) et chaque ligne (image) a 8 points (apparaît dans 8 cartes).

Voici une représentation du plus célèbre plan projectif fini (ordre 2) (géométrie) à 7 points, connu sous le nom de Fano Plane , copié de Noelle Evans - Finite Geometry Problem Page

Je pensais créer une image qui expliquerait comment le plan d'ordre 2 ci-dessus pourrait être transformé en un puzzle similaire avec 7 cartes et 7 images, mais un lien de la question jumelle math.exchange a exactement un tel schéma: Dobble-et- la-geometrie-finie

Pour ceux qui ont du mal à imaginer la géométrie du plan projectif avec 57 points, il existe une façon très agréable et intuitive de construire le jeu avec 57 cartes et 57 symboles (basé sur la réponse de Yuval Filmus pour cette question ):

1. Pour les cartes avec 8 symboles, créez une grille 7x7 de symboles uniques.
2. Ajoutez 8 symboles supplémentaires pour les "pentes" de 0 à 6, plus un pour la pente à l'infini.
3. Chaque carte est une ligne sur la grille (7 symboles) plus un symbole de la pente définie pour la pente de la ligne. Les lignes ont un décalage (c'est-à-dire le point de départ à gauche) et une pente (c'est-à-dire combien de symboles monter pour chaque pas à droite). Lorsque la ligne quitte la grille en haut, entrez à nouveau en bas. Voir cet exemple de figure (images de boardgamegeek ) pour deux de ces cartes:

Dans l'exemple, je prends une ligne avec une pente zéro (rouge) et une avec une pente 1 (vert). Ils se croisent à exactement un point commun (le hibou).

Cette méthode garantit que deux cartes ont exactement un symbole commun, car

1. Si les pentes sont différentes, les lignes se coupent toujours à exactement un point.
2. Si les pentes sont les mêmes, alors les lignes ne se coupent pas et il n'y aura pas de symbole commun de la grille. Dans ce cas, le symbole de pente sera le même.

De cette façon, nous pouvons construire des cartes 7x7 (7 décalages et 7 pentes).

Nous pouvons également construire sept cartes supplémentaires à partir de lignes verticales à travers la grille (c'est-à-dire en prenant chaque colonne). Pour ceux-ci, l'icône de pente infinie est utilisée.

Étant donné que chaque carte se compose de sept symboles de la grille et d'exactement un symbole "pente", nous pouvons créer une carte supplémentaire, qui se compose simplement des 8 symboles de pente.

Cela nous laisse 7x8 + 1 = 57 cartes possibles et 7 x 7 + 8 = 57 symboles requis.

(Naturellement, cela ne fonctionne qu'avec une grille de nombre premier (par exemple n = 7). Sinon, les lignes de pente différente pourraient avoir zéro ou plusieurs intersections si la pente est un diviseur de la taille de la grille.)

Il y a donc k = 55 cartes contenant m = 8 images chacune à partir d'un pool de n images au total. Nous pouvons reformuler la question «Combien d'images n avons-nous besoin, afin que nous puissions construire un ensemble de k cartes avec une seule image partagée entre une paire de cartes? de manière équivalente en demandant:

Étant donné un espace vectoriel à n dimensions et l'ensemble de tous les vecteurs, qui contiennent exactement m éléments égaux à un et tous les autres zéro, quelle doit être la taille de n , afin que nous puissions trouver un ensemble de k vecteurs, dont les produits scalaires par paires sont tous égaux à 1 ?

Il existe exactement ( n choisir m ) des vecteurs possibles pour construire des paires. Nous avons donc au moins besoin d'un n assez grand pour que ( n choisissez m )> = k . Ceci est juste une borne inférieure, donc pour remplir la contrainte de compatibilité par paire, nous avons probablement besoin d'un n beaucoup plus élevé .

Juste pour expérimenter un peu, j'ai écrit un petit programme Haskell pour calculer des jeux de cartes valides:

Edit: Je viens de réaliser après avoir vu la solution de Neil et Gajet, que l'algorithme que j'utilise ne trouve pas toujours la meilleure solution possible, donc tout ce qui suit n'est pas nécessairement valide. J'essaierai de mettre à jour mon code bientôt.

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

Le nombre maximum de cartes compatibles résultant pour m = 8 images par carte pour un nombre différent d'images à choisir parmi n pour les premiers n ressemble à ceci:

Cette méthode de force brute ne va cependant pas très loin à cause de l'explosion combinatoire. Mais j'ai pensé que ça pourrait être intéressant.

Il est intéressant de noter que pour un m donné , k augmente avec n seulement jusqu'à un certain n , après quoi il reste constant.

Cela signifie que pour chaque nombre d'images par carte, il existe un certain nombre d'images parmi lesquelles choisir, ce qui se traduit par un nombre maximum de cartes légales. Ajouter plus d'images à choisir parmi ce nombre optimal n'augmente pas davantage le nombre de cartes légales.

Les premiers k optimaux sont:

D'autres ont décrit le cadre général de la conception (plan projectif fini) et montré comment générer des plans projectifs finis d'ordre premier. Je voudrais juste combler certaines lacunes.

Des plans projectifs finis peuvent être générés pour de nombreux ordres différents, mais ils sont plus simples dans le cas d'un ordre premier p. Ensuite, les entiers modulo pforment un champ fini qui peut être utilisé pour décrire les coordonnées des points et des lignes dans le plan. Il y a 3 différents types de coordonnées pour les points: (1,x,y), (0,1,x)et (0,0,1)où xet ypeuvent prendre des valeurs de 0la p-1. Les 3 différents types de points expliquent la formule p^2+p+1du nombre de points dans le système. On peut aussi décrire les lignes avec les mêmes 3 types de coordonnées différentes: [1,x,y], [0,1,x]et [0,0,1].

Nous calculons si un point et une ligne sont incidents par si le produit scalaire de leurs coordonnées est égal à 0 mod p. Ainsi, par exemple, le point (1,2,5)et la ligne [0,1,1]sont incidents p=7depuis 1*0+2*1+5*1 = 7 == 0 mod 7, mais le point (1,3,3)et la ligne [1,2,6]ne sont pas incidents depuis 1*1+3*2+3*6 = 25 != 0 mod 7.

En traduisant dans le langage des cartes et des images, cela signifie que la carte avec les coordonnées (1,2,5)contient l'image avec les coordonnées [0,1,1], mais la carte avec les coordonnées (1,3,3)ne contient pas l'image avec les coordonnées [1,2,6]. Nous pouvons utiliser cette procédure pour développer une liste complète des cartes et des images qu'elles contiennent.

Soit dit en passant, je pense qu'il est plus facile de considérer les images comme des points et des cartes comme des lignes, mais il y a une dualité dans la géométrie projective entre les points et les lignes, donc cela n'a vraiment pas d'importance. Cependant, dans ce qui suit, j'utiliserai des points pour les images et des lignes pour les cartes.

La même construction fonctionne pour tout champ fini. Nous savons qu'il existe un champ d'ordre fini qsi et seulement si q=p^k, une puissance première. Le champ est appelé GF(p^k)ce qui signifie "champ de Galois". Les champs ne sont pas aussi faciles à construire dans le cas de puissance principale que dans le cas principal.

Heureusement, le travail acharné a déjà été fait et mis en œuvre dans les logiciels libres, à savoir Sage . Pour obtenir une conception de plan projectif d'ordre 4, par exemple, tapez simplement

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

et vous obtiendrez une sortie qui ressemble à

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

J'interprète ce qui précède comme suit: il y a 21 images étiquetées de 0 à 20. Chacun des blocs (ligne en géométrie projective) me dit quelles images apparaissent sur une carte. Par exemple, la première carte aura les images 0, 1, 2, 3 et 20; la deuxième carte aura les images 0, 4, 8, 12 et 16; etc.

Le système d'ordre 7 peut être généré par

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

qui génère la sortie

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

Je viens de trouver un moyen de le faire avec 57 ou 58 photos mais maintenant j'ai très mal à la tête, je posterai le code rubis dans 8 à 10 heures après avoir bien dormi! juste un indice ma ma solution toutes les 7 cartes partagent la même marque et 56 cartes au total peuvent être construites en utilisant ma solution.

voici le code qui génère les 57 cartes dont ypercube parlait. il utilise exactement 57 images, et désolé j'ai écrit du vrai code C ++ mais sachant que vector <something>c'est un tableau contenant des valeurs de type, somethingil est facile de comprendre ce que fait ce code. et ce code génère des P^2+P+1cartes utilisant des P^2+P+1images contenant chacune une P+1image et partageant une seule image en commun, pour chaque valeur P principale. ce qui signifie que nous pouvons avoir 7 cartes en utilisant 7 images ayant chacune 3 images (pour p = 2), 13 cartes en utilisant 13 images (pour p = 3), 31 cartes en utilisant 31 images (pour p = 5), 57 cartes pour 57 images (pour p = 7) et ainsi de suite ...

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

encore une fois désolé pour le code retardé.

Voici la solution de Gajet en Python, car je trouve Python plus lisible. Je l'ai modifié pour qu'il fonctionne également avec les nombres non premiers. J'ai utilisé Thies Insight pour générer un code d'affichage plus facile à comprendre.

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)

Avec sortie:

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

Utilisation du z3prouveur de théorème

Soit Ple nombre de symboles par carte. Selon cet article et sa ypercubeᵀᴹréponse, il y a respectivement des N = P**2 - P + 1cartes et des symboles. Un jeu de cartes peut être représenté avec sa matrice d'incidence qui a une ligne pour chaque carte et une colonne pour chaque symbole possible. Son (i,j)élément est 1si la carte ia un symbole jdessus. Il suffit de remplir cette matrice avec ces contraintes à l'esprit:

• chaque élément vaut zéro ou un
• la somme de chaque ligne est exactement P
• la somme de chaque colonne est exactement P
• deux lignes doivent avoir exactement un symbole en commun

Cela signifie des N**2variables et des N**2 + 2*N + (N choose 2)contraintes. Il semble être gérable en peu de temps avec z3de petites entrées.

edit : Malheureusement P = 8 semble être trop grand pour cette méthode. J'ai tué le processus après 14 heures de temps de calcul.

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)

Résultats

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

J'aime beaucoup ce fil. Je construis ce projet python github avec des parties de ce code ici pour dessiner des cartes personnalisées au format png (donc on peut commander des jeux de cartes personnalisés sur Internet).

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

J'ai écrit un article sur la façon de générer ce type de decks, avec du code en Perl. Le code n'est pas optimisé mais il est au moins capable de générer des decks de commandes "raisonnables" ... et quelques autres.

Voici un exemple avec l'ordre 8, qui doit prendre en compte un calcul sous-jacent légèrement plus compliqué, car 8 n'est pas premier bien qu'un ordre valide pour générer ce type de decks. Voir ci-dessus ou l'article pour une explication plus détaillée, ci-dessous si vous voulez simplement générer un Spot-It légèrement plus difficile :-)

$ 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

Chaque identifiant de 0à 72peut être lu à la fois comme identifiant de carte et comme identifiant d'image. Par exemple, la dernière ligne signifie que:

• carte 72contient des photos 2, 13, 22, ..., 59, 68ET
• photo 72apparaît dans les cartes 2, 13, 22, ..., 59et 68.