Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Flip-Game

Автор: Isaev 10.11.2014, 11:47

Доброго времени суток! Была такая игрушка, когда-то в детстве сталкивался: http://zbbucket.bitbucket.org/refrigerator-kineticjs/ Там ввиду того, что вертикаль и горизонталь были чётные, всё было просто На сколько я помню, выписывал не правильные положения, нажимал их и, если эта операция не приводила к правильному ответу, повторял ещё раз Так максимум за 2 итерации решалось произвольная матрица с чётными сторонами. Алго было получено изучением способа инвертирования одной позиции и применения его ко всем не правильным Это довольно быстро и просто для человека, но скорее всего не оптимально, т.к. при таком подходе приходится нажимать на те же позиции по несколько раз, а это "пустые ходы", которые ни к чему не приводят Интересует развитие алгоритма: 1. Как математически определить существует ли решение вообще? 2. Как решить за минимальное количество ходов? 3. Как изменится алгоритм, если стороны могут быть как чётными, так и не чётными 4. Как подойти к алго, если на поле появятся преграды? Для начала интересует пункты 1-3... И как эта задача вообще выражается математически? Пункт 4 думаю не получится описать формулой и хоть частично придётся прибегать к бруту?

Автор: Lipetsk 10.11.2014, 17:42

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

Автор: Akina 10.11.2014, 18:24

Цитата(Lipetsk @  10.11.2014,  18:42 ) по-моему, нужно заметить некоторые закономерности  Кому нужны закономерности в частной задаче? Коли уж на то пошло - то для инверсии одного выключателя надо переключить все выключатели в его строке и столбце, вклячая и его самого, по одному разу. Порядок неважен.  Для поиска оптимума надо подобрать все перевороты в любом порядке, и выбросить все парные. Цитата(Isaev @  10.11.2014,  12:47 ) 1. Как математически определить существует ли решение вообще? 3. Как изменится алгоритм, если стороны могут быть как чётными, так и не чётными Проработай изменение чётности всего поля при однократном перевороте. Проработай отдельно чётности столбцов и строк. Учти, что в конечной позиции они должны быть равны чётности строки/столбца/поля по всем чётностям. Это позволит увидеть некоторые закономерности и в частности возможность существования нерешаемой начальной позиции.

Автор: Isaev 11.11.2014, 12:03

Lipetsk, закономерности это тоже больше для визуального решения, а не для математики Наверняка решение можно свести к матрицам или к решению системы уравнений с Х неизвестными Цитата(Akina @  10.11.2014,  18:24 ) Для поиска оптимума надо подобрать все перевороты в любом порядке, и выбросить все парные. Это ясно, но подход не оптимален, как мне кажется... Хотя нужно иметь несколько идей, чтобы было что тестировать по скорости Цитата(Akina @  10.11.2014,  18:24 ) Учти, что в конечной позиции они должны быть равны чётности строки/столбца/поля по всем чётностям. вот смысла этой фразы не уловил

Автор: Akina 11.11.2014, 12:23

Цитата(Isaev @  11.11.2014,  13:03 ) подход не оптимален, как мне кажется...  Найдите более оптиальный. Цитата(Isaev @  11.11.2014,  13:03 ) смысла этой фразы не уловил  Обозначьте, например, горизонтальное положение нулём, а вертикальное единицей. Посчитайте суммарную чётность столбца, строки, всего поля. Если позиция - не конечная, то в этом наборе минимум 2 элемента отличаются от набора для конечно позиции.

Автор: Lipetsk 12.11.2014, 08:51

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

Автор: Akina 12.11.2014, 09:04

Цитата(Lipetsk @  12.11.2014,  09:51 ) вы думаете, что решений, в которых каждая клетка не нажимается повторно (нажимается 0 или 1 раз), может быть несколько? Если решения различать в т.ч. и по порядку нажатия - да, иначе нет.

Автор: Lipetsk 12.11.2014, 09:28

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

Автор: Akina 12.11.2014, 12:32

Цитата(Lipetsk @  12.11.2014,  10:28 )  от порядка нажатия результат не меняется Я с прицелом на  Цитата(Isaev @  10.11.2014,  12:47 ) 4. Как подойти к алго, если на поле появятся преграды? Потому как непонятно, что разумеется под "преградами". Это вполне может оказаться стенка, разрушающаяся при первом флипе сквозь неё.

Автор: Isaev 12.11.2014, 14:14

[deleted]

Автор: Isaev 12.11.2014, 14:33

Цитата(Lipetsk @ 12.11.2014,  08:51) А вы думаете, что решений, в которых каждая клетка не нажимается повторно (нажимается 0 или 1 раз), может быть несколько? Логично, второй пункт нужно вычеркнуть, не подумавши написал Я о том, что повторные нажатия должны отсеиваться на этапе решения, а не составлением всех возможных нажатий и отсеиванием дублей Цитата(Akina @  12.11.2014,  12:32 ) Я с прицелом на  Цитата(Isaev @  10.11.2014,  12:47 Найти цитируемый пост) 4. Как подойти к алго, если на поле появятся преграды? Под преградой подразумевается Клетка имеющая значение отличное от 0 и 1, например 2 И инвертирование происходит до сталкновения с ней и не дальше Пример в аттаче т.ч. в принципе решение всегда одно

Автор: Akina 12.11.2014, 14:59

Цитата(Isaev @  12.11.2014,  15:33 ) Под преградой подразумевается Клетка имеющая значение отличное от 0 и 1, например 2И инвертирование происходит до сталкновения с ней и не дальше Такая преграда не разрушает независимости решения от порядка ходов. Добавлено через 4 минуты и 59 секунд Для любого порядконезависимого решения можно сформулировать постулат - если решение существует, то существует единственное кратчайшее решение, в котором для каждой клетки производится либо ноль флипов, либо один. В общем случае для решения задачи необходимо выполнить поиск решения системы битовых уравнений. Количество уравнений и переменных равно количеству клеток, переменные битовые - область значений переменных ограничивается множеством {0;1}. Система либо имеет решение, либо нет.

Автор: Isaev 13.11.2014, 19:13

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)