Решите все лабиринты 4x4 одновременно с минимальными ходами

Ответ 1

Я закодировал эту проблему как SAT- проблему с 4280308 переменными и 21975717 предложениями (включая много избыточных, но, казалось бы, полезных), которые тригелинг решил примерно через 100 1/2 часов, найдя эту строку решения длиной 29:

RRDRRDRDLDLDULLDLDRDDURDRRDRR

Подобное вычисление пришло к выводу, что спустя почти 85 часов решение длины 28 не существует.

Вот быстрая и грязная программа на Haskell, которую я использовал для создания проблемы SAT:

import Data.List(tails,nub)
import Data.Bits
import Numeric(showHex)
import System.Environment(getArgs)

data Lit = Lit Bool [Char]

type Wall = Int -- [Bool]

lit s = Lit True s
litS s = lit (s "")

inv (Lit b s) = Lit (not b) s

instance (Show Lit) where
  showsPrec _ (Lit b s) = showString (if b then "" else "~") . showString s
  showList = showString . unwords . (map show)

showDir d = showChar ("NESW"!!d)
dir n d = litS $ showChar 'D' . shows n . showDir d

showStuff n s p = showHex n . showChar (['A'..]!!p) . shows s
pos n s p = litS $ showChar 'P' . showStuff n s p
posh n s p h = litS $ showDir h . showStuff n s p

opdir :: Int -> Int
opdir d = (d+2) 'mod' 4

(<-&) :: Lit -> [Lit] -> [[Lit]]
l <-& ls = lt : lf where 
  lt = l : map inv ls                   --      l or ~l1 or ~l2 ...
  lf = [ [ inv l, li ] | li <- ls ]     --      ~l or li , all i

(<-|) :: Lit -> [Lit] -> [[Lit]]
l <-| ls = lf : lt where 
  lf = (inv l) : ls                     --      ~l or l1 or l2 ...
  lt = [ [ l, inv li ] | li <- ls ]     --      l or ~li , all i

atmostone l = [ [inv a, inv b] | (a:bs) <- tails l, b <- bs ]

dirconds n = concat [ atmostone [ dir i d | d <- [0..3]]
                    | i <- [0..n-1] ]

boundary p = (p<5) || (p>24) || (p 'mod' 5 == 0)
positions = [ p | p<-[0..24], not (boundary p) ]
start = head positions
stop = last positions
wp = [ if boundary p then 0 else p - 4 - p 'div' 5 | p <- [0..23]]
       ++ [1,0,0,0,0,0]

wallat :: Wall -> Int -> Bool
wallat w p = testBit (4*w+1) (wp!!p) -- (True:False:w) !! (wp!!p)

jump:: Int -> Int -> Int
jump pos dir =  pos + ([-5,1,5,-1]!!dir)

freestep :: Wall -> Int -> Int -> Maybe Int
freestep w pos dir = let np = jump pos dir in 
           if wallat w np
              then Nothing
              else Just np

reach :: Wall -> Int -> [Int]
reach w p = [ np | Just np <- map (freestep w p) [0..3] ]

reachable :: Wall -> [Int]
reachable w = go [start] [start] where
                 go seen [] = seen
                 go seen front = let new = nub [ n | p <- front,
                                                     n <- reach w p,
                                                     n 'notElem' seen ]
                                 in go (seen++new) new

nicereachable :: Wall -> Maybe [Int]
nicereachable w =
  let r = reachable w
  in if and [ p 'elem' r || wallat w p | p <- positions]
       then Just r
       else Nothing

mazestepdirposconds w n p d =
  let ph = posh w (n+1) p d
      conds = case freestep w p d of
                (Just np) -> ph <-& [ pos w n np, dir n (opdir d) ]
                Nothing   -> ph <-& [ pos w n p, dir n d ]
  in (ph,conds)

mazestepposconds w n p =
  let cnds = map (mazestepdirposconds w n p) [0..3]
      ps = pos w (n+1) p
  in ( ps <-| (map fst cnds)) ++ (concatMap snd cnds)

mazestepconds w r n = concatMap (mazestepposconds w n) r

mazeconds w len r = [ pos w 0 start ] :
                    [ pos w i stop | i <- [6..len] ] :
                    (concat [ atmostone [ pos w s p | p <- positions ] 
                                          | s<-[0..len] ]) ++
                    (concatMap (mazestepconds w r) [0..len-1])

conds l = dirconds l ++ 
          concat [ mazeconds w l r |
                   (w,Just r) <- [(i,nicereachable i)|i<-[0..2^14-1]]]

main = do
         [n] <- getArgs
         mapM_ print $ conds (read n)

