все вы, вероятно, видели головоломку движущегося числа/картинки. Тот, где у вас есть цифры от 1 до 15 в сетке 4x4 и пытается получить их из случайной начальной позиции в
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
Моя подруга или некоторые из моих друзей, не являющихся программистами, могут решить эту проблему с помощью какой-то магической магии, которую они не могут мне объяснить. Я не могу решить головоломку.
Самый многообещающий подход, который я выяснил, состоит в том, чтобы решить первую строку, тогда я бы получил
1 2 3 4
X X X X
X X X X
X X X
затем первый столбец, не касаясь решенных ячеек
1 2 3 4
5 X X X
9 X X X
13 X X
а затем вторую строку в
1 2 3 4
5 6 7 8
9 X X X
13 X X
а затем второй столбец
1 2 3 4
5 6 7 8
9 10 X X
13 14 X
проблема заключается в том, что оставшиеся X (случайные) плитки иногда находятся в неразрешимой позиции, и это то, где мое решение терпит неудачу. Но я чувствую, что нахожусь на правильном пути.
Моя программа выполняет решение указанной строки/столбца, пытаясь получить номер X в указанную позицию, если не портить правильные ячейки. Но он не может делать последние 3 плитки на сетке 2x2. Что мне не хватает?
Вы определенно находитесь на правильном пути, но вместо того, чтобы решать по строке/столбцу итеративно до того, чтобы оставаться с 2x2, разрешите, пока у вас не будет минимум 3x3, а затем разрешите только эту сетку. 3x3 - это наименьший размер, необходимый для правильной переупорядочивания сетки (в то время как 2x2 не дает вам полной гибкости, которая вам может понадобиться, как вы уже говорили). Этот подход также масштабируется - вы можете решить 5x5, 10x10 и т.д.
Убедитесь, что ваша головоломка разрешима в первую очередь. Не все -.
В противном случае ваша стратегия выглядит здорово.
Этот сайт имеет приятное объяснение о сетках 3x3, вы, вероятно, могли бы легко расширить его до 4x4.
Я думаю, что наиболее эффективным способом решения этого вопроса является использование аддитивных паттернов с приемлемым эвристическим алгоритмом и алгоритмом IDA *. Как описано здесь - http://www.aaai.org/Papers/JAIR/Vol22/JAIR-2209.pdf. (Я думаю, что Фелнер сказал нам, что нашел способ, который является довольно хорошим, но я не помню точно, что это было (двунаправленный A *?), Но во всяком случае этого должно быть достаточно (-:).
В любом случае этот курс был давно, поэтому я рекомендую прочитать статью.
НТН. Будьте осторожны.
При уменьшении единственно возможный случай, который вы не можете решить, должен иметь форму 1 3 2 X
и вы хотите получить его в
1 2 3 X
используя дополнительную строку и столбец, вы можете переместить их в правильные позиции с помощью простой предварительно вычисленной последовательности
Стратегия решения, описанная оригинальным плакатом, всегда будет работать для стандартной разрешимой 15-головоломки. Если Axarydax может уменьшить 15-головоломку до состояния, описанного и все еще неспособного ее решить, то с самого начала было невозможно. Позвольте мне объяснить.
Если мы рассматриваем пустое место в головоломке как один из фрагментов, то каждый законный ход включает в себя замену пустой "плитки" для соседней плитки. Это позволяет рассматривать движения на головоломке как перестановки на 16 символов. То есть элементы симметричной группы S 16. Каждое примитивное перемещение является "свопом" или транспозицией между двумя элементами (одним из которых является пробел).
Поскольку головоломка начинается и заканчивается пустой плиткой в правом нижнем углу, пустая плитка должна двигаться ровно столько раз, чтобы головоломка была решена. (Это проще всего увидеть, представив наброшенный шаблон шахматной доски поверх головоломки - после нечетного количества перемещений пробел будет на другом цветовом квадрате.) Это означает, что принятое решение должно быть произведением равномерно много перестановок, поэтому он должен быть элементом чередующейся группы A 16, которая имеет ровно половину S 16. (Из 16! Перестановок S 16, 16!/2 перестановки четные, а 16!/2 нечетны. Более того, четный * четный = четный, четный * нечетный = нечетный и нечетный * нечетный = ровный.)
Если необходимая корректирующая перестановка оказывается нечетной, невозможно решить загадку, независимо от того, что вы делаете. Если необходимая корректирующая перестановка четная, и если Axarydax следует описанной стратегии, то перестановка, требуемая для оставшегося блока 2x2, обязательно будет четной перестановкой, фиксирующей пустой квадрат. Единственными четными перестановками только трех элементов являются вращения 1- > 2- > 3- > 1 (обозначение цикла (123)) и 1- > 3- > 2- > 1 (обозначение цикла (132)). Они легко выполняются на оставшихся четырех квадратах, не нарушая других.
Поскольку неправдоподобно, что Axarydax не может определить эти тривиальные решения блоков 2x2, я подозреваю, что либо он/она был взломан, либо 15-головоломка, пытающаяся каким-то образом нестандартна.
Всегда есть до 4 позиций перемещения из любого заданного. Интересно, достигнет ли простой алгоритм, который будет обрабатывать все варианты, построив дерево 2-4, в "разрешенную" позицию или переполнение стека:)