Lights Out и её необычные применения

в 9:19, , рубрики: Занимательные задачки, картинки, красивые узоры, математика

Наверное, некоторые из вас слышали о такой головоломке, как Lights Out. Если кто-то не знает, суть вкратце такова: имеется поле из n x n клеток, часть клеток «включена», часть «выключена». При нажатии на клетку все клетки в области креста переключат своё состояние. Примерно так:

Lights Out и её необычные применения - 1 Lights Out и её необычные применения - 2

Собственно, задача — сделать все клетки поля «выключенными». Под катом кое-что интереснее, чем просто решение.

Сам алгоритм решения довольно нудный и объяснять его здесь долго. Вкратце — для поля каждого размера существует бинарная матрица A всех возможных ходов. Если представить изначальное поле в виде бинарного вектора X, то решение поля b — это решение системы бинарных линейных уравнений Ab = X. Нетрудно догадаться, что можно обратить матрицу A, сохранить её в переменной и находить решение уже любого поля по формуле b = A[sup]-1[/sup]X. Если кто-то хочет почитать подробнее, то здесь есть потрясающая статья, описывающая все нюансы. Мы двигаемся дальше.

К слову, решение существует не всегда для любой размерности. Размеры 5x5 или 17x17, например, решение имеют не всегда и в этой статье мы их не рассматриваем.

Генерация паттернов

Рассмотрим для примера следующее поле 20x20:

Lights Out и её необычные применения - 3

А теперь давайте посмотрим на его решение:

Lights Out и её необычные применения - 4

Красиво, правда? Давайте увеличим размер (и выключим границы, а то от них рябит в глазах). Возьмём, например, 75x75:

Lights Out и её необычные применения - 5

И посмотрим на его решение:

Lights Out и её необычные применения - 6

Довольно красиво. Но давайте не мелочиться, а сразу возьмём 150x150:

Lights Out и её необычные применения - 7

И его решением будет… Ух ты.

Lights Out и её необычные применения - 8

Завораживает. Издалека похоже на план города. Или на древнегреческую мозаику. Или на туркменский ковёр. Только почему-то зелёный.

А что будет, если попробовать получить решение для решения? Получим ещё один узор, производный. А потом можно сделать так ещё раз и получить ещё один производный узор.

Lights Out и её необычные применения - 9

Lights Out и её необычные применения - 10

Lights Out и её необычные применения - 11

При этом рано или поздно узоры зацикливаются. Для разных размеров разные периоды, при этом для чётных полей период больше, чем для нечётных (6x6 и 7x7, на больших размерах период уже в несколько сотен минимум):

Lights Out и её необычные применения - 12 Lights Out и её необычные применения - 13

При этом любой производный узор сохраняет любую осевую отражательную симметрию (анимации не зациклены, в зацикленной версии должно быть 2045 кадров):

Lights Out и её необычные применения - 14

Lights Out и её необычные применения - 15

Lights Out и её необычные применения - 16

Помимо отражательной, производный паттерн также способен сохранять и вращательную симметрию:

Lights Out и её необычные применения - 17

Хэши

Помимо паттернов, Lights Out можно использовать как медленную, криптографически нестойкую (из-за детерминистичности), но экзотическую хэш-функцию.

Как именно её считать? Ну, например, если считать всё поле начальным значением, то можно использовать в качестве хэша первые два столбца второго производного поля. Главную задачу хэш-функции они сохраняют — при небольшом изменении в начальных данных хэш меняется заметно. Вот, посмотрите сами:

Lights Out и её необычные применения - 18 Lights Out и её необычные применения - 19

И только хэш:

Lights Out и её необычные применения - 20 Lights Out и её необычные применения - 21

Без анимации, чтобы заметить различие:

Lights Out и её необычные применения - 22 Lights Out и её необычные применения - 23

Где это можно применять? Ну, наверное, нигде. Для контрольных сумм он слишком медленный. В криптографии тоже не применить, потому что очень легко подобрать начальные данные, дающие данный хэш. Зато необычно.

Скрытие данных

Последнее применение — это скрытие данных внутри поля. Можно нарисовать на поле что-нибудь, затем несколько раз вычислить производный узор и выложить куда-нибудь. А благодаря цикличности изначально зашифрованное поле рано или поздно покажет себя. Вот пример (осторожно, гифка в 252 кадра). Если что, данные на 9-м кадре:

Lights Out и её необычные применения - 24

Приложение с исходниками на codeplex. К сожалению, пока есть версия только для Windows.

Автор: Sixshaman

Источник

Поделиться новостью

* - обязательные к заполнению поля