Он принимает один аргумент командной строки, целое число, указывающее длину строки решения. Выводом является проблема SAT CNF с одним предложением на строку, символическими литералами и тильдой для отрицания. Это формат, который Дональд Кнут использует для своих решателей SAT здесь. Я превратил это в более обычный формат DIMACS, используя его программу SAT-TO-DIMACS. Он написан на CWEB, поэтому вы должны превратить его в программу на C с помощью ctangle. Вам также понадобится gb_flip.w. Программа читает из stdin и записывает в stdout, и вы захотите дать ей такую опцию, как h20 чтобы увеличить размер хеш-таблицы.

Чтобы нарушить симметрию, я добавил блок D0E чтобы заставить первый шаг идти вправо. (Обратите внимание, что я использовал NESW вместо URDL, потому что ранее я читал об аналогичной проблеме, используя их в качестве указаний.)

Программа рассматривает все 2423 лабиринта, где каждая позиция либо достижима, либо стена. Как заметил @Hans_Olsson, достаточно рассмотреть только 2083 лабиринта, где каждая позиция является либо стеной, либо достижимой без прохождения цели. Чтобы оптимизировать программу так, чтобы она учитывала только эти лабиринты, добавьте p/= stop, после p <- front, в определении reachable.

Кодировка

(Я добавлю замечания, относящиеся к описанию того, что делает программа. Они могут быть проигнорированы, если вас интересует только кодировка.)

Пусть len будет длиной решения, которое мы ищем, пусть i будет целым числом с диапазоном 0<=i<=len (если не указано иное). Пусть m варьируется по всем рассматриваемым лабиринтам, а p по достижимым позициям конкретного лабиринта. Достижимые позиции включают значения start и stop для начальной позиции и цели. Пусть d колеблется по четырем возможным направлениям.

(Программа выводит m как шестнадцатеричное 14-битное число, кодирующее положения стенок, а p как заглавную букву. Она использует непостоянно имена переменных: n для m или для i или для len, w (стены) для m, s (шаг) для i, и в одном случае h (помощник) для d.)

Для каждого i<len и каждого d существует переменная D<i><d> указывающая, что шаг i -th решения должен идти в направлении d. (Программа создает их с помощью функции dir.)

Для каждого i0<len есть пункты, требующие, чтобы максимум одна из четырех переменных D<i0><d> была истинной.

Для каждого m, i и p существует переменная P<m><i><p> указывающая, что в лабиринте m в момент времени i достигается положение p. (Программа создает их с помощью функции pos.)

Для каждого лабиринта m0 существует единичное предложение P<m0><0><start> устанавливающее начальную позицию.

Для каждого m0 и i0 есть пункты, требующие, чтобы не более одной из переменных P<m0><i0><p> истинно (мы не можем находиться в двух разных позициях). Они избыточны, за исключением случая i0=0 (где они могут быть заменены единичными предложениями ~P<m0><0><p> для всех p!=start), но, похоже, помогают.

Переход от лабиринтов в момент времени i0 к моменту времени i0+1 соответствии с направлением, данным в D<i0><d>, описывается с помощью вспомогательных переменных. Для каждого m, i>0, p и d существует переменная P<m><i><p><d>. (Программа создает их с помощью posh функции. Она печатает их как <d><m><i><p>, чтобы длина имени переменной не превышала 8 символов, установленных программами Кнута.)

Идея состоит в том, что каждое направление дает возможную причину, по которой позиция может быть достигнута. Переменная указывает, что в лабиринте m в момент времени i позиция p достигается "из-за" d. Если мы рассмотрим движение в каком-то направлении, ударившись о стену и отскочив от нее как идущие с этого направления, то мы можем интерпретировать переменные как достижение этой позиции, исходя из направления d.

Итак, давайте рассмотрим некоторые фиксированные m, i<len, p и d. Как может P<m><i+1><p> быть верным из-за d? Если нет стены в направлении d (идущей от p), то, возможно, мы пришли оттуда; позвольте назвать эту позицию np. Если есть стена, то мы, возможно, были здесь раньше, пытались пойти туда и ударить стену.

Поэтому нам нужны пункты, устанавливающие, что P<m><i+1><p><d> эквивалентно соединению (логическому и) P<m><i><p'> и D<i><d'>, где p'=np и d' - противоположное направление d если стены нет, и p'=p и d'=d если стены нет. (Программа делает это в функции mazestepdirposconds.)

Тогда нам просто нужны предложения, устанавливающие, что для каждого m0, i0>0 и p0 переменная P<m0><i0><p0> эквивалентна дизъюнкции (логической или) четырех переменных P<m0><i0><p0><d>.

Наконец, нам нужно добавить условие, что лабиринты решены. Итак, для каждого лабиринта m0 нам понадобится предложение, требующее, чтобы одна из переменных P<m0><i><stop> была истинной. Поскольку лабиринт не может быть решен менее чем за 6 шагов, нам нужно только рассмотреть i>=6.

