Мгновенное безумие

Instant Insanity — это название, данное компанией Parker Brothers своей версии головоломки 1967 года, которая существует с древних времен и продается многими производителями игрушек и головоломок под разными названиями, в том числе: Devil's Dice ( Pressman ); DamBlocks (Шапер); Логи-Кубес (Шеффер); Logi Cubes (ThinkinGames); Даффи Дотс (Рейсс); Эти блоки (Остин); PsykoNosis (Идеи от А до Я) и многие другие. ^[1]

Головоломка состоит из четырех кубиков с гранями, окрашенными в четыре цвета (обычно красный, синий, зеленый и белый). Цель головоломки — сложить эти кубики в столбик так, чтобы на каждой стороне стопки (спереди, сзади, слева и справа) был изображен каждый из четырех цветов. Распределение цветов на каждом кубике уникально, и порядок, в котором расположены четыре кубика, не имеет значения, если на каждой стороне изображен каждый цвет.

Эта проблема имеет решение на основе теории графов , в котором для представления каждого куба можно использовать граф с четырьмя вершинами, помеченными B, G, R, W (синий, зеленый, красный и белый); между двумя вершинами существует ребро, если два цвета находятся на противоположных сторонах куба, и петля в вершине, если противоположные стороны имеют одинаковый цвет. Каждый отдельный куб можно разместить в одном из 24 положений, поместив любую из шести граней вверх, а затем повернув куб до трех четвертей оборота. После того, как стопка сформирована, ее можно повернуть на три четверти оборота, не меняя ориентации какого-либо куба относительно других. Если игнорировать порядок укладки кубиков, общее возможное количество комбинаций составит 82 944 (24 * 24 * 24 * 24/4). Загадку исследует Д. Е. Кнут в статье об оценке времени выполнения процедур исчерпывающего поиска с обратным поиском. ^[2]

Каждую позицию головоломки можно решить за восемь ходов или меньше. ^[3]

Первая известная запатентованная версия головоломки была создана Фредериком А. Шоссовым в 1900 году и продавалась как головоломка Katzenjammer . ^[4] Головоломка была воссоздана Францем Оуэном Армбрустером, также известным как Фрэнк Армбрустер , и независимо опубликована издательствами Parker Brothers и Pressman в 1967 году. Только компанией Parker Brothers было продано более 12 миллионов головоломок. Головоломка похожа или идентична множеству других головоломок. ^[5]^[6] (например, «Великий Тантализатор» , около 1940 года, и самое популярное имя до «Мгновенного безумия »).

Одна версия головоломки в настоящее время продается компанией Winning Moves Games USA.

Решение

Учитывая, что кубы уже раскрашены и что они имеют четыре различных цвета (красный, зеленый, синий, белый), мы попытаемся создать график, который дает четкое представление обо всех положениях цветов во всех кубах. Полученный граф будет содержать четыре вершины, по одной для каждого цвета, и мы пронумеруем каждое ребро от одного до четырех (по одному номеру для каждого куба). Если ребро соединяет две вершины (Красную и Зеленую) и число ребер равно трем, то это означает, что третий куб имеет Красную и Зеленую грани, противоположные друг другу.

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

Итак, если у нас есть два ориентированных подграфа, мы фактически можем представить все четыре грани (которые имеют значение) всех четырех кубов.

Первый ориентированный граф будет представлять переднюю и заднюю грани.
Второй ориентированный граф будет представлять левую и правую грани.

Мы не можем случайным образом выбрать любые два подграфа — так каковы критерии выбора?

Нам нужно выбрать графики такие, что:

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

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

Верхний подграф позволяет получить цвета левой и правой граней соответствующего куба. Например:

Сплошная стрелка от красного к зеленому говорит, что у первого куба красный цвет будет на левой стороне, а зеленый — на правой.
Пунктирная стрелка от синего к красному говорит, что у второго куба на левой грани будет синий, а на правой — красный.
Пунктирная стрелка от белого к синему говорит, что у третьего куба на левой грани будет белый, а на правой — синий.
Штрихпунктирная стрелка от зеленого к белому говорит, что у четвертого куба на левой грани будет зеленый, а на правой — белый.

Нижний подграф позволяет получить цвета передней и задней грани соответствующего куба. Например:

Сплошная стрелка от белого к синему говорит, что у первого куба белая лицевая сторона и синяя задняя.
Пунктирная стрелка от зеленого к белому говорит, что у второго куба на передней грани будет зеленый цвет, а на задней — белый.
Пунктирная стрелка от синего к красному говорит, что у третьего куба на передней грани будет синий, а на задней — красный.
Пунктирная стрелка от красного к зеленому говорит, что у четвертого куба красный цвет будет на передней грани, а зеленый — на задней.

