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

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



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

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

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

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


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



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



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



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



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



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



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

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







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



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







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



Хэши


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

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



И только хэш:



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



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

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


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



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

Comments 24

    +5
    Что то есть напоминающее Конвеевскую жизнь? НЕТ?
      0
      Да, есть такое. Только правила расчёта производного поля другие.
        +3
        И то и другое — клеточные автоматы
          +4
          Или ожившие QR-коды :)
          0
          Еще, было бы, любопытно взглянуть на алгоритм решения.
            +3
            Да, собственно, ничего особенного. Поле предоставляется в виде 1-мерного бинарного вектора X длины n x n. Задача — получить те клетки поля, которые при ходе в них сделают его нулевым.

            Далее, рассмотрим для примера поле 3x3. У нас есть изначальная конфигурация X и 9 возможных ходов.

            Как можно записать ход в клетку (1, 1), например? Он выглядит так:

            image

            А как одномерный вектор он будет записан так:
            [1]
            [1]
            [0]
            [1]
            [0]
            [0]
            [0]
            [0]
            [0]

            Аналогично можно представить ходы во все остальные клетки. Обозначим их через a11...a33

            Теперь о решении. Если, например, решением являются клетки (1, 2) и (3, 2), то математически решение запишется в виде:

            a12 + a32 = X.

            Более развёрнуто:

            0*a11 + 1*a12 + 0*a13 + 0*a21 + 0*a22 + 0*a23 + 0*a31 + 1*a32 + 0*a33 = X.

            Или в матричном виде:

            [ a11 a12 a13 a21 a22 a23 a31 a32 a33]*b = X

            Покороче:
            Ab = X.

            Наше искомое решение — это b. Решив эту систему бинарных линейных уравнений, мы получим вектор, состоящий из единиц и нулей. Если в эту клетку нужно сделать ход, то на её месте в векторе будет 1, если нет — то 0.

            Для больших размерностей всё аналогично. Вот тут всё описывается на примере 5x5.

            Ну и да, для некоторых размерностей у матрицы A ранг меньше, чем её размер, т.е. решение существует не всегда.
              0
              А как решая матрицу, получить координаты решения?
              Или это итерационный процесс и из шага итерации получим конкретную клетку?
                0
                Ну, допустим, мы решили систему линейных уравнений и получили вектор b. Допустим, что у нас размер 3x3. Тогда
                      [ b11 ]
                      [ b12 ]
                      [ b13 ]
                      [ b21 ]
                b = [ b22 ]
                      [ b23 ]
                      [ b31 ]
                      [ b32 ]
                      [ b33 ]

                Ну вот, если bij = 1, то ход в клетку (i, j) содержится в решении. Если bij = 0, то нет.
            +1
            Красиво. Нужно сделать online реализацию на JavaScript.
              0
              Лучше в виде ночника irl.
                0
                Будильника… Пока не решишь, он не заткнется.
                0
                Я думал об этом, кстати. Но руки так и не дошли. Зато непрерывную версию я писал уже на JS(всё равно без решалки, ни один человек из тех, что я спрашивал, не знает в принципе о возможности решения).
                +1
                Получился клёвый генератор ковров.
                Только цвета добавить по кадрам и как-то смешивать их.
                  0
                  Цвет должен зависеть от кол-ва инверсий клетки. Клетка 2 раза зажглась — цвет поменялся и т.д.
                  0
                  А если сделать модицикацию, которая зажигает различные фигуры, как в тетрисе, в случайном порядке, то математически решение уже навряд ли можно будет найти и головоломка становится гораздо интереснее.
                    +2
                    В емаксе есть эта игра, правда на ограниченном поле (M-x 5x5). И присутствует также возможность рассчитать решение:
                    Скрин
                    Кружками отмечены поля, которые нужно активировать, чтобы выиграть
                    image

                      0
                      Когда играл еще только в демку Myst IV, в камине был дощечка, на которой квадраты переключались таким образом. Уж не помню, сколько времени потратил, но таки смог «перекрасить ее».
                      Настоящее решение, если не играли, не читайте
                      И так обидно было —
                      на всякий случай :)
                      такая изящная загадка была,
                      ну все, это последний рубеж, пеняйте на себя
                      а всего-то нужно было включить светильники…


                        0
                        Странно, что никто не вспомнил про это: i.imgur.com/ffH82gF.jpg
                          0
                          Колобки! :)
                            0
                            Да, это Братья Пилоты. :)
                            www.ag.ru/games/pilot-brothers-po-sledam-polosatogo-slona
                              0
                              У меня с детства комикс сохранился — приключения колобков, называется! :)
                          0
                          В криптографии тоже не применить, потому что очень легко подобрать начальные данные, дающие данный хэш
                          а если брать случайную матрицу А(случаи когда нет обратной можно использовать как одностороннюю функцию)
                            +1
                            Объясните, пожалуйста, что вы называете решением.
                            Решение — это же последовательность переключений клеток.
                              +1
                              порядок значения не имеет, сложение по модулю 2 коммутативно и ассоциативно

                            Only users with full accounts can post comments. Log in, please.