Ответ 2

Используя мета-алгоритм A * и С#, я нашел следующие 32 и 31 символьные последовательности (пока):

RRDRRDRLDRDLDLULLLDDRDDRDRURRDRD (32 characters)
RRDRRDRLDRDLDLULLLDDRDDRDURRDRRD (32 characters)
RRDRRDRLDRDLDLULLLDDRDDDURDRRDR (31 characters)

I разветвленный Olavi ideone с 31 символьной последовательностью, чтобы убедиться, что я не сделал никаких ошибок.

Что касается количества лабиринтов, я получаю 3828 действительных лабиринтов, используя алгоритм заполнения заливки.

Исходный код проекта С# и скомпилированный выпуск двоичный файл (в папке bin\release) в Google Диске.

Вы можете ввести начальную строку для поиска A * и максимальную длину поиска. Для кода была довольно оптимизация скорости, но все еще есть место для большего количества. Например, для каждого расширения он создает 4 экземпляра класса Candidate, создавая новые лабиринты, которые запускают каждый шаг старого кандидата, а затем 4 разных направления (слева, справа, вверх, вниз). С помощью метода Candidate.Clone() производительность может быть значительно улучшена, профайлер показывает текущую точку доступа именно там. Кроме того, пока нет многопоточности, и программа использует все больше и больше памяти для посещенного списка (около 2 ГБ через 10 минут на моем ПК). Обратите внимание: запуск программы внутри IDE замедляет ее даже в режиме освобождения, поэтому лучше начать ее снаружи.

Основной мета-алгоритм, который приводит к следующим выше последовательностям:

• A * найдите известную строку длины N с максимальной длиной M, удалив все больше символов с конца, например

  A * поиск RRDRRDRLDRDLDLULLLDDRDDRDRURRRDD (32 символа), M = 33

  A * поиск RRDRRDRLDRDLDLULLLDDRDDRDRURRRD (31 символ), M = 33

  A * поиск RRDRRDRLDRDLDLULLLDDRDDRDRURRR (30 символов), M = 33

  A * поиск RRDRRDRLDRDLDLULLLDDRDDRDRURR (29 символов), M = 33

  ...

• Как только будет найдена более короткая строка, чем N, используйте ее как новую максимальную длину для поиска A *, чтобы сделать ее быстрее и меньше памяти.

Фактические комбинации, которые я пробовал, можно увидеть в исходном коде, см. фрагмент кода ниже. Тайминги взяты из более старой неоптимизированной версии, и текущая версия должна быть примерно в 6 раз быстрее.

        //// 33 char solution
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURRRDDR", 33); // 33 chars, 00:00:00.0032911 Finished, 1 solution, best 33, visitedList length 0

        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURRRDD", 33); // 32 chars, 00:00:00.0308543 Finished, 1 solution, best 33, visitedList length 3
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURRRD", 33); // 31 chars, 00:00:00.0871429  Finished, 2 solutions, best 33, visitedList length 14
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURRR", 33); // 30 chars, 00:00:00.2536057  Finished, 2 solutions, best 33, visitedList length 49

        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURR", 33); // 29 chars, 00:00:01.0540762  Finished, 8 solutions, best 32, visitedList length 205
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRUR", 33); // 28 chars, 00:00:03.8993877  Finished, 7 solutions, best 32, visitedList length 771
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRU", 33); // 27 chars, 00:00:10.4225150  Finished, 7 solutions, best 32, visitedList length 2069
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDR", 33); // 26 chars, 00:00:24.2552908  Finished, 7 solutions, best 32 visitedList length 4484
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRD", 33); // 25 chars, 00:01:44.3295165  Finished, 14 solutions, best 32, visitedList length 16600
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDR", 33); // 24 chars, 00:16:18.6666045  Finished, 14 solutions, best 32, visitedList length 77106

        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURR", 32); // 29 chars, 00:00:00.3134699  Finished, 1 solution, best 32, visitedList length 66
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRUR", 32); // 28 chars, 00:00:01.1053798  Finished, 1 solution, best 32, visitedList length 238
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRU", 32); // 27 chars, 00:00:03.5172143  Finished, 1 solution, best 32, visitedList length 730
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDR", 32); // 26 chars, 00:00:07.1336796  Finished, 1 solution, best 32, visitedList length 1413
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRD", 32); // 25 chars, 00:00:26.4906874  Finished, 2 solutions, best 32, visitedList length 5084
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDR", 32); // 24 chars, 00:02:52.8134463  Finished, 2 solutions, best 32, visitedList length 24623
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDD", 32); // 23 chars, cancelled after 6 seconds, finds RRDRRDRLDRDLDLULLLDDRDDDURDRRDR (31 chars)

        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDD", 31); // 23 chars, 00:01:58.4861802  Finished, 1 solution, best 31, visitedList length 18835
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRD", 30); // 22 chars, 00:00:34.6602434  Finished, 0 solution, best distance 44, visitedList length 21084  
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDR", 30); // 21 chars, 00:04:32.2439241  Finished, 0 solution, best distance 44, visitedList length 78500
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDD", 30); // 20 chars, cancelled after 10 minutes, found no solution, best distance 44
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLD", 30); // 19 chars, cancelled after 10 minutes, found no solution, best distance 44

        //var aStarSearch = new AStarSearch("R", 29); // Complete search, would take waaay too long and consume much memory 