На третьем изображении показан производный стек куба, который является решением проблемы.

Важно отметить, что:

Вы можете произвольно маркировать кубы, так как одно такое решение отобразит еще 23, поменяв местами кубы, но не изменив их конфигурации.
Два направленных подграфа могут взаимозаменяемо представлять направление спереди назад и слева направо, т. е. один из них может представлять направление спереди назад или слева направо. Это потому, что одно такое решение также визуализирует еще 3 просто путем вращения. Добавив эффект в 1., мы создадим еще 95 решений, предоставив только одно. Для сравнения: такие четыре куба могут генерировать 24 ³ × 3 = 41472 конфигурации.
Не важно обращать внимание на верх и низ стопки кубиков. ^[7]

Обобщения

Учитывая n кубов, грани каждого из которых окрашены в один из n цветов, определение возможности сложить кубики так, чтобы каждый цвет появлялся ровно один раз на каждой из 4 сторон стопки, является NP-полным . ^[8]^[9]

Игра «Складывание кубов» — это версия этой головоломки для двух игроков. Учитывая упорядоченный список кубиков, игроки по очереди добавляют следующий кубик на вершину растущей стопки кубиков. Проигравшим становится первый игрок, который добавит кубик, в результате которого на одной из четырех сторон стопки цвет повторится более одного раза. Робертсон и Манро ^[10] доказал, что эта игра является PSPACE-полной , что иллюстрирует наблюдение о том, что NP-полные головоломки имеют тенденцию приводить к PSPACE-полным играм.

Ссылки

^ Кости дьявола
^ Кнут, DE (1975), "Оценка эффективности программ с возвратом", Math. Комп. , 29 (129): 132–136, doi : 10.1090/S0025-5718-1975-0373371-6
^ https://habrahabr.ru/post/336858/ (на русском языке)
^ Патент США № 646,463.
^ Слокам; Ботерманс (1986), Головоломки старые и новые , с. 38
^ «Страница головоломок Роба — головоломки с узорами» . Архивировано из оригинала 22 октября 2007 г. Проверено 12 августа 2007 г.
^ Билер, Р.; Мгновенное безумие: дополнительный материал для введения в теорию графов ; Депр. факультет математики и статистики, Государственный университет Восточного Теннесси; Джонсон-Сити, Теннесси: 2017 г.
^ Гэри, MR; Джонсон, Д.С. (1979), Компьютеры и трудноразрешимость: руководство по теории NP-полноты , WH Freeman, p. 258 (проблема GP15);
^ Робертсон, Э.; Манро, И. (1978), «NP-полнота, головоломки и игры», Util. Математика. , 13 : 99–116 .
^ Робертсон, Эдвард; Манро, Ян (1978). «NP-полнота, головоломки и игры». Утилитас Математика . 13 : 99–116.

Слокам; Ботерманс (1987), Старые и новые головоломки , Сиэтл: Вашингтонский университет Press, стр. 38, ISBN 0-295-96579-7

[1] Кости дьявола

[2] Кнут, DE (1975), "Оценка эффективности программ с возвратом", Math. Комп. , 29 (129): 132–136, doi : 10.1090/S0025-5718-1975-0373371-6

[3] ttps://habrahabr.ru/post/336858/ (на русском языке)

[4] Патент США № 646,463.

[5] Слокам; Ботерманс (1986), Головоломки старые и новые , с. 38

[6] «Страница головоломок Роба — головоломки с узорами» . Архивировано из оригинала 22 октября 2007 г. Проверено 12 августа 2007 г.

[7] Билер, Р.; Мгновенное безумие: дополнительный материал для введения в теорию графов ; Депр. факультет математики и статистики, Государственный университет Восточного Теннесси; Джонсон-Сити, Теннесси: 2017 г.

[8] Гэри, MR; Джонсон, Д.С. (1979), Компьютеры и трудноразрешимость: руководство по теории NP-полноты , WH Freeman, p. 258 (проблема GP15);

[9] Робертсон, Э.; Манро, И. (1978), «NP-полнота, головоломки и игры», Util. Математика. , 13 : 99–116 .

[10] Робертсон, Эдвард; Манро, Ян (1978). «NP-полнота, головоломки и игры». Утилитас Математика . 13 : 99–116.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]