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