Ответ 3

Похоже, вы могли бы использовать A * search здесь, используя эвристику максимальной эвристики из всех лабиринтов. Это консервативно приближается к расстоянию до решения и, вероятно, даст разумный первый подход.

Поскольку все лабиринты малы, вы можете построить идеальную эвристику для каждого, запустив BFS в обратном направлении от конца каждого лабиринта, чтобы прекомпретировать расстояние от каждой точки до цели каждого лабиринта. Если вы кэшировали это в справочных таблицах, вы могли бы использовать эвристику для лабиринта, которая прекрасно сообщила вам о минимальном количестве ходов.

Я на самом деле не пробовал это, так что это остается экспериментально подтвержденным, но я думаю, что это будет отличная отправная точка для решения.

РЕДАКТИРОВАТЬ Я просто прочитал записку, в которой говорится, что каждый робот должен посещать цель хотя бы один раз и не обязательно заканчивать цель. В этом случае измените эвристику на максимальное расстояние от любого робота, который еще не достиг цели цели.

Надеюсь, это поможет!

Ответ 4

Несколько идей:

• Ни одна из подстрок RLR, LRL, UDU или DUD не может отображаться в любом оптимальном решении, поскольку в каждом лабиринте они оставляют робота в том же положении (если первое перемещение блокируется стена) или один шаг в направлении первого перемещения (иначе), который в каждом случае совпадает с результатом выполнения только первого перемещения в последовательности. То же самое относится к RRLLRR, LLRRLL и т.д. (И, вероятно, для всех более длинных шаблонов, хотя я еще не подтвердил это, и они дают уменьшающуюся отдачу с точки зрения обрезки поиска). [РЕДАКТИРОВАТЬ: Это не совсем правильно - оно применяется только в том случае, если ни один робот, который еще не достиг g, достигнет g во втором из трех ходов. Tricky]
• В любом действительном решении, если все Ds и Rs меняются местами, и все Ls и Us меняются местами, мы получаем другое действующее решение, так как это "перевернутое" решение разрешит все лабиринты, которые были "перевернуты" вокруг главной диагонали - это всего лишь набор всех лабиринтов. В результате мы должны рассмотреть только решения, в которых первым движением является, скажем, R.
• Один из способов продолжить поиск A * (или ветвь, связанный или полный список) заключается в записи на каждом node в дереве поиска состояния робота во всех допустимых лабиринтах ~ 4000. Но мы можем сэкономить немало времени и пространства , объединяя состояния всех лабиринтов, которые не могли быть выделены нашими ходами до сих пор. Мы можем сделать это, записав третье "неизвестное" состояние ячейки, *. Всякий раз, когда мы пытаемся сделать переход в ячейку *, это состояние разбивается на 2 под-состояния: состояние, в котором оно становится пустой ячейкой (и наш ход завершается успешно), и состояние, в котором оно становится стеной ( и мы остаемся в том же положении). Если выявление этой ячейки будет стеной, это означает, что уже невозможно достичь ячейки цели, тогда это под-состояние не генерируется.

Так, например, после попытки самого первого перемещения (R) полная информация о состоянии в дереве поиска node состоит из следующих двух частичных лабиринтов:

x # * *    . x * *
* * * *    * * * *
* * * *    * * * *
* * * g    * * * g

Если мы попробуем движение D, мы закончим:

. # * *    . x * *    . . * *
x * * *    * # * *    * x * *
* * * *    * * * *    * * * *
* * * g    * * * g    * * * g

Обратите внимание, что переход из состояния слева должен преуспеть, потому что иначе робот был бы помещен в ячейку (1, 1).

В другом примере следующий частичный лабиринт представляет 32 разных полных лабиринта (соответствующих 32 различным способам, которые могут быть разрешены ячейками *), каждый из которых имеет одинаковое оптимальное решение:

x # * *
. # * *
. # # *
. . . g

