Лабиринт на сетке N на N квадратных ячеек определяется путем указания того, является ли каждое ребро стеной или нет стеной. Все внешние края - стены. Одна ячейка определяется как начало , а одна ячейка определяется как выход , а выход доступен с самого начала. Начало и выход никогда не являются одной и той же ячейкой.
Обратите внимание, что ни начало, ни выход не должны находиться на внешней границе лабиринта, так что это правильный лабиринт:
Строка «N», «E», «S» и «W» указывает на попытку перемещения на север, восток, юг и запад соответственно. Ход, заблокированный стеной, пропускается без движения. Строка выходит из лабиринта, если применение этой строки с начала приводит к достижению выхода (независимо от того, продолжается ли строка после достижения выхода).
Вдохновленный этим загадочным вопросом, для которого xnor предоставил доказуемый метод решения с очень длинной строкой, напишите код, который может найти единственную строку, которая выходит из любого лабиринта 3 на 3.
За исключением недопустимых лабиринтов (начало и выход из одной и той же ячейки или выход, недоступный из начала), существует 138 172 действительных лабиринта, и строка должна выходить из каждого из них.
Срок действия
Строка должна удовлетворять следующему:
- Он состоит только из символов «N», «E», «S» и «W».
- Он выходит из любого лабиринта, к которому он применяется, если он запущен в начале.
Поскольку набор всех возможных лабиринтов включает в себя каждый возможный лабиринт с каждой возможной действительной начальной точкой, это автоматически означает, что строка выйдет из любого лабиринта из любой действительной начальной точки. То есть из любой начальной точки, из которой возможен выход.
выигрыш
Победителем является ответ, который предоставляет самую короткую действительную строку и включает код, использованный для ее создания. Если несколько ответов содержат строку с самой короткой длиной, побеждает первый, кто отправит эту строку.
пример
Вот пример строки длиной 500 символов, чтобы дать вам что-то, что можно превзойти:
SEENSSNESSWNNSNNNNWWNWENENNWEENSESSNENSESWENWWWWWENWNWWSESNSWENNWNWENWSSSNNNNNNESWNEWWWWWNNNSWESSEEWNENWENEENNEEESEENSSEENNWWWNWSWNSSENNNWESSESNWESWEENNWSNWWEEWWESNWEEEWWSSSESEEWWNSSEEEEESSENWWNNSWNENSESSNEESENEWSSNWNSEWEEEWEESWSNNNEWNNWNWSSWEESSSSNESESNENNWEESNWEWSWNSNWNNWENSNSWEWSWWNNWNSENESSNENEWNSSWNNEWSESWENEEENSWWSNNNNSSNENEWSNEEWNWENEEWEESEWEEWSSESSSWNWNNSWNWENWNENWNSWESNWSNSSENENNNWSSENSSSWWNENWWWEWSEWSNSSWNNSEWEWENSWENWSENEENSWEWSEWWSESSWWWNWSSEWSNWSNNWESNSNENNSNEWSNNESNNENWNWNNNEWWEWEE
Спасибо orlp за пожертвование.
Leaderboard
Равные баллы перечислены в порядке их размещения. Это не обязательно порядок, в котором ответы были опубликованы, так как оценка для данного ответа может со временем обновляться.
судья
Вот валидатор Python 3, который принимает строку NESW в качестве аргумента командной строки или через STDIN.
Для недопустимой строки это даст вам наглядный пример лабиринта, для которого он не подходит.
источник
Ответы:
C ++,
979593918683828179 символовМоя стратегия довольно проста - алгоритм эволюции, который может увеличивать, уменьшать, менять элементы и изменять действительные последовательности. Моя логика эволюции теперь почти такая же, как у @ Sp3000, так как он был лучше моего.
Однако моя реализация логики лабиринта довольно изящна. Это позволяет мне проверить, действительны ли строки на скорости волдырей. Попробуйте выяснить это, посмотрев на комментарий
do_move
иMaze
конструктор.источник
do_move
сейчас безумно быстро.Python 3 + PyPy,
8280 символовЯ не решался опубликовать этот ответ, потому что я в основном принял подход orlp и сделал свой собственный поворот. Эта строка была найдена, начиная с псевдослучайного решения длины 500 - было пробовано довольно много семян, прежде чем я смог побить текущую запись.
Единственная новая важная оптимизация заключается в том, что я смотрю только на одну треть лабиринтов. Две категории лабиринтов исключены из поиска:
<= 7
квадратики достижимыИдея состоит в том, что любая строка, которая решает остальные лабиринты, должна также автоматически решать вышеописанное. Я убежден, что это верно для второго типа, но это определенно не верно для первого типа, поэтому вывод будет содержать некоторые ложные срабатывания, которые необходимо проверять отдельно. Эти ложные срабатывания обычно пропускают всего около 20 лабиринтов, поэтому я подумал, что это будет хороший компромисс между скоростью и точностью, а также даст струнам немного больше передышки для мутирования.
Сначала я прошел длинный список эвристик поиска, но никому из них не удалось придумать ничего лучше, чем 140 или около того.
источник
0
чтобыn
по пути , и предположим , что строкаS
получает вас от0
кn
. ЗатемS
также доставит вас из любой промежуточной клеткиc
вn
. Предположим иначе. Позвольтеa(i)
быть позиции послеi
шагов, начиная с0
иb(i)
начиная сc
. Затемa(0) = 0 < b(0)
каждый шаг изменяетсяa
и неb
более чем на 1, иa(|S|) = n > b(|S|)
. Возьми самый маленькийt
такой, чтоa(t) >= b(t)
. Ясно,a(t) != b(t)
иначе они будут синхронизированы, поэтому они должны поменяться местами, шагаяt
в одном направлении.C ++ и библиотека от lingeling
Используя подход, основанный на SAT , я мог бы полностью решить аналогичную проблему для лабиринтов 4x4 с заблокированными ячейками вместо тонких стен и фиксированными начальными и выходными положениями в противоположных углах. Поэтому я надеялся, что смогу использовать те же идеи для этой проблемы. Однако, хотя для другой проблемы я использовал только 2423 лабиринта (в то время как было замечено, что 2083 достаточно), и он имеет решение длины 29, в кодировании SAT использовались миллионы переменных, и для его решения потребовались дни.
Поэтому я решил изменить подход двумя важными способами:
Я также провел некоторые оптимизации, чтобы использовать меньше переменных и предложений модулей.
Программа основана на @ orlp. Важным изменением стал выбор лабиринтов:
is_solution
проверяет, все ли достижимые позиции достигнуты.Таким образом, я получаю в общей сложности 10772 лабиринта со стартовыми позициями.
Вот программа:
Во- первых ,
configure.sh
и решателя, а затем скомпилировать программу с чем - то вроде , где есть путь , где соответственно. есть, так что оба могут, например, быть . Или просто поместите их в тот же каталог и обойтись без параметров и .make
lingeling
g++ -std=c++11 -O3 -I ... -o m3sat m3sat.cc -L ... -llgl
...
lglib.h
liblgl.a
../lingeling-<version>
-I
-L
Программа принимает один обязательный аргумент командной строки, строка , состоящая из
N
,E
,S
,W
(для фиксированных направлений) или*
. Таким образом, вы можете найти общее решение размера 78, указав строку 78*
с (в кавычках), или найти решение, начинающееся сNEWS
,NEWS
после чего укажите столько*
s, сколько вы хотите для дополнительных шагов. В качестве первого теста возьмите ваше любимое решение и замените некоторые буквы на*
. Это быстро находит решение для удивительно высокого значения «некоторые».Программа скажет, какой лабиринт он добавляет, описывается структурой стены и начальным положением, а также даст количество доступных мест и стен. Лабиринты сортируются по этим критериям, и добавляется первый нерешенный. Поэтому большинство добавленных лабиринтов есть
(9/4)
, но иногда появляются и другие.Я взял известное решение длиной 79 и для каждой группы из 26 смежных букв попытался заменить их любыми 25 буквами. Я также попытался удалить 13 букв из начала и конца и заменить их на любые 13 в начале и любые 12 в конце, и наоборот. К сожалению, все вышло неудовлетворительно. Итак, можем ли мы принять это как показатель того, что длина 79 является оптимальной? Нет, я также попытался улучшить решение длины 80 до длины 79, и это также не увенчалось успехом.
Наконец, я попытался объединить начало одного решения с концом другого, а также с одним решением, преобразованным одной из симметрий. Теперь у меня заканчиваются интересные идеи, поэтому я решил показать вам, что у меня есть, хотя это не привело к новым решениям.
источник