Аналитическое решение квеста из игры "Братья-пилоты"

Здравствуйте уважаемые форумчане!

Начну немного издалека.
Однажды, когда моя младшая сестрёнка заинтересовалась квестами, я вспомнил об игре "Братья Пилоты: По следам полосатого слона", в которую мы играли в 199.. каком-то году (боже, я такой старый? Ужас :)). Вобщем, раскопал, поставил, посидели, посмеялись, поиграли...

Теперь суть.
В этой игре есть задача по взлому холодильника - надо повернуть все ручки в горизонтальное положение, чтоб он открылся. Естессно поворачиваются они с подвохом, (для тех кто не знаком с игрой см. систему ниже). Ну, в то время, все мои друзья (и я конечно) решали задачку методом "научного тыка" и шибко не заморачивались. Но вот я снова столкнулся с этим холодильником. Уже такой взрослый, большой, небритый, с инженерным дипломом и профессией слесаря-сборщика (да, так бывает, увы).

И одолел меня вот какой вопрос: а имеет ли описанная задача аналитическое решение? Поскольку я увлекаюсь кодингом, алгоритмическое решение я себе вполне представляю. А вот как сформулировать проблему математическим языком, и самое главное какими методами её можно (и можно ли) решить - не представляю совершенно. Из той каши в голове, что осталась от институтского курса вышки сварить ничего не получается.

Как Вы понимаете, конкретное решение для описанной игры мне не нужно. Мне просто интересна сама возможность аналитического решения и указание на математический аппарат для этого.

Описание задачи (ежели чего упустил сильно не бейте:))
Дано:
1. Дана квадратная матрица (размерность, в обобщённом случае любая, в игре - 4х4)
2. Элементы матрицы могут принимать только два значения (ну, пусть ноль или еденица)
3. Начальное состояние элементов матрицы - произвольное
4. Изменение значения одного из элементов, влечёт изменение значений элементов в ряду и столбце содержащих изменяемый элемент (отмечу, цепной реакции тут нет. Т.е. наведённые изменения в столбце и ряду не вызывают последующих изменений).
Данное изменение элемента (вместе с наведенными изменениями) назовём ходом.

Собственно, требуется: привести все элементы матрицы в одинаковое состояние (т.е. все нули или все еденицы) за конечное (но не ограниченное) число ходов, с указанием порядка сделанных ходов (неважно, номера это будут элементов, или множество индексов).


Собственно вот как-то так. Если дочитали пост до конца - уже спасибо! :)
Буду рад если кто-нибудь заинтересуется и ответит.
Удачи всем!

Если учесть, что каждое "тыкание" приводит к инверсии строго заданной группы элементов, то приходим к двум выводам:
1) порядок этих "тыканий" неважен;
2) "тыкать" два раза в один и тот же элемент бессмысленно.
Из чего, в свою очередь, можно сделать вывод, что эта задача может быть решена не более чем за n^2 "тыканий", где n - порядок матрицы. Это позволяет представить решение рассматриваемой задачи в виде вектора фиксированной размерности, n^2 элементов которого могут принимать значения 1 - "тыкать" и 0 - не "тыкать" в соответствующий элемент исходной матрицы.
В таком виде задача имеет конечное число вариантов решений (2^(n^2)), может рассматриваться как комбинаторная (см. "Комбинаторика") и решаться методами комбинаторной оптимизации. Некоторые задачи комбинаторной оптимизации могут быть сведены к виду задач линейного программирования, а именно: целочисленного линейного программирования. Рассматриваемая же задача сводится к частному случаю целочисленного линейного программирования - булевскому программированию.

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

Цитата
zklb (Дмитрий)
неверно. важен порядок и тыкать можно в один и тот же элемент более одного раза.

Если Вас не затруднит, то приведите, пожалуйста, контрпример, демонстрирующий ошибочность моих выводов.

да, был не прав) беру слова обратно.

Здравствуйте!

Спасибо всем кто заинтересовался.
Все Ваши суждения лично мне кажутся вполне логичными.
Но, если я правильно понял, речь идёт о построении оптимизированного (с учётом Ваших выводов и суждений), но всё-таки алгоритма перебора? А другие варианты возможны? Т.е., например, если (и возможно ли?) зависимость изменения элемента от связанных с ним элементов выразить некоторой функцией, то можно ли свести задачу к системе каких-либо уравнений? Или подобный класс задач в принципе не решается другими методами?

Цитата
daun
Здравствуйте!

Спасибо всем кто заинтересовался.
Все Ваши суждения лично мне кажутся вполне логичными.
Но, если я правильно понял, речь идёт о построении оптимизированного (с учётом Ваших выводов и суждений), но всё-таки алгоритма перебора? А другие варианты возможны? Т.е., например, если (и возможно ли?) зависимость изменения элемента от связанных с ним элементов выразить некоторой функцией, то можно ли свести задачу к системе каких-либо уравнений? Или подобный класс задач в принципе не решается другими методами?

Вы задали целый ряд вопросов, однозначные ответы на которые требуют либо уточнения самих вопросов, либо отдельного исследования. Попытаюсь это пояснить своими ответами, начав с конца.

> Или подобный класс задач в принципе не решается другими методами?

Этот вопрос очень близок к вопросу о равенстве/неравенстве классов P и NP. Ответ на него стоит $1 млн. Именно столько составляет премия за ответ на каждый из шести оставшихся вопросов тысячелетия (до Перельмана, доказавшего гипотезу Пуанкаре, их было семь).

> Т.е., например, если (и возможно ли?) зависимость изменения элемента от связанных с ним элементов выразить некоторой функцией, то можно ли свести задачу к системе каких-либо уравнений?

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

> Но, если я правильно понял, речь идёт о построении оптимизированного (с учётом Ваших выводов и суждений), но всё-таки алгоритма перебора?

В общем случае, да. Но Вы ведь интересовались областью математики и просили указать "традиционный" аппарат решения таких задач. Что есть, то есть.

> А другие варианты возможны?

Я не зря ранее отмечал, что очень часто для таких частных задач отыскиваются специализированные решения, которые превосходят то, что предлагает общий подход. Одно из таких решений, не требующих явного перебора всех вариантов, Вам предложил г-н brukvalub. Если дополнить предложенное решение осознанием того факта, что четное число раз тыкать в один и тот же элемент не имеет смысла, а любое количество нечетных тыканий эквивалентно одному тыканью, то получим вполне аналитическое решение: по одному разу ткнуть в каждый из тех элементов, для которых значение суммы нежелательных элементов по горизонтали и вертикали в исходной матрице нечетно. По виду, такое решение до некоторой степени похоже, например, на определение ранга матрицы, а вычислительно является даже более простым.

Большое спасибо всем Вам за ответы и потраченное время.

Всего Вам доброго!

вот до кучи решение задачи образца 1998 года:
http://groups.google.com/group/fido7.ru.math/browse_thread/thread/19a0a0210eda188/2d1a1cee2f70db5e