Несмотря на то, что по-прежнему можно использовать templatetypedef BFS эвристику для A *, тот факт, что каждая ячейка теперь может находиться в одном из трех состояний, увеличивает общее количество предварительно вычисленных расстояний до 16 * 3 ^ 14 = 76527504, что по-прежнему управляемо. Нам нужно представить множества элементов, которые могут принимать 3 состояния как суммы степеней 3 для формирования индексов в таблицы поиска, и это не так быстро или удобно, как работа с элементами из 2 состояний, но это не слишком сложно: единственное дорогая операция - деление на 3, что может быть сделано путем умножения на 0x55555556 и сохранения верхних 32 бит 64-битного результата.

Ответ 5

Я быстро бросил реализацию вместе (см. здесь, если вам интересно, это немного беспорядок, хотя). Я не уверен, что это аналогичный подход к описанию @templatetypedef. Я в основном делаю следующее:

• Создайте все лабиринты и вычислите расстояние от каждой ячейки до последней ячейки (отфильтруйте все лабиринты с недостижимыми областями, поскольку они эквивалентны лабиринтам, которые имеют стены в этих местах).
• Начните ходить через все лабиринты одновременно. Текущий балл - это общее расстояние до конечной ячейки над всеми лабиринтами, которые еще не достигли конечной ячейки.
• Вычислить оценку для каждого из четырех возможных направлений. Жестко двигайтесь в направлении, имеющем лучший (самый низкий) балл.

Этот подход сходится, но он принимает 103 шага. Затем я попытался заглянуть вперед, поэтому вместо жадного выбора лучшего следующего шага с жадностью выберем наилучшую последовательность k следующих шагов.

Я использовал этот подход до k = 10 со следующими результатами:

 k | length | sequence
--------------------
 1 |   103  | RDRDRDRDRLDDRRDRURRDLLDDRURURRDDLLLDDRRDRURRUURRRDDDULLLDDDRRRDLLDDRRLURRLLUDRRDDRRRLUUURRRDDDULLDDRDRR
 2 |    86  | RDRDRDRDRLDDRRDRURRDLLDDRUURRDRDLLLDDRDRURRUURRDRDDULLLDDDRRDRRLULLDDRDRURRLUURURRDDRD
 3 |    79  | RDRDRDRDRLDDRRDRURURDRDLLDDLDRDRRDRURURURRDDDULLLDDRDRRRLULLDDRDRRLURURDRURRDDD
 4 |    70  | RDRDRDRDRLDDRRDRUURRDLLDLDDRDRURUURRDRDDLULLLDDRDRRRDLLDDRRRLUURURRDDD
 5 |    73  | RDRDRDRDRLLDDRRDRURRURRDDDULLLDDRDRDRUURURRDDRDLULLDDRDRRLUURURRDLLLDDRRR
 6 |    70  | RDRDRDRLDRDRDUURRDLLLDDRDRDRURUURRDDULLLDDRDRRRLUUURRRDRLLDDULLDDRDRRR
 7 |    64  | RDRDRDRLDDRRDRLLDDRURUURDRDDULLLDDRDRRDRLURURURRDLDULLDDLLDRDRRR
 8 |    67  | RDRDRDRDLLDDRRDRURUURRDDULLLDDRDDRUURRDRURRDLLLDULLDDRDRRLUURURRDDD
 9 |    64  | RDRDRDRDRLLDDRURRDDRUUURRDDULLLDDRDRDRRLUUURRRDLDULLDDLLDRDRURRD
10 |    58  | RDRDRDRDRLLLDDRURDRDRUUURRDDDLULLLDRDDRRURRDRRLDDUURURRDDD

Конечно, этот подход становится невыполнимым при больших k. Поскольку OP утверждает, что проблема может быть решена всего за 29 ходов, этот жадный подход кажется не лучшим способом...

Ответ 6

Я взял 41 длинную строку из исходного сообщения и попытался свести ее к минимуму. Я обнаружил, что 4 символа могут быть удалены. Не так много, но я думаю, что это стоит того. Итак, из этого RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD я добрался до этого RRDRRDRLDRDRLDLUULRULULLDDRDDDRDURDRD. Он передает каждый лабиринт, созданный методом @Vincent.

Я также проверил другие результаты этой темы, но существенной разницы не было.

Я использовал код @Vincent для генерации лабиринтов.

Здесь ссылка на код и пример. http://ideone.com/9OFr5E

Пожалуйста, дайте мне знать, если я где-то ошибся.

Ответ 7

Давайте подумаем об этом на минуту.

Рассмотрим повторный шаблон DRDRDRDRDRDR. Мы можем запутать робота, представив что-то вроде:

xx#x
x#xx
xxxx
xx#x

где не будет работать ни запуск с Right (RDRDRDRDRDRD), ни запуск с Down (DRDRDRDRDRDR).

