Каковы математические / вычислительные принципы этой игры?

Question

У моих детей есть эта забавная игра под названием Найди это! Ограничения игры (насколько я могу описать):

• Это колода из 55 карт
• На каждой карте 8 уникальных картинок (т.е. на карте не может быть 2 одинаковых картинок)
• Учитывая любые 2 карты, выбранные из колоды, есть 1 и только 1 подходящая картинка .
• Соответствующие изображения могут быть по-разному масштабированы на разных картах, но это только усложняет игру (т. Е. Небольшое дерево по-прежнему соответствует большему дереву)

Принцип игры: переверните 2 карты, и тот, кто первым выберет подходящую картинку, получит очко.

Вот картинка для уточнения:

(Пример: из нижних 2-х карт выше видно, что изображение соответствует зеленому динозавру. Между изображением справа внизу и справа - голова клоуна.)

Я пытаюсь понять следующее:

1. Какое минимальное количество различных изображений требуется для соответствия этим критериям и как бы вы это определили?

2. Используя псевдокод (или Ruby), как бы вы сгенерировали 55 игровых карт из массива из N картинок (где N - минимальное число из вопроса 1)?

Обновление:

Снимки появляются более двух раз на колоду (вопреки тому, что некоторые предполагали). Посмотрите на эту картинку из 3 карт, каждая с молнией:

Answer 1

Конечные проективные геометрии

Аксиомы из проективной (плоской) геометрии немного отличаются от евклидовой геометрии:

• Каждые две точки имеют ровно одну линию, проходящую через них (это то же самое).
• Каждые две линии встречаются ровно в одной точке (это немного отличается от Евклида).

Теперь добавьте "конечный" в суп, и у вас возникнет вопрос:

Можем ли мы получить геометрию всего с 2 точками? С 3 баллами? С 4? С 7?

Есть еще открытые вопросы относительно этой проблемы, но мы знаем это:

• Если существуют геометрии с Q точками, то Q = n^2 + n + 1 и n называются order геометрии.
• В каждой строке n+1 точек.
• Из каждой точки проходите ровно n+1 строк.

• Общее количество строк также Q.

• И, наконец, если n является простым, то существует геометрия порядка n.

---

Какое отношение это имеет к головоломке, можно спросить.

Поставьте card вместо point и picture вместо line, и аксиомы станут:

• Каждые две карты имеют ровно одну общую картинку.
• Для каждых двух снимков есть ровно одна карточка с обоими.

Теперь давайте возьмем n=7, и у нас есть order-7 конечная геометрия с Q = 7^2 + 7 + 1. Это составляет Q=57 линий (картинки) и Q=57 точек (карты). Я предполагаю, что создатели головоломки решили, что число 55 больше, чем 57, и оставили 2 карты.

Мы также получаем n+1 = 8, поэтому из каждой точки (карты) проходит 8 строк (появляется 8 изображений), и каждая строка (изображение) имеет 8 точек (отображается в 8 картах).

---

Вот представление самой известной конечной проективной (порядка 2) плоскости (геометрии) с 7 точками, известной как Плоскость Фано , скопированной с Ноэль Эванс - Страница задачи конечной геометрии

Я думал о создании изображения, которое объясняет, как с помощью вышеприведенного самолета порядка 2 можно создать аналогичную головоломку с 7 картами и 7 фотографиями, но тогда ссылка из вопроса-близнеца math.exchange имеет именно такую ​​диаграмму: Dobble-и-ла-Geometrie-finie

Answer 2

Таким образом, существует k = 55 карт, содержащих m = 8 изображений, каждая из которых состоит из n изображений.Мы можем переформулировать вопрос: «Сколько изображений n нам нужно, чтобы мы могли построить набор карт k с одним общим изображением между любой парой карт?»эквивалентно, задавая:

Учитывая n -мерное векторное пространство и набор всех векторов, которые содержат ровно m элементов, равных одному и всем остальнымноль, насколько большим должно быть n , чтобы мы могли найти набор k векторов, чьи произведения попарных точек равны 1 ?

Существует ровно ( n выбор m ) возможных векторов для построения пар.Так что нам по крайней мере нужен достаточно большой n , чтобы ( n выберите m )> = k .Это всего лишь нижняя граница, поэтому для выполнения ограничения парной совместимости нам, возможно, понадобится намного более высокий n .

Просто для эксперимента я написал небольшую программу на Haskell для вычисления допустимых наборов карт:

