Пользователь
20,5
рейтинг
23 октября 2015 в 13:15

Разработка → ШишНашКи

image

Что тут? Математическая головоломка, немножко групповых перестановок, две задачи для узколобых и грань шутки. Beg your pardon, если эта головоломка придумана до меня и я жалкий невежа, вообразивший, что изобрел нечто новенькое. В случае лицензионной чистоты я нарекаю её ШишНашКи отныне и вовеки веков. Аминь.

По следам публикации


Человеческий гений в лице Mrrl решил задачу Бога в уме за 20 ходов.
Видео решения

Постановка задачи


Дана доска 4x4 клетки со случайно перемешанными числами от 1 до 16.

image
Случайный расклад

Перестановками необходимо упорядочить все клетки по возрастанию, начиная с верхнего левого угла доски. Перестановкой называется вращение любых 4 соседних клеток на пи/2, пи и минус пи/2.

Пример перестановки в математической записи (поворот на -пи нижнего правого угла):

 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16
 01 02 03 04 05 06 07 08 09 10 15 11 13 14 16 12

Головоломка чем-то напоминает Кубик Рубика, но есть нюансы. Нет групп симметрии (я не буду вдаваться в подробности математической теории КР). И любой из 16! раскладов решается. Эту теорему достаточно легко доказать, решив задачу номер 1.

Задача номер 1


Найдите комбинацию перестановок, меняющих местами две голубые клетки.

image
Расклад задачи номер 1

Ответ для тупых
-U-M-L+U+L


Задача номер 2


Найти число Бога для этой головоломки. Число Бога — это минимальное число ходов, с помощью которых решается любой расклад. Например, для Кубика Рубика, в 2008 году это число было 23, а ныне — уже 20. Проблему решили перебором всех раскладов. Моя задача попроще, но также не сахар: 16 — не хрен собачий, скажите спасибо, что автор не выбрал доску 5x5.

Я решил, что наихудший расклад из всех возможных — полная инверсия доски. В этом случае каждую клетку надо тянуть через все поле.

image
Начальный наихудший расклад

Несколько помучившись и стартовав от числа Бога=39, я дошел до 30.

image
Фейковая таблица рекордов в достижении числа Бога

Думаю, на Хабре есть пара человек, которые найдут число Бога, равное 25. Ну хорошо, хорошо, Mrrl, не два, а три человека.

Кто хочет поиграться на iPhone, игра готова для бесплатного тестирования. С Вас — apple id.
Вадим Башуров @PapaBubaDiop
карма
971,5
рейтинг 20,5
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (25)

  • 0
    Хорошо бы видео с геймплеем добавить. А так интересно, я бы поиграл.
    • 0
      Ссылка на видео во втором предложении статьи)
      ШишНашКи
  • +3
    Что-то для перевёрнутой доски у меня получилось 20.
    Я правильно понимаю, что поворот на пи - это один ход?
    (A1 A3 C1 C3 B22)4

    Думаю, что есть гораздо более сложные ситуации (перевёрнутая доска с несколькими парами переставленных клеток?)
    • 0
      Что-то сложно для меня, АБС — это колонки, 123 — строки?

      Инверсионный расклад, возможно и не самый сложный.
      • +2
        Да, 9 центров названы как клетки шахматной доски.
        • 0
          Это гениально. Как ты решил?
          • +4
            В уме :) Сначала придумал, как лучше поставить на место углы, потом сообразил, что для остального этот метод тоже подходит.
  • 0
    Когда-то давным-давно Gamos сделал паззл с картинками про Колумба. Возможно, механика пригодится для новой игры.
  • +1
    Android когда ждать?
    Или традиционно «coming soon», а по факту – забудьте?
    • 0
      Не потяну я зеленого человечка, Вы уж сами…
  • +3
    Перестановкой называется вращение любых 4 соседних клеток на пи, 2*пи и минус пи.

    пи/2, пи и минус пи/2
    • +2
      Инфляция, все выросло в два раза, спасибо, исправлю.
  • +3
    Не такое красивое решение как у Mrrl, но в те же 20 ходов и тоже в уме
    Все повороты строго на Пи:

    A1A3 B1B3 C1C3 A1A3 B1B3 A1A3 A2C2 A1C1 A3C3 A2C2
    • 0
      Как вы это делаете? Видимо и кубик Рубика собираете не послойно и быстрее минуты.
      • 0
        Не послойно — только через подгруппы… это даёт мало поворотов, но получается долго
  • +2
    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 (и то, и другое решается полным анализом графа переходов)
    • 0
      Напиши статью. Полный анализ графа переходов — это численное решение?
      • 0
        Там нет ни одного вещественного числа — значит, комбинаторное.
        Написать статью я думал ещё про решение Bricks2048. Даже картинки подготовил. Но тогда (в мае) руки не дошли, а сейчас уже забыл половину.
        А решение шишнашек в нынешнем виде на статью не тянет. Основное достижение там — быстрое вычисление порядкового номера перестановки 12 элементов и восстановление перестановки по номеру.
        • 0
          Нечестно оставлять нас без сладкого!
          Хорошо, на самом деле у меня есть обобщенная игра, где меняется не только размер доски (4х4, 5х5, 6х6 — далее палец не влазит в размер экрана), но и группы вращения.
          Самое зубодробительное — вращение матрицы 3х3 вокруг её центральной клетки. То есть в случае доски 4х4 — лишь 4 срединные клетки являются кликабельными, сиречь центрами вращения. И я пока не уверен, что все расклады сходятся.
          • 0
            Ну как же там могут сходиться все расклады? Мало того, что поворот матрицы 3*3 — чётная перестановка, так ещё и все числа остаются на клетках своего цвета. Для доски 4*4 там не более 8!^2/2=812851200 раскладов. Думаю, что программа сможет её полностью проанализировать за несколько минут. Правда, сейчас она занята тем, что доказывает, что 16 — наилучшее решение для перевёрнутой доски.
            • 0
              Я неправильно сформулировал- 3х3 матрица не вращения, а преобразования. Клетки переходят друг в друга по периметру.
              • 0
                Тогда любой расклад решается.
                Сначала, вращая два противоположных кольца (5 и 11), переставляем по циклу плитки 2, 10, 7 — примерно за 10 ходов, хотя наверняка можно быстрее. Потом поворачиваем кольцо 10 (11 переходит в 7), и прокручиваем тот же цикл обратно. Получается цикл 10,7,11 — последовательные элементы на одном кольце. Три таких цикла (в разных положениях) в сочетании с поворотом всего кольца дают транспозицию (около 70 ходов), которой достаточно, чтобы сделать всё, что угодно.
                Если разрешены повороты только на 90 гр, то диаметр графа — 12 ходов (причём на этом расстоянии только две комбинации, к сожалению, не знаю, какие).
    • 0
      Программа доказала: для этого расположения 16 ходов — минимум.
  • 0
    Напоминает SWEEKEND из Microsoft Games, только там пиктограммы были всякие вместо циферок.
  • 0
    Готов к тестированию!)
    e.rtishchev@gmail.com

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.