Однако давайте рассмотрим повторный паттерн RRDDRRDDRRDD. Чтобы запутать робота, нам нужен тупик где-то. Давайте рассмотрим возможности и посмотрим, сможем ли мы найти схему, которая провалила бы оба вида начальных ходов (т.е. RR или DD).

1

x#xx
#xxx
xxxx
xxxx 

Очевидно, не разрешимый лабиринт.

2

xx#x
x#xx
xxxx 
xxxx 

Это отключает RRDDRRDDRRDD. Теперь, какие блоки мы могли бы добавить, чтобы он также не DDRRDDRRDDRR? Попробуйте и убедитесь, что нет способа добавить блоки, которые также блокировали бы DDRRDDRRDDRR и оставались бы разрешимым лабиринтом.

3

xxx#
xx#x
xxxx
xxxx

Так же, как 2.

4 5 6 8 9 10

xxxx    xxxx    xxxx    xxxx    xxxx    xxxx
xxx#    x#xx    xx#x    xxxx    xxxx    xxxx
xxxx    #xxx    x#xx    xxx#    x#xx    xx#x
xxxx    xxxx    xxxx    xxxx    #xxx    x#xx

Не споткнись.

7

xxxx
xxx#
xx#x
xxxx

Ясно, что нет способа добавить блоки таким образом, что DDRRDDRRDDRRDDRR также потерпит неудачу и останется разрешимым.

11 12

xxxx    xxxx
xxxx    xxxx
xxx#    xxxx
xx#x    xxx#

Неразрешимые лабиринты.

Принимая во внимание, что, похоже, нет лабиринтов, которые могут потерпеть неудачу как в RRDDRRDDRRDDRRDD и в DDRRDDRRDDRRDDRR, возможно, решение можно сформировать, попробовав один шаблон, пройдя шаги назад и начав с другой возможности (т. DDRRDDRRDDRRDDRR Если мы начали с RR то DD и наоборот Versa).

Я надеюсь, что у меня будет больше времени подумать о необходимости, в этом случае, гарантировать, что пересечение шагов назад приведет к началу.

ОБНОВИТЬ

Как отмечалось в комментариях, двухэтапные последовательности действительно терпят неудачу в нескольких лабиринтах. Однако последовательность из 28 DDRRDDRRDDRRLLUURRDDRRDDRRDD, опираясь на эту идею, похоже, решает 3456 из 3828 лабиринтов.

Ответ 8

Здесь код Python, который нашел третью последовательность, RRDRRDRDLDLDULLLDDRDDURDRRDRR, за 95 минут, учитывая первые 9 направлений (обратите внимание, что Кристиан Сиверс нашел свою вторую последовательность за 45 минут, учитывая первые 9). Это поиск в глубину с некоторыми предварительными расчетами, которые, вероятно, просто повезло. Ханс Олссон показал, что при наличии 15 начальных шагов мы можем найти еще много последовательностей длиной 29 (код ниже нашел одну за 17 секунд).

Существуют ограничения на количество разрешенных U и L, которое основано на знании последовательности в ответе Кристиана Сиверса, а также на предотвращении шаблонов RLR и RRLL (и сопоставимых зеркальных и повернутых), как отметил j_random_hacker. Кроме того, есть проверка того, действительно ли ход что-то меняет, по крайней мере, в одном лабиринте (из 2432... упрощение этой проверки может сэкономить немного больше времени), а также проверка того, что предварительно вычисленные наименьшие ходы все еще необходимы меньше или равно выделенным ходам в последовательности (ограничено 29). Кодировка любого одного состояния лабиринта находится в 32 битах.

Также обратите внимание, что доступно только 2423 лабиринта, а не 3828, как показано в других местах на этой странице. (Последний список включает лабиринты, которые отличаются только в недоступных местах.)

Файл mazes.txt (доступен здесь) содержит все 3828, и код сокращает его.

"""
Let f(state, move, seq) represent the optimal sequence for the simultaneous maze solution. We define state as a list of 3828 numbers since we can represent each maze state with 16 bits for the maze and 16 bits for the robot position.

We can precalculate the shortest route to the start for each positon for each maze. Moving anywhere from the start position will just stay at the start. Then our search backwards from the end becomes:

    f(state, 0, seq) = seq

    f(state, move, seq)
      if position is too far from start for any maze, given move:
        return []
      otherwise:
        return union of f(next_state(mv), move - 1, reverse(mv) + seq)
          where mv <- [r, l, u, d]

There are at most 2423 * 16 = 38768 states for any one maze but many are unreachable / invalid (I know, 2423 to even a small power is a huge number). We can also try more a restricted distance pruning by, for example, looking at the difference in distance between different maze states. Also, we'll remember not to use RLR, LRL, UDU or DUD as j_random_hacker pointed out.

0111
0111
0000
1000

0b0111011100001000
"""

