15 Puzzle - известная головоломка, включающая в себя перемещение 15 плиток по сетке 4x4. Начиная со случайной конфигурации, цель состоит в том, чтобы расположить плитки в правильном порядке. Вот пример решенной загадки 15:
01 02 03 04
05 06 07 08
09 10 11 12
13 14 15
Каждый ход головоломки имеет вид Вверх / Вниз / Влево / Вправо. Движение «Вниз» состоит из скольжения плитки внизу над пустым местом. Движение «Вправо» состоит из скольжения плитки вправо, в пустое место. Вот как выглядит доска после ходов Вниз и Вправо.
01 02 03 04
05 06 07 08
09 10 11
13 14 15 12
Цель этой задачи - написать программу, которая может выводить серию ходов, необходимых для решения 15 головоломок. Победителем становится программа, которая решает пять тестовых случаев (ниже) за наименьшее количество ходов. Сгенерированное решение не обязательно должно быть идеальным, оно просто должно быть лучше конкурентов. Для каждого отдельного теста программа не должна занимать более десяти секунд на подходящей машине.
Ваша программа должна быть способна решить любую головоломку, которую можно решить, я просто использую эти пять тестов в качестве оценки.
Ваша программа получит нерешенную головоломку 15 в качестве входных данных в формате 2D-массива. 2D-массив может быть отформатирован в соответствии с используемым языком или изменен, если в языке нет 2D-массивов. Первым элементом первого подмассива будет число в верхнем левом углу, а последним элементом первого подмассива будет число в верхнем правом углу. А 0
будет пустым пространством.
В качестве вывода ваша программа должна напечатать список ходов в том порядке, в котором они должны быть выполнены. Каждый шаг должен быть пронумерован, чтобы повысить удобство использования результатов.
РЕДАКТИРОВАТЬ: Основываясь на комментариях, я позволю выводу быть либо в форме Вниз / Вверх / и т. Д. Или в форме координат части для перемещения. Поскольку это не код гольф, наиболее важной частью является решение головоломки.
Некоторые другие общие правила не предусматривают использование внешнего источника и т. Д.
Тестовый пример 1
([5,1,7,3],[9,2,11,4],[13,6,15,8],[0,10,14,12])
Пример вывода:
1: Down
2: Down
3: Down
4: Left
....
Тестовый пример 2
([2,5,13,12],[1,0,3,15],[9,7,14,6],[10,11,8,4])
Тестовый пример 3
([5,2,4,8],[10,0,3,14],[13,6,11,12],[1,15,9,7])
Тестовый пример 4
([11,4,12,2],[5,10,3,15],[14,1,6,7],[0,9,8,13])
Тестовый пример 5
([5,8,7,11],[1,6,12,2],[9,0,13,10],[14,3,4,15])
Ответы:
PyPy, 195 ходов, ~ 12 секунд вычислений
Вычисляет оптимальные решения с использованием IDA * с эвристикой «шаговой доступности», дополненной линейными конфликтами. Вот оптимальные решения:
И код:
источник
JavaScript (ES6) всего шагов 329 для всех 5 тестов в течение ~ 1 минуты
редактировать ту же стратегию, разные цели, лучшее решение. Помедленнее ...
Это более или менее то, как я решаю это вручную: используя промежуточные цели. После каждой цели относительные плитки не перемещаются снова. Каждая промежуточная цель достигается с помощью параметрической функции BSF. 2 параметра - это условие цикла L (повторить, пока истина) и условие выбора S (выбрать, какую плитку можно переместить). Шаги:
Примечание: я не проверяю расположение плиток 14 и 15. Неразрешимые головоломки вроде
[11,4,12,2,,15,10,3,5,,14,1,6,7,,0,9,8,13]
14 и 15 поменялись местами.Откройте фрагмент для тестирования или игры (только Firefox)
Показать фрагмент кода
Набор тестов В консоли Firefox / FireBug
Выход
источник
Я начал работать над этой проблемой и хотел внести свой вклад в мой код до сих пор. Как заявил Гарет, проблема сравнима с головоломкой из 8 плиток, поэтому код основан на великолепном решении Кейта Рэндалла и, следовательно, на Python. Это решение может решить все 5 контрольных примеров с общей суммой менее 400 ходов, а также другие головоломки. Он содержит оптимизированное и грубое решение. Код сейчас немного раздут. Вывод сокращен как "llururd .." Надеюсь, что это полезно. http://www.penschuck.org/joomla/tmp/15Tile.txt (пояснение) http://www.penschuck.org/joomla/tmp/tile15.txt (код Python)
источник