ШишНашКи

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

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

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

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

Перестановками необходимо упорядочить все клетки по возрастанию, начиная с верхнего левого угла доски.
Перестановкой называется вращение любых 4 соседних клеток на пи, 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

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

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

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

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

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

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

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

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

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

Кто хочет поиграться на iPhone, игра готова для бесплатного тестирования. С Вас — apple id.

ссылка на оригинал статьи http://habrahabr.ru/post/269391/