Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 25
Хорошо бы видео с геймплеем добавить. А так интересно, я бы поиграл.
Ссылка на видео во втором предложении статьи)
ШишНашКи
ШишНашКи
Что-то для перевёрнутой доски у меня получилось 20.
Думаю, что есть гораздо более сложные ситуации (перевёрнутая доска с несколькими парами переставленных клеток?)
Я правильно понимаю, что поворот на пи - это один ход?
(A1 A3 C1 C3 B22)4
Думаю, что есть гораздо более сложные ситуации (перевёрнутая доска с несколькими парами переставленных клеток?)
Перестановкой называется вращение любых 4 соседних клеток на пи, 2*пи и минус пи.
пи/2, пи и минус пи/2
Не такое красивое решение как у Mrrl, но в те же 20 ходов и тоже в уме
Все повороты строго на Пи:
A1A3 B1B3 C1C3 A1A3 B1B3 A1A3 A2C2 A1C1 A3C3 A2C2
A1A3 B1B3 C1C3 A1A3 B1B3 A1A3 A2C2 A1C1 A3C3 A2C2
16 ходов. Но это уже с помощью программы.
C1^2 C2^2 C3^2 B1^2 B2^2 B3^2 A1^2 A3^2 C1^2 C3^2 B3^2 B2^2 C3^2 B1^2 C2^2 C1^2
Число Бога не превосходит 21: за 9 ходов можно из любого положения поставить на место нижний ряд, а потом за 12 решить оставшийся прямоугольник 3*4 (и то, и другое решается полным анализом графа переходов)
C1^2 C2^2 C3^2 B1^2 B2^2 B3^2 A1^2 A3^2 C1^2 C3^2 B3^2 B2^2 C3^2 B1^2 C2^2 C1^2
Число Бога не превосходит 21: за 9 ходов можно из любого положения поставить на место нижний ряд, а потом за 12 решить оставшийся прямоугольник 3*4 (и то, и другое решается полным анализом графа переходов)
Напиши статью. Полный анализ графа переходов — это численное решение?
Там нет ни одного вещественного числа — значит, комбинаторное.
Написать статью я думал ещё про решение Bricks2048. Даже картинки подготовил. Но тогда (в мае) руки не дошли, а сейчас уже забыл половину.
А решение шишнашек в нынешнем виде на статью не тянет. Основное достижение там — быстрое вычисление порядкового номера перестановки 12 элементов и восстановление перестановки по номеру.
Написать статью я думал ещё про решение Bricks2048. Даже картинки подготовил. Но тогда (в мае) руки не дошли, а сейчас уже забыл половину.
А решение шишнашек в нынешнем виде на статью не тянет. Основное достижение там — быстрое вычисление порядкового номера перестановки 12 элементов и восстановление перестановки по номеру.
Нечестно оставлять нас без сладкого!
Хорошо, на самом деле у меня есть обобщенная игра, где меняется не только размер доски (4х4, 5х5, 6х6 — далее палец не влазит в размер экрана), но и группы вращения.
Самое зубодробительное — вращение матрицы 3х3 вокруг её центральной клетки. То есть в случае доски 4х4 — лишь 4 срединные клетки являются кликабельными, сиречь центрами вращения. И я пока не уверен, что все расклады сходятся.
Хорошо, на самом деле у меня есть обобщенная игра, где меняется не только размер доски (4х4, 5х5, 6х6 — далее палец не влазит в размер экрана), но и группы вращения.
Самое зубодробительное — вращение матрицы 3х3 вокруг её центральной клетки. То есть в случае доски 4х4 — лишь 4 срединные клетки являются кликабельными, сиречь центрами вращения. И я пока не уверен, что все расклады сходятся.
Ну как же там могут сходиться все расклады? Мало того, что поворот матрицы 3*3 — чётная перестановка, так ещё и все числа остаются на клетках своего цвета. Для доски 4*4 там не более 8!^2/2=812851200 раскладов. Думаю, что программа сможет её полностью проанализировать за несколько минут. Правда, сейчас она занята тем, что доказывает, что 16 — наилучшее решение для перевёрнутой доски.
Я неправильно сформулировал- 3х3 матрица не вращения, а преобразования. Клетки переходят друг в друга по периметру.
Тогда любой расклад решается.
Сначала, вращая два противоположных кольца (5 и 11), переставляем по циклу плитки 2, 10, 7 — примерно за 10 ходов, хотя наверняка можно быстрее. Потом поворачиваем кольцо 10 (11 переходит в 7), и прокручиваем тот же цикл обратно. Получается цикл 10,7,11 — последовательные элементы на одном кольце. Три таких цикла (в разных положениях) в сочетании с поворотом всего кольца дают транспозицию (около 70 ходов), которой достаточно, чтобы сделать всё, что угодно.
Если разрешены повороты только на 90 гр, то диаметр графа — 12 ходов (причём на этом расстоянии только две комбинации, к сожалению, не знаю, какие).
Сначала, вращая два противоположных кольца (5 и 11), переставляем по циклу плитки 2, 10, 7 — примерно за 10 ходов, хотя наверняка можно быстрее. Потом поворачиваем кольцо 10 (11 переходит в 7), и прокручиваем тот же цикл обратно. Получается цикл 10,7,11 — последовательные элементы на одном кольце. Три таких цикла (в разных положениях) в сочетании с поворотом всего кольца дают транспозицию (около 70 ходов), которой достаточно, чтобы сделать всё, что угодно.
Если разрешены повороты только на 90 гр, то диаметр графа — 12 ходов (причём на этом расстоянии только две комбинации, к сожалению, не знаю, какие).
Программа доказала: для этого расположения 16 ходов — минимум.
Напоминает SWEEKEND из Microsoft Games, только там пиктограммы были всякие вместо циферок.
Готов к тестированию!)
e.rtishchev@gmail.com
e.rtishchev@gmail.com
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
ШишНашКи