Редактировать: Я только что понял, увидев решение Нейла и Гайета, что используемый мной алгоритм не всегда находит наилучшее возможное решение, поэтому все нижеприведенное не обязательно верно.Я постараюсь обновить свой код в ближайшее время.

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

Полученное максимальное количество совместимых карт для m = 8 изображений на карту для различного количества изображений на выбор n для первых нескольких n выглядит следующим образом:

Этот метод грубой силы не очень далеко, хотя из-за комбинаторного взрыва.Но я подумал, что это все еще может быть интересно.

Интересно, кажется, что для данных m , k увеличивается с n только доопределенное значение n , после чего оно остается постоянным.

Это означает, что для каждого количества снимков на карте имеется определенное количество снимков на выбор, что приводит к максимально возможному числулегальные карточки.Добавление большего количества картинок, чтобы выбрать из прошлого, что оптимальное количество больше не увеличивает количество легальных карт.

Первые несколько оптимальных k :

Answer 3

Для тех, у кого проблемы с изображением геометрии проективной плоскости с 57 точками, есть действительно хороший, интуитивно понятный способ построить игру с 57 картами и 57 символами (основанный на ответе Yuval Filmus для этот вопрос ):

1. Для карт с 8 символами создайте сетку уникальных символов 7x7.
2. Добавьте еще 8 символов для «уклонов» от 0 до 6, плюс один для бесконечного уклона.
3. Каждая карта представляет собой линию на сетке (7 символов) плюс один символ из наклона, установленного для наклона линии. Линии имеют смещение (то есть начальную точку слева) и наклон (то есть, сколько символов нужно поднять для каждого шага вправо). Когда линия покидает сетку сверху, введите ее снова внизу. Посмотрите на этот пример (изображения из boardgamegeek ) для двух таких карт:

В этом примере я возьму одну линию с наклоном ноль (красный) и одну линию с наклоном 1 (зеленый). Они пересекаются ровно в одной общей точке (сова).

Этот метод гарантирует, что любые две карты имеют ровно один общий символ, потому что

1. Если наклоны разные, то линии всегда будут пересекаться ровно в одной точке.
2. Если наклоны одинаковы, то линии не будут пересекаться, и в сетке не будет общего символа. В этом случае символ наклона будет таким же.

Таким образом, мы можем построить карты 7х7 (7 смещений и 7 уклонов).

Мы также можем построить семь дополнительных карт из вертикальных линий через сетку (т.е. взяв каждый столбец). Для них используется значок наклона бесконечности.

Поскольку каждая карта состоит из семи символов из сетки и ровно одного символа «уклон», мы можем создать одну дополнительную карту, которая просто состоит из всех 8 символов уклона.

В результате у нас остается 7x8 + 1 = 57 возможных карт и 7 x 7 + 8 = 57 необходимых символов.

(Естественно, это работает только с сеткой размером с простое число (например, n = 7). В противном случае линии с другим наклоном могут иметь ноль или более одного пересечения, если наклон является делителем размера сетки.)

Answer 4

Другие описали общие рамки для проектирования (конечная проективная плоскость) и показали, как генерировать конечные проективные плоскости простого порядка. Я просто хотел бы заполнить некоторые пробелы.

Конечные проективные плоскости могут быть сгенерированы для многих различных порядков, но они наиболее просты в случае простого порядка p. Тогда целые числа по модулю p образуют конечное поле, которое можно использовать для описания координат точек и линий на плоскости. Для точек существует 3 вида координат: (1,x,y), (0,1,x) и (0,0,1), где x и y могут принимать значения от 0 до p-1. 3 различных вида точек объясняют формулу p^2+p+1 для количества точек в системе. Мы также можем описать линии с одинаковыми тремя различными типами координат: [1,x,y], [0,1,x] и [0,0,1].

Мы вычисляем, являются ли точка и линия инцидентными, равняется ли произведение точек их координат на 0 mod p. Так, например, точка (1,2,5) и линия [0,1,1] являются инцидентными, когда p=7 с 1*0+2*1+5*1 = 7 == 0 mod 7, но точка (1,3,3) и линия [1,2,6] не являются инцидентными с 1*1+3*2+3*6 = 25 != 0 mod 7.

Перевод на язык карточек и картинок, то есть карта с координатами (1,2,5) содержит картинку с координатами [0,1,1], но карта с координатами (1,3,3) не содержит картинку с координатами [1,2,6]. Мы можем использовать эту процедуру для разработки полного списка карточек и изображений, которые они содержат.

