* Crossposted in RU.ALGORITHMS

Hi, Vlad !

Replying to a message of Vlad Koshelev to All:

 VK> В игрульке сабж есть такая задачка: имеется сейф, содержащий 4x4
 VK> ручек,

Занумеруем его поля так

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

И будем смотреть на поле как на граф с 16-ю вершинами, в котором ребрами
соединены те вершины, у которых соответствующие им клетки находятся либо в
одной
строке, либо в одном столбце.

 VK> каждая из которых может принимать одно из 2-х состояний:
 VK> повернута вертикально или горизонтально. Требуется перевести все
 VK> ручки в горизонтальное положение, причем, поворачивая ручку (i, j),
 VK> все ручки строки i и столбца j меняют свое состояние на
 VK> противоположное. Алгоритм: горизонтальные ручки представляем, как 0,
 VK> вертикальные - 1.

Соответственно, каждому положению будет соответствовать 16-тимерный вектор с
элементами из кольца Z_2={0,1}.
Пусть B - вектор-столбец соотвествующий начальному состоянию, E - конечному (к
которому мы хотим привести сейф; в данном случае E=(0,0,0,...,0)).
Тогда решение задачи сводится к отысканию решения уравнения
A*X+B=E
над кольцом Z_2, где X - неизвестный вектор-столбец (соответствующий поворотам
ручек), а A - матрица смежности графа. В нашем случае

    [1,1,1,1,1,0,0,0,1,0,0,0,1,0,0,0]
    [1,1,1,1,0,1,0,0,0,1,0,0,0,1,0,0]
    [1,1,1,1,0,0,1,0,0,0,1,0,0,0,1,0]
    [1,1,1,1,0,0,0,1,0,0,0,1,0,0,0,1]
    [1,0,0,0,1,1,1,1,1,0,0,0,1,0,0,0]
    [0,1,0,0,1,1,1,1,0,1,0,0,0,1,0,0]
    [0,0,1,0,1,1,1,1,0,0,1,0,0,0,1,0]
    [0,0,0,1,1,1,1,1,0,0,0,1,0,0,0,1]
A = [1,0,0,0,1,0,0,0,1,1,1,1,1,0,0,0]
    [0,1,0,0,0,1,0,0,1,1,1,1,0,1,0,0]
    [0,0,1,0,0,0,1,0,1,1,1,1,0,0,1,0]
    [0,0,0,1,0,0,0,1,1,1,1,1,0,0,0,1]
    [1,0,0,0,1,0,0,0,1,0,0,0,1,1,1,1]
    [0,1,0,0,0,1,0,0,0,1,0,0,1,1,1,1]
    [0,0,1,0,0,0,1,0,0,0,1,0,1,1,1,1]
    [0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,1]

В нашем случае она невырождена, поэтому решение можно записать в виде
X=A^{-1}*(E-B)
Кстати, в нашем случае A^{-1}=A (напоминаю, что все действия производятся по
mod 2), поэтому решение выглядит так
X=A*(E-B)

 VK> Бежим по полученной матрице и проверяем суммы
 VK> элементов строки i и столбца j (элемент (i, j) включается в общую
 VK> сумму один раз). Если сумма нечетна, ручку (i, j) переворачиваем. Так
 VK> за один проход задача решена. То есть

 VK> 1 0 1 1                                                     1 0 1 1
 VK> 0 1 0 0 Обрабатываем (1, 1) (нумерация с 0) => Сумма = 3 => 1 0 1 1
 VK> 1 1 0 1                                                     1 0 0 1
 VK> 0 1 0 1                                                     0 0 0 1
     ^^^^^^^ соотвественно, если мы примем это состояние за начальное, т.е.
B=(1,0,1,1,0,1,0,0,1,1,0,1,0,1,0,1), то решение получится

X = (0,0,1,1,1,1,0,0,0,1,0,1,0,0,1,0), что означает, что поворачивать надо
ручки с номерами 3,4,5,6,10,12,15:

- - X X
X X - -
- X - X
- - X -

Это, так сказать, была идея общего решения подобных задач. Теперь ответ на твой

 VK> ВОПРОС: Hа чем основан алгоритм? Откуда его можно вывести?

Hазовем клетку(ручку) "нечетной", если сумма всех чисел, стоящих с ней в одной
строке или столбце нечетна. Соответственно, твой алгоритм состоит в поворотах
"нечетных" ручек. Hетрудно видеть, что при таком повороте ручка перестает быть
"нечетной", а все остальные ручки сохраняют свою "четность". Поэтому с каждым
поворотом число "нечетных" ручек уменьшается на 1 и в конце концов становится
равным 0. Hу и последнее наблюдение: состояние без "нечетных" ручек только одно

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Что и требовалось доказать.

 VK> Замечания: простой перебор дает 16! ≈ 4 млрд. вариантов;

Hеправда на самом деле их всего 2^16 (каждую ручку можно повернуть или нет;
двойной поворот=отсутвие оного; повороты разных ручек перестановочны между
собой), а это лишь 65536 вариантов.

 VK> ЗЫ. А что делать, если у ручек k состояний? 8|

Все то же самое, только вычисления надо делать над кольцом Z_k={0,1,2,...,k-1}
(то есть по mod k).

Regards,      ° °
        Max    ~