Я действительно люблю скользящие мозаичные головоломки, но в последнее время у меня не было времени на них. Следовательно, мне нужна программа, чтобы дать мне исправление головоломок со скользящей плиткой, в частности головоломок Клоцкого.
Ваш вклад будет в следующем формате:
#######
#001gg#
##.222#
.######
где #
представляет стены, .
представляет открытую область, g
представляет цель, а соседние числа представляют различные блоки. Вы можете предположить, что:
- Там будет не более 10 блоков
- Там не будет двух блоков с одинаковым номером
- Все блоки будут обнесены стенами
- Сетка прямоугольная
0
Блок достаточно большой , чтобы охватить все гола квадратов.- Есть правильное решение
Вам необходимо вернуть последовательность ходов, которая поместит 0
блок так, чтобы он охватывал все квадраты ворот. Блоки не могут проходить через стены или другие блоки. Для вышеупомянутой загадки соответствующая последовательность будет
2L,1R,1R,1D,0R,0R,0R
в то время как представляет перемещение 2
блока 1 на квадрат влево, 1
блок 2 на квадрат вправо (сверху цели), затем на 1 квадрат вниз, а затем на 0
3 квадрата вправо.
На самом деле есть несколько последовательностей, которые будут работать для вышеуказанной проблемы, и создание любой из них приемлемо. Ваше решение должно быть оптимальным, а это означает, что оно должно создавать последовательность, которая решает головоломку за как можно меньшее количество шагов.
Последовательность должна быть распечатана, как указано выше, но может быть разделена запятой, новой строкой или пробелом. Мне все равно, есть ли запятые или пробелы. Вы должны произвести вывод за разумное время (максимум 120 секунд на загадки ниже).
Головоломка 1:
..####..
..#00#..
###00###
#......#
#.1122.#
##3124##
.#3344#.
.##55##.
..#gg#..
..####..
Головоломка 2:
######
#1002#
#1002#
#3445#
#3675#
#8gg9#
######
Головоломка 3:
.####.
##1g##
#22g3#
#4255#
#4.56#
#.006#
#7008#
######
Головоломка 4:
.####.
##00##
#.00g#
#.0.1#
#..g2#
######
Это код-гольф, поэтому выигрывает самое короткое (в байтах) решение!
источник
Ответы:
Питон, 1761
Отчасти сгорел в этом вопросе, поэтому не мог заставить себя играть в гольф. В любом случае, на данный момент это единственное решение, которое решает все в течение срока (самый длинный, № 3, занимает 27 секунд).
источник
JavaScript (ES6), 446
388Поиск в ширину, поэтому первое найденное решение является самым коротким.
Хотя я все еще думаю, что это хорошее решение, этого недостаточно. Даже после проверки миллионов позиций (время выполнения несколько минут), я не смог найти решение для примера 2 и 3.
Отредактируйте модифицированную версию ES6, чтобы преодолеть ограничение по времени выполнения JavaScript. Головоломка 3 решается за 7 минут, 145 шагов. Головоломка 2 решена за 10 минут, 116 шагов
Изменить 2 Большое ускорение, используя идею @ orlp считать равными любые два блока с одинаковой формой (исключая специальный блок '0'). Это уменьшает пространство посещаемых позиций во время BSF. Например, для головоломки 2 любая позиция с замененным блоком 1,2,3 или 5 действительно одинакова.
Время: самая длинная головоломка 3 ~ 20 секунд на моем ноутбуке.
Используйте Firefox, чтобы поиграть с новым JsFiddle для тестирования.
Устаревшие
EcmaScript 6 (FireFox) JSFiddleEcmaScript 5 (Chrome) JSFiddleпример
Головоломка 1
Головоломка 2
Головоломка 3
Головоломка 4
источник