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

196

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

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

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

Вот картинка для пояснения:

определите это

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

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

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

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

Обновить:

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

Callmeed
источник
64
+1 за превращение игры во что-то, что ранит мой мозг.
кабаре
3
Минимальное количество снимков на карту или минимальное количество снимков, учитывая, что на карточку приходится 8? Кроме того, каждая фотография должна быть сопоставимой?
Истина
7
Я думаю, что вам нужно добавить больше ограничений. В противном случае вы можете положить яблоко на каждую карточку, а затем добавить любое количество уникальных изображений на каждую карточку. Каждая пара карт будет соответствовать только на изображении яблока.
Mbeckish
8
@ Cabaret: В таком случае вам понравится сет . Невероятно весело и отягчающее.
dmckee --- котенок экс-модератора
4
Хотя это отличный вопрос, его уже задавали на математическом сайте (мной). Здесь немного не по теме. - math.stackexchange.com/questions/36798/…
Джавид Джамай

Ответы:

148

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

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

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

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

Можем ли мы получить геометрию всего с 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-et- ла-Geometrie-finie

Самолет Фано

ypercubeᵀᴹ
источник
9
Таким образом, эта игра демонстрирует неевклидову геометрию? Было бы правильно сказать, что карты верны?
RMorrisey
2
Это звучит круто, но я не уверен, что это действительно хорошо моделирует проблему. @ypercube, не могли бы вы объяснить немного больше, почему вы считаете, что аналогия между картой / изображением и точкой / линией действительна?
Нейт Кол
@Nate: первая аналогия every two cards have exactly one picture in common, изложенная в вопросе. Во-вторых for every two pictures there is exactly one card that has both of them, ОП может сказать нам, удовлетворяет ли игровой набор.
ypercubeᵀᴹ
4
Отличный ответ! Отличное понимание, понимание того, что игра соответствует свойствам проективной плоскости Порядка 7, плюс одно из лучших объяснений проективных плоскостей для непрофессионалов, которые я видел.
RBarryYoung
3
Brilliant. Мне нужно будет прочитать это еще 100 раз, чтобы попытаться выяснить, как генерировать наборы карт в Python ...
Джаред
22

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

  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). В противном случае линии с другим наклоном могут иметь ноль или более одного пересечения, если уклон является делителем размера сетки.)

Свен Цвей
источник
18

Таким образом, есть k = 55 карт, содержащих m = 8 изображений каждая из общего количества 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 выглядит следующим образом:

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

Интересно, что , кажется , что для данного м , K увеличивается с ростом п только до некоторого п , после чего она остается постоянной.

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

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

оптимальная таблица

Thies Heidecke
источник
Это просто первоначальная попытка связать, верно? Вы не включили требование «парные точки, равные 1» ...
Nemo
Видимо, подсветка синтаксиса здесь действительно не поддерживает Haskell еще ( meta.stackexchange.com/questions/78363/... ), но я буду бросать в подсказке только в случае , если это в будущем.
BoltClock
@BoltClock спасибо за ваши изменения! я не знал, что вы могли бы дать подсказки для подсветки синтаксиса для конкретного языка.
Thies Heidecke
Это еще не очень хорошо известно :)
BoltClock
9

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

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

Я только что нашел способ сделать это с 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 изображений (для р = 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();
    }
}

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

Ali1S232
источник
37
У меня есть элегантное доказательство этого, но, увы, это поле для комментариев слишком мало, чтобы его содержать.
Sarnold
@Gajet: Вы управляли этим для p=4? (и 21 карта / картинки)
ypercubeᵀᴹ
4 не работает в моем алгоритме, так как 4 не простое число, в моем алгоритме важно, чтобы p было простым.
Ali1S232
@ypercube после повторной проверки, были некоторые незначительные ошибки в моем алгоритме, но я проверил его, 2, 3,5,7, и я могу доказать, что для любого другого простого числа это будет работать, так что вот мой полный код (но в c ++)
Ali1S232
1
@Gajet: классное решение! Теперь я понимаю, почему мой жадный алгоритм не всегда дает лучшее решение.
Thies Heidecke
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)

С выходом:

***      *   
   ***   *   
      ****   
*  *  *   *  
 *  *  *  *  
  *  *  * *  
*   *   *  * 
 *   **    * 
  **   *   * 
*    * *    *
 * *    *   *
  * * *     *
         ****
Нил Г
источник
2
я думаю, что последние три карты в вашем примере недействительны, потому что они не делят изображение с пятой картой. Просто проверил мой код более часа, прежде чем я понял это :) Интересно, что максимальный размер легального набора карт составляет 5 на 4 изображения на карту и не увеличивается даже при большем количестве изображений на выбор.
Thies Heidecke
1
@ Благодаря диаграмме, которую я создал с использованием кода Gajet, гораздо проще понять, почему существуют именно такие (p) + (p * p) + (1)конфигурации.
Нил Дж
1
@Neil: Спасибо за обновленную диаграмму, благодаря которой гораздо проще увидеть, как работает решение Gajet!
Thies Heidecke
1
@Gajet: я думаю, что вы ошибаетесь all p except 4 and 6. Если вы хотите создать конечную плоскость, в которой есть p*p+p+1точки и линии (карты и рисунки), то это связано finite fieldsи не связано rings. Есть конечные поля порядка, pкогда р primeили а prime power. Ваш код работает правильно для простых чисел, потому что выражения типа k * p + (j + i * k) % pвыражаются k*p + j + i*kв терминах умножения и сложения в конечном поле порядка p.
ypercubeᵀᴹ
1
Он будет работать правильно для простых чисел тоже, если вы можете выразить эти операции (. Мульт и сложение) в конечных полях порядка p^2, p^3и т.д. Таким образом, он будет работать4, 8, 9, 16, 25, 27, ...
ypercubeᵀᴹ
4

Используя 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небольших затратах.

редактировать : к сожалению, 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.>
PGY
источник
4

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

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

PlagTag
источник
3

Я написал статью о том, как генерировать такие колоды с помощью кода на 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.
polettix
источник