Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 24
Что то есть напоминающее Конвеевскую жизнь? НЕТ?
Еще, было бы, любопытно взглянуть на алгоритм решения.
Да, собственно, ничего особенного. Поле предоставляется в виде 1-мерного бинарного вектора X длины n x n. Задача — получить те клетки поля, которые при ходе в них сделают его нулевым.
Далее, рассмотрим для примера поле 3x3. У нас есть изначальная конфигурация X и 9 возможных ходов.
Как можно записать ход в клетку (1, 1), например? Он выглядит так:
А как одномерный вектор он будет записан так:
[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 ранг меньше, чем её размер, т.е. решение существует не всегда.
Далее, рассмотрим для примера поле 3x3. У нас есть изначальная конфигурация X и 9 возможных ходов.
Как можно записать ход в клетку (1, 1), например? Он выглядит так:
А как одномерный вектор он будет записан так:
[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 ранг меньше, чем её размер, т.е. решение существует не всегда.
Красиво. Нужно сделать online реализацию на JavaScript.
Лучше в виде ночника irl.
Я думал об этом, кстати. Но руки так и не дошли. Зато непрерывную версию я писал уже на JS(всё равно без решалки, ни один человек из тех, что я спрашивал, не знает в принципе о возможности решения).
Получился клёвый генератор ковров.
Только цвета добавить по кадрам и как-то смешивать их.
Только цвета добавить по кадрам и как-то смешивать их.
А если сделать модицикацию, которая зажигает различные фигуры, как в тетрисе, в случайном порядке, то математически решение уже навряд ли можно будет найти и головоломка становится гораздо интереснее.
В емаксе есть эта игра, правда на ограниченном поле (M-x 5x5). И присутствует также возможность рассчитать решение:
Скрин
Кружками отмечены поля, которые нужно активировать, чтобы выиграть
Когда играл еще только в демку Myst IV, в камине был дощечка, на которой квадраты переключались таким образом. Уж не помню, сколько времени потратил, но таки смог «перекрасить ее».
Настоящее решение, если не играли, не читайте
И так обидно было —
на всякий случай :)
такая изящная загадка была,
ну все, это последний рубеж, пеняйте на себя
а всего-то нужно было включить светильники…
Странно, что никто не вспомнил про это: i.imgur.com/ffH82gF.jpg
В криптографии тоже не применить, потому что очень легко подобрать начальные данные, дающие данный хэша если брать случайную матрицу А(случаи когда нет обратной можно использовать как одностороннюю функцию)
Объясните, пожалуйста, что вы называете решением.
Решение — это же последовательность переключений клеток.
Решение — это же последовательность переключений клеток.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Lights Out и её необычные применения