Доброго времени суток!

Была такая игрушка, когда-то в детстве сталкивался: link
Там ввиду того, что вертикаль и горизонталь были чётные, всё было просто
На сколько я помню, выписывал не правильные положения, нажимал их и, если эта операция не приводила к правильному ответу, повторял ещё раз
Так максимум за 2 итерации решалось произвольная матрица с чётными сторонами.
Алго было получено изучением способа инвертирования одной позиции и применения его ко всем не правильным
Это довольно быстро и просто для человека, но скорее всего не оптимально, т.к. при таком подходе приходится нажимать на те же позиции по несколько раз, а это "пустые ходы", которые ни к чему не приводят

Интересует развитие алгоритма:
1. Как математически определить существует ли решение вообще?
2. Как решить за минимальное количество ходов?
3. Как изменится алгоритм, если стороны могут быть как чётными, так и не чётными
4. Как подойти к алго, если на поле появятся преграды?

Для начала интересует пункты 1-3... И как эта задача вообще выражается математически?
Пункт 4 думаю не получится описать формулой и хоть частично придётся прибегать к бруту?

Это сообщение отредактировал(а) Isaev - 12.11.2014, 14:34

по-моему, нужно заметить некоторые закономерности и пользоваться ими

закономерность 1:
выберем 2 строки и 2 столбца
щёлкая по 1 разу по клеткам в их пересечении развернём только эти 4 клетки

закономерность 2:
выберем 2 строки и 1 столбец
щёлкая по 1 разу по клеткам в их пересечении развернём 6 клеток -- в выбранных строках и оставшихся 3 столбцах

Далее, используя эти две закономерности можно развернуть любые две клетки в одном столбце
Тоже самое можно делать с любыми двумя клетками в одной строке
А с учётом того, что щелчок по клетке разворачивает 7 клеток, теперь можно 6 из них развернуть обратно и научиться разворачивать одну произвольную клетку

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


Проработай изменение чётности всего поля при однократном перевороте.
Проработай отдельно чётности столбцов и строк.
Учти, что в конечной позиции они должны быть равны чётности строки/столбца/поля по всем чётностям.
Это позволит увидеть некоторые закономерности и в частности возможность существования нерешаемой начальной позиции.

Lipetsk, закономерности это тоже больше для визуального решения, а не для математики
Наверняка решение можно свести к матрицам или к решению системы уравнений с Х неизвестными


Это ясно, но подход не оптимален, как мне кажется... Хотя нужно иметь несколько идей, чтобы было что тестировать по скорости


вот смысла этой фразы не уловил

Найдите более оптиальный.


Обозначьте, например, горизонтальное положение нулём, а вертикальное единицей. Посчитайте суммарную чётность столбца, строки, всего поля. Если позиция - не конечная, то в этом наборе минимум 2 элемента отличаются от набора для конечно позиции.

А вы думаете, что решений, в которых каждая клетка не нажимается повторно (нажимается 0 или 1 раз), может быть несколько?


Это сообщение отредактировал(а) Lipetsk - 12.11.2014, 08:52

Если решения различать в т.ч. и по порядку нажатия - да, иначе нет.

но от порядка нажатия результат не меняется!
здесь каждый набор нажатых клеток соответствует уникальному изменению поля, и порядок не важен

Я с прицелом на 

Потому как непонятно, что разумеется под "преградами". Это вполне может оказаться стенка, разрушающаяся при первом флипе сквозь неё.

[deleted]

Это сообщение отредактировал(а) Isaev - 12.11.2014, 14:34

Логично, второй пункт нужно вычеркнуть, не подумавши написал

Я о том, что повторные нажатия должны отсеиваться на этапе решения, а не составлением всех возможных нажатий и отсеиванием дублей


Под преградой подразумевается Клетка имеющая значение отличное от 0 и 1, например 2
И инвертирование происходит до сталкновения с ней и не дальше
Пример в аттаче
т.ч. в принципе решение всегда одно


Это сообщение отредактировал(а) Isaev - 12.11.2014, 14:40

Присоединённый файл ( Кол-во скачиваний: 6 )
 beisp.png 2,51 Kb

Такая преграда не разрушает независимости решения от порядка ходов.

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

В общем случае для решения задачи необходимо выполнить поиск решения системы битовых уравнений. Количество уравнений и переменных равно количеству клеток, переменные битовые - область значений переменных ограничивается множеством {0;1}. Система либо имеет решение, либо нет.

Посидел вечерок порисовал)
Пришёл к следующим выводам:
а. При четных сторонах матрицы за 1 ход инвертируется не чётное кол-во позиций
    потому мы можем всегда добиться изменения 1 позиции ---> решение есть всегда.
б. Если одна из сторон не чётная, за 1 ход инвертируется четное количество позиций
    и изменения 1 позиции мы достигнуть не можем никак!
   Вместо этого можем менять по 2 (вроде любые 2 на выбор, если ничего не просмотрел)
   т.е. если кол-во не правильных положений изначально не чётное ---> решений нет

когда обе стороны не четные, пока не разобрался к какому случаю относится