@Sixshaman10 апр 2015 в 09:19

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

2 мин

23K

Занимательные задачкиМатематика *

Из песочницы

+33

Комментарии 24

@GarryC 10 апр 2015 в 09:57

Что то есть напоминающее Конвеевскую жизнь? НЕТ?

@Sixshaman 10 апр 2015 в 10:37

Да, есть такое. Только правила расчёта производного поля другие.

@bask 10 апр 2015 в 10:54

И то и другое — клеточные автоматы

@Jeffry_Choser 10 апр 2015 в 10:58

Или ожившие QR-коды :)

@Jeffry_Choser 10 апр 2015 в 10:59

Еще, было бы, любопытно взглянуть на алгоритм решения.

@Sixshaman 10 апр 2015 в 11:40

Да, собственно, ничего особенного. Поле предоставляется в виде 1-мерного бинарного вектора X длины n x n. Задача — получить те клетки поля, которые при ходе в них сделают его нулевым.

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

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

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

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

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

a₁₂ + a₃₂ = X.

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

0*a₁₁ + 1*a₁₂ + 0*a₁₃ + 0*a₂₁ + 0*a₂₂ + 0*a₂₃ + 0*a₃₁ + 1*a₃₂ + 0*a₃₃ = X.

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

[ a₁₁ a₁₂ a₁₃ a₂₁ a₂₂ a₂₃ a₃₁ a₃₂ a₃₃]*b = X

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

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

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

Ну и да, для некоторых размерностей у матрицы A ранг меньше, чем её размер, т.е. решение существует не всегда.

@Jeffry_Choser 10 апр 2015 в 18:55

А как решая матрицу, получить координаты решения?
Или это итерационный процесс и из шага итерации получим конкретную клетку?

@Sixshaman 10 апр 2015 в 21:09

Ну, допустим, мы решили систему линейных уравнений и получили вектор b. Допустим, что у нас размер 3x3. Тогда
      [ b₁₁ ]
      [ b₁₂ ]
      [ b₁₃ ]
      [ b₂₁ ]
b = [ b₂₂ ]
      [ b₂₃ ]
      [ b₃₁ ]
      [ b₃₂ ]
      [ b₃₃ ]

Ну вот, если b_ij = 1, то ход в клетку (i, j) содержится в решении. Если b_ij = 0, то нет.

@Lerg 10 апр 2015 в 11:18

Красиво. Нужно сделать online реализацию на JavaScript.

@artoym 10 апр 2015 в 11:33

Лучше в виде ночника irl.

@lolmaus 10 апр 2015 в 11:43

Будильника… Пока не решишь, он не заткнется.

@Sixshaman 10 апр 2015 в 11:50

Я думал об этом, кстати. Но руки так и не дошли. Зато непрерывную версию я писал уже на JS(всё равно без решалки, ни один человек из тех, что я спрашивал, не знает в принципе о возможности решения).

@SHVV 10 апр 2015 в 12:30

Получился клёвый генератор ковров.
Только цвета добавить по кадрам и как-то смешивать их.

@Jeffry_Choser 10 апр 2015 в 18:57

Цвет должен зависеть от кол-ва инверсий клетки. Клетка 2 раза зажглась — цвет поменялся и т.д.

@NeoNN 10 апр 2015 в 13:37

А если сделать модицикацию, которая зажигает различные фигуры, как в тетрисе, в случайном порядке, то математически решение уже навряд ли можно будет найти и головоломка становится гораздо интереснее.

@bromzh 10 апр 2015 в 15:12

В емаксе есть эта игра, правда на ограниченном поле (M-x 5x5). И присутствует также возможность рассчитать решение:

Скрин

Кружками отмечены поля, которые нужно активировать, чтобы выиграть

@Mingun 10 апр 2015 в 17:51

Когда играл еще только в демку Myst IV, в камине был дощечка, на которой квадраты переключались таким образом. Уж не помню, сколько времени потратил, но таки смог «перекрасить ее».

Настоящее решение, если не играли, не читайте

И так обидно было —

на всякий случай :)

такая изящная загадка была,

ну все, это последний рубеж, пеняйте на себя

а всего-то нужно было включить светильники…