Кстати, я думаю, что проще воспринимать картинки как точки, а карты как линии, но в проективной геометрии между точками и линиями есть двойственность, так что это действительно не имеет значения. Однако в дальнейшем я буду использовать точки для картинок и линии для карточек.

Та же самая конструкция работает для любого конечного поля. Мы знаем, что существует конечное поле порядка q тогда и только тогда, когда q=p^k - простая степень. Поле называется GF(p^k), что означает «поле Галуа». Поля не так просто построить в простом степенном случае, как в простом.

К счастью, тяжелая работа уже выполнена и реализована в свободном программном обеспечении, а именно Sage . Например, чтобы получить проективную плоскость порядка 4, просто наберите

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

и вы получите вывод, похожий на

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

Я интерпретирую вышесказанное следующим образом: есть 21 изображение, помеченное от 0 до 20. Каждый из блоков (линия в проективной геометрии) говорит мне, какие изображения появляются на карте. Например, первая карта будет иметь изображения 0, 1, 2, 3 и 20; вторая карта будет иметь изображения 0, 4, 8, 12 и 16; и так далее.

Система порядка 7 может быть сгенерирована с помощью

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

, который генерирует вывод

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

Answer 5

Я только что нашел способ сделать это с 57 или 58 фотографиями, но сейчас у меня очень сильная головная боль, я выложу код рубина через 8-10 часов после того, как я выспался!просто подсказка для моего решения: каждые 7 карт имеют одинаковую оценку, и с помощью моего решения можно построить 56 карт.

Вот код, который генерирует все 57 карт, о которых говорил ypercube.он использует ровно 57 картинок, и извините, я написал настоящий код C ++, но зная, что vector <something> - это массив, содержащий значения типа something, легко понять, что делает этот код.и этот код генерирует карты P^2+P+1, используя P^2+P+1 изображения, каждое из которых содержит P+1 изображение, и совместно использует только 1 общее изображение для каждого простого значения P.это означает, что мы можем иметь 7 карт, используя 7 изображений, каждое из которых имеет 3 изображения (для p = 2), 13 карт, используя 13 изображений (для p = 3), 31 карту, используя 31 изображение (для p = 5), 57 карт для 57 изображений(для p = 7) и так далее ...

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

еще раз извините за задержанный код.

Answer 6

Вот решение Gajet на Python, так как я считаю Python более читабельным.Я изменил его так, чтобы он работал и с не простыми числами.Я использовал Thies Insight для создания более понятного кода дисплея.

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)

С выводом:

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

Answer 7

Мне очень нравится эта тема.Я строю этот проект на github python с частями этого кода, чтобы рисовать пользовательские карты в формате png (так что можно заказать пользовательские карточные игры в Интернете).

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

Answer 8

Использование средства доказательства теорем z3

Пусть P - количество символов на карточку.Согласно ответам этой статьи и ypercubeᵀᴹ есть N = P**2 - P + 1 карточек и символов соответственно.Колода карт может быть представлена ​​с ее матрицей инцидентности, которая имеет строку для каждой карты и столбец для каждого возможного символа.Элемент (i,j) равен 1, если на карточке i имеется символ j.Нам нужно всего лишь заполнить эту матрицу с учетом следующих ограничений:

• каждый элемент равен нулю или единице
• сумма каждой строки в точности равна P
• сумма каждого столбца равна точно P
• любые две строки должны иметь ровно один общий символ

Это означает N**2 переменные и N**2 + 2*N + (N choose 2) ограничения.Кажется, что это можно сделать за очень короткое время с z3 для небольших входов.

edit : К сожалению, P = 8 кажется слишком большим для этого метода.Я убил процесс после 14 часов вычислений.

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)

Результаты

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

Answer 9

Я написал статью о том, как генерировать такие колоды с помощью кода на Perl. Код не оптимизирован, но, по крайней мере, способен генерировать колоды «разумных» порядков ... и некоторые другие.

Вот пример с порядком 8, который должен учитывать немного более сложную математическую схему, потому что 8 не является простым, хотя действительный порядок для генерации таких колод. См. Выше или статью для более подробного объяснения, ниже, если вы просто хотите создать немного более сложный Spot-It: -)

$ 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

Каждый идентификатор от 0 до 72 может быть прочитан как идентификатор карты и как идентификатор изображения. Например, последняя строка означает, что:

• карта 72 содержит изображения 2, 13, 22, ..., 59, 68, И
• изображение 72 появляется в карточках 2, 13, 22, ..., 59 и 68.