# Does not differentiate a completed maze
def move_pre(maze, direction):
  pos = maze >> 16
  temp = pos
  shift = -1
  while temp:
    shift += 1
    temp >>= 1
  if direction == 'l':
    if (pos not in [1<<3, 1<<7, 1<<11, 1<<15]) and not (maze & (1 << (shift + 1))):
      shift = shift + 1
  if direction == 'r':
    if (pos not in [1, 1<<4, 1<<8, 1<<12]) and not (maze & (1 << (shift - 1))):
      shift = shift - 1
  if direction == 'u':
    if pos < (1 << 12) and not (maze & (1 << (shift + 4))):
      shift = shift + 4
  if direction == 'd':
    if pos > (1 << 3) and not (maze & (1 << (shift - 4))):
      shift = shift - 4
  maze ^= (pos << 16)

  return maze | (1 << (shift + 16))

def get_moves_pre(maze, visited):
  l = move_pre(maze, 'l')
  r = move_pre(maze, 'r')
  u = move_pre(maze, 'u')
  d = move_pre(maze, 'd')
  return [m for m in [l, r, u, d] if m != maze and not (m >> 16) & visited]

# Returns 0 if the maze is completed
def move(maze, direction):
  if not maze:
    return maze

  pos = maze >> 16
  temp = pos
  shift = -1
  while temp:
    shift += 1
    temp >>= 1
  if direction == 'l':
    if (pos not in [1<<3, 1<<7, 1<<11, 1<<15]) and not (maze & (1 << (shift + 1))):
      shift = shift + 1
  if direction == 'r':
    if (pos not in [1, 1<<4, 1<<8, 1<<12]) and not (maze & (1 << (shift - 1))):
      shift = shift - 1
  if direction == 'u':
    if pos < (1 << 12) and not (maze & (1 << (shift + 4))):
      shift = shift + 4
  if direction == 'd':
    if pos > (1 << 3) and not (maze & (1 << (shift - 4))):
      shift = shift - 4
  maze ^= (pos << 16)

  if shift == 15:
    return 0

  return maze | (1 << (shift + 16))

"""
0111
0111
0000
1000
"""
#a = 0b0111011100001000
#print "{0:b}".format(move(a | (1 << 16), 'd'))

def get_moves(maze, visited):
  l = move(maze, 'l')
  r = move(maze, 'r')
  u = move(maze, 'u')
  d = move(maze, 'd')
  return [m for m in [l, r, u, d] if m != maze and not (m >> 16) & visited]

def least_steps(maze):
  visited = 0
  stack = [(i, 1) for i in get_moves_pre(maze, visited)]

  while stack:
    (new_maze, count) = stack.pop(0)
    # robot is in starting position
    if new_maze & (1 << (16 + 15)):
      return count
    visited |= (new_maze >> 16)

    stack.extend(
      [(i, count + 1) for i in get_moves_pre(new_maze, visited)]
    )

#print least_steps(0b10111011100001000)

least_moves = {0: 0}

# We can reduce the number of mazes by grouping only reachable sections
def reachable(maze):
  global least_moves
  visited = 0
  stack = get_moves_pre(maze, visited)

  while stack:
    new_maze = stack.pop(0)
    # hash least moves
    least_moves[new_maze] = least_steps(new_maze)
    visited |= (new_maze >> 16)

    mvs = get_moves_pre(new_maze, visited)
    if mvs:
      stack.extend(mvs)

  return visited

#print reachable(0b10111001110111000)
#print reachable(0b10110001010111000)

rs = {}

print "precalculating..."
for L in open("mazes.txt"):
  L = L.strip()
  maze = int(L, 2) | (1 << 16)
  r = reachable(maze)
  if r in rs:
    rs[r].append(maze)
  else:
    rs[r] = [maze]

mazes = []

for r in rs:
  mazes.append(rs[r][0])

print "%s reachable mazes" % len(mazes)

def get_next_params(mazes, seq, rd_count, seq_length, max_rd_count):
  global least_moves
  if len(seq) == seq_length:
    return []

  next_states = []
  mazes_state = [None] * len(mazes)

  if seq[-2:] != "ud" and seq[-3:] != "ddu":
    for i, maze in enumerate(mazes):
      if seq_length - len(seq) < least_moves[maze]:
        return []
      mazes_state[i] = move(maze, 'u')
    next_states.append((mazes_state[:], seq + 'u', rd_count))

  if seq[-2:] != "lr" and seq[-3:] != "rrl":
    for i, maze in enumerate(mazes):
      if seq_length - len(seq) < least_moves[maze]:
        return []
      mazes_state[i] = move(maze, 'l')
    next_states.append((mazes_state[:], seq + 'l', rd_count))

  if rd_count < max_rd_count:
    if seq[-2:] != "rl" and seq[-3:] != "llr":
      for i, maze in enumerate(mazes):
        if seq_length - len(seq) < least_moves[maze]:
          return []
        mazes_state[i] = move(maze, 'r')
      next_states.append((mazes_state[:], seq + 'r', rd_count + 1))

    if seq[-2:] != "du" and seq[-3:] != "uud":
      for i, maze in enumerate(mazes):
        if seq_length - len(seq) < least_moves[maze]:
          return []
        mazes_state[i] = move(maze, 'd')
      next_states.append((mazes_state[:], seq + 'd', rd_count + 1))

  return next_states


