Задача про сейф
Предыстория
Когда-то давно, когда трава была зеленее и солнце ярче, играл я в “Братьев Пилотов”. И был там чудо-холодильник, который по совместительству выполнял роль сейфа. Чтобы его открыть, нужно было переключить все переключатели в положение “открыто”. Это было бы просто, если бы переключатели не были связаны между собой. Если нажать на один, то переключаются все переключатели в том же столбце и в той же строке.
Я всегда проходил эту головоломку “методом научного тыка”. Пока на первом курсе института нам не дали её на олимпиаде по программированию. Как оказалось, это чисто математическая задача про матрицы, которую “просто надо знать, как решать”. На олимпиаде я этого не знал, и попробовал решить её методом перебора, но не смог. Прошли годы и уже моя дочь играет в “Братьев Пилотов”, и я наконец решил эту задачу методом перебора на PHP :)
Задача
На игровом поле 4 на 4 клетки расположены переключатели, которые могут иметь два состояния 0 и 1. Переключение любого из переключателей приводит к переключению переключателей в том же столбце и той же строке. Начальное состояние игрового поля может задаваться заранее, либо выбираться случайным образом (через серию случайных переключений). Нужно написать скрипт, который бы методом перебора нашёл последовательную комбинацию переключений, которая бы приводила все переключатели в 0 или 1 (задаётся пользователем).
P.S.
Позднее я использовал решение этой задачи и для других головоломок. Метод перебора оказался очень эффективным решением для любых “связанных переключателей” в играх в стиле “поиск предметов”.
P.P.S.
Чтобы открыть сейф, нужно запомнить положение выключенных переключателей, а потом последовательно нажать на них. Потом опять запомнить положение выключенных переключателей и опять нажать на них. И так до тех пор, пока сейф не откроется и Коллега не назовёт вас “медвежатником”.