def different(state, new_state):
  return any([a != b for (a,b) in zip(state, new_state)])

def f(mazes, seq_length, max_rd_count, starting_seq='l', rd_count=0):
  global start_time
  stack = [(mazes, starting_seq, rd_count)]
  count = 0

  while stack:
    mazes, seq, rd_count = stack.pop()

    count += 1
    if not (count % 1000):
      print "%s sequences so far, current length: %s, %s seconds" % ("{:,}".format(count), len(seq), time.time() - start_time)

    if not any(mazes):
      return seq

    for (new_mazes, new_seq, new_rd_count) in get_next_params(mazes, seq, rd_count, seq_length, max_rd_count):
      if (different(mazes, new_mazes)):
        stack.append((new_mazes, new_seq, new_rd_count))

  return None

#         x x xxx x    x
# rrdrrdrdldldulldldrddurdrrdrr
# llullulururudrruruluudlullull
#         x x xxx x    x
def play(maze, seq):
  for m in seq:
    maze = move(maze, m)
  return maze 

# Start into the sequence
new_mazes = []
seq = "llullulur"#urudrruruluudlullull"
rd_count = 0
for c in seq:
  if c in ['r', 'd']:
    rd_count += 1
for m in mazes:
  new_mazes.append(play(m, seq))

print "starting sequence: %s\nrd count: %s" % (seq, rd_count)
import time
print "starting calculation..."
start_time = time.time()
print f(new_mazes, 29, 7, seq, rd_count)
print("--- %s seconds ---" % (time.time() - start_time))

Ответ 9

Идея улучшения существующих решений может быть расширена не только для поиска по начальной строке, но и для того, чтобы иметь как фиксированную начальную, так и конечную строку.

Это достаточно быстро, что даже без распараллеливания вы можете перейти от 32-шаговых решений к 29-шаговым решениям за несколько минут.

Для конечной строки m ходов вы находите квадраты, которые начинаются там и применяют последовательность конечных частей, чтобы достичь конечной точки. (На каждом шаге вы рассматриваете два возможных предшественника каждой точки и добавляете конечную точку. Два возможных предшественника для квадрата S, для R-перемещения - это квадрат S и его L-сосед, если он действителен, Move (S, L). Каждый из них добавляется только в том случае, если Move (S ', R) == S.) (Может опубликовать весь код позже.)

Затем им дается расстояние m, а их соседям расстояние m + 1 и т.д.

Затем вы применяете поиск A *, используя эту эвристику.

Это заняло 1 минуту, чтобы перейти от RRDRRDRLDRDLDLULLLDDRDDRDURRDRRD (32 длинных), оставив первые 7 и 11 последних с RRDRRDRDLDDULDLDLDRDDRDURRDRRD (30 длинных) и сохранив первые 15, а затем полминуты, чтобы найти RRDRRDRDLDDULDLDLDRDRDURDRRDR (29)

И обратите внимание, что существует 2423 лабиринта, которые можно пройти, но нужно учитывать только 2083, так как у остальных есть квадраты, которые могут быть достигнуты только путем прохождения через конечную точку.

Ответ 10

Не совсем ответ, но другие могут оказаться полезными для ответа.

Похоже, лучший подход - это двигаться по диагонали. Тем не менее, я сталкиваюсь с несколькими сложными ситуациями, которые я перечисляю ниже, которые, похоже, поднимают подходы, которые я придумываю вручную.

1 0 0 0    1 0 0 0    1 0 0 0    1 0 # Z    1 0 # Z
0 # X #    0 # # X    0 # # X    # 0 X 0    # 0 # Z
0 Z # Z    0 Z Z #    0 0 0 #    Z Z # 0    Z 0 X 0
0 0 0 1    0 0 0 1    X # 0 1    Z Z # 1    Z Z # 1

Где: 1 - начало/конец. 0 - пустое пятно, # является стеной, Z является либо стеной, либо пустой, а X - это неприятные пятна от застревания или трудности с их получением.

Подход, который может решить вышеупомянутые лабиринты с наименьшим количеством команд, должен быть близок к решению любого лабиринта.