我遇到了这个非常有趣的问题，我们有一个4x4的迷宫和一个机器人试图进入目标。问题是，您必须找到一系列预定义命令，这些命令将始终导致机器人到达目标。
假设我们有一个像这样的迷宫：
x . . .
. # # .
. # # .
. . . g
这种特殊的迷宫可以用例如命令序列DDDRRR或RRRDDD来解决，其中R =右，L =左，U =上，D =下（duh）。
然而，这些序列都不会解决这个迷宫：
x . # .
. . . .
# . . .
. . . g
机器人总是从左上角开始，目标总是在右下方，迷宫始终是2D 4x4矩阵。
我已经实现了一个算法，让我获得了78个命令的获胜序列。我确信至少存在29个命令的解决方案（其他人完成了这个）。
这个问题实际上已经有几年了，所以我丢失了当时使用的算法，但基本的想法是在我生成的所有迷宫中搜索，并始终选择导致解决最多的路线迷宫。这实际上让我得到了一个略长于78的序列;我手动减少了一些命令，我发现这些命令是多余的。
是的，暴力迫使需要几年的时间。
如果我的记忆服务，可能会有少于4000个迷宫（可能的迷宫是左上角和右下角之间的路径存在）。
哦！机器人在执行命令期间至少一次访问目标就足够了。也就是说，它不必在最后一个命令之后坐在目标上。
我有没有抓住任何人的兴趣？我应该如何处理这个问题以获得更有效的答案？谢谢你考虑:)
这是一个（非常）匆忙拼凑的Java片段。它应该编译运行:)程序有点同时播放~4000个迷宫。程序对UP，LEFT，DOWN和RIGHT进行输入（w，a，s，d），然后模拟移动，显示一些统计数据。如果你尝试的话，你可以在屏幕上看到的是每个位置的每个迷宫中的障碍物总量，以及每个迷宫的当前位置总量。这很难解释:)问我是否有问题。
再说一遍......不要介意可怕的代码。它是在20分钟内写成的
我从this user's answer间接得到了这个想法，并在聊天中进一步与Mooing Duck建模。我们的想法是找到一个解决迷宫右侧的序列。也就是说，解决所有迷宫中至少一半的解决方案，并且从一开始就镜像并再次运行解决剩余的迷宫。
插图：
首先找到一个序列，其第一个命令是RIGHT，它解决了这个迷宫：
0 1 0 0
0 1 0 0
0 0 0 0
0 1 0 0
一个这样的序列是RDDRRRD。该序列的镜像对应物是这样的
R -> D
D -> R
L -> U
U -> L
这意味着RDDRRRD - > DRRDDDR
现在，这个镜像序列能否解决迷宫？不，它卡住了。因此，即使对于这个迷宫，它也不是有效的序列。我们必须找到这样一个序列，它至少解决了所有迷宫中的一半，并且它的镜像对应物在从一开始就再次运行时解决了其余部分。
在简单地强制执行R，D和L的所有可能排列后，我得到了一些可能的序列。
一个这样的序列是RRDRRRDRLDRDR
现在的下一个问题是，在运行此序列之后，剩余的迷宫处于随机混乱状态。我们需要获得最短（最佳）可能的序列，将所有剩余的迷宫返回到起始位置（0,0）。这部分我只是手工完成（现在）。我的答案绝不是最佳的，但它让所有的迷宫都回到了开头。
这个序列是LDLUULURUUULULL
在此之后我们只需运行镜像序列DDRDDDRDURDRD，我们就解决了所有的迷宫问题。
这个特殊的顺序是完整的：
RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD - 41步
虽然这是一个充满希望且令人瞩目的里程碑，但距离最佳证明解决方案还有12步之遥。非常欢迎任何见解！还要感谢迄今为止帮助过我的每个人:)
我已经无法以编程方式获得比58移动长序列更好的答案。然而，通过上述方法并且只是手工磨削字符，我已经能够将序列缩小到仅33个字符。这个顺序如下：
RRDRRDRLDRDLDLULLLDDRDDRDRURRRDDR - 33次移动
虽然序列现在非常接近29目标，但我仍然在寻找具有相同口径的程序化获取解决方案。从序列中删除字符时我没有使用逻辑 - 我只是删除了一个字符并检查它是否解决了所有迷宫，冲洗并重复。
我把这个问题编码为SAT问题4280308变量和21975717条款（包括许多冗余但看似有用的）treengeling在大约100 1/2小时后解决，找到长度为29的解决方案字符串：
RRDRRDRDLDLDULLDLDRDDURDRRDRR
几乎85小时后得出类似的计算结果，没有长度为28的解。
这是我用来创建SAT问题的快速而肮脏的Haskell程序：
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)
它需要一个命令行参数，一个表示解决方案字符串长度的整数。输出是CNF SAT问题，每行一个子句，符号文字和否定波形符。这是Donald Knuth用于他的SAT求解器here的格式。我使用他的SAT-TO-DIMACS程序将其转换为更常用的DIMACS格式。它是用CWEB编写的，所以你必须把它变成一个带有ctangle的C程序。你还需要gb_flip.w。程序从stdin读取并写入stdout，你会想给它一个像h20这样的选项来增加它的哈希表大小。
为了打破对称性，我添加了单位子句D0E以强制第一步向右移动。 （请注意，我使用的是NESW而不是URDL，因为我之前读过有关使用这些作为方向的a similar problem。）
该计划考虑所有2423个迷宫，其中每个位置可以到达或墙。作为@Hans_Olsson observed，仅考虑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阶段是朝着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>，以便将变量名称长度保持在Knuth程序强加的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。
不完全是一个答案，但其他人可能会发现它有助于提出答案。
似乎总体上最好的方法是对角移动。但是，我遇到了一些棘手的情况，我在下面列出了这些情况，这些情况似乎绊倒了我手工提出的方法。
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是麻烦的地方，要么遇到困难，要么遇到困难。
能够以最少数量的命令解决上述迷宫的方法应该非常接近于解决任何迷宫问题。
使用元A *算法和C＃，我发现了以下32和31个字符序列（到目前为止）：
RRDRRDRLDRDLDLULLLDDRDDRDRURRDRD (32 characters)
RRDRRDRLDRDLDLULLLDDRDDRDURRDRRD (32 characters)
RRDRRDRLDRDLDLULLLDDRDDDURDRRDR (31 characters)
我forked Olavi's ideone与31个字符序列，以确保我没有错误。
关于迷宫计数，我使用泛洪填充算法获得3828个有效迷宫。
在Google Drive上的C＃项目源代码和已编译的发布二进制文件（在bin \ release文件夹中）。
您可以在那里输入A *搜索的起始字符串和最大搜索长度。对代码进行了一些速度优化，但仍有更多优势。例如，对于每个扩展，它创建4个Candidate类的实例，创建新的迷宫，运行旧候选人的每一步，然后是4个不同的方向（左，右，上，下）。使用Candidate.Clone()方法，性能可以大大提高，分析器显示当前的热点。此外，到目前为止还没有多线程，程序使用越来越多的内存用于访问列表（在我的PC上10分钟后大约2 GB）。请注意，即使在发布模式下，在IDE中运行程序也会使其速度降低，因此最好在外部启动它。
导致上述序列的基本元算法是：
我尝试过的实际组合可以在源代码中看到，请参阅下面的代码片段。时间来自较旧的未优化版本，当前版本应该快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
听起来你可以在这里使用A *搜索，将所有迷宫中的最大启发式作为启发式。保守地接近解决方案的距离，可能会给出合理的第一种方法。
由于所有迷宫都很小，你可以通过从每个迷宫的末端反向运行BFS来预先计算从每个点到每个迷宫的目标的距离，从而为每个迷宫构建完美的启发式。如果你在查找表中缓存了这个，你可以使用一个迷你启发式方法，完美地告诉你剩下的最小移动次数。
我还没有尝试过这个，所以这仍然需要通过实验验证，但我认为这将是解决方案的一个很好的起点。
编辑我刚读了一个说明，说每个机器人必须至少一次访问目标，而不一定是在目标上结束。在这种情况下，将启发式修改为从尚未达到目标的任何机器人到目标的最大距离。
希望这可以帮助！
一些想法：
g的机器人在三次移动中的第二次到达g时才适用。整蛊！]*来做到这一点。每当我们尝试移动到*单元格时，这个状态就会分裂成两个子状态：它成为空单元格的状态（我们的移动成功完成），以及它成为墙壁的状态（我们保持在同一位置）。如果将此单元格显示为墙壁意味着不再可能到达目标单元格，则不会生成该子状态。因此，例如，在尝试第一次移动（R）之后，搜索树节点中的完整状态信息由以下两个部分迷宫组成：
x # * * . x * *
* * * * * * * *
* * * * * * * *
* * * g * * * g
如果我们再尝试D动作，我们最终会：
. # * * . x * * . . * *
x * * * * # * * * x * *
* * * * * * * * * * * *
* * * g * * * g * * * g
请注意，从左侧状态的移动必须成功，否则机器人将被装入（1,1）单元格。
再举一个例子，下面的部分迷宫代表32种不同的完整迷宫（对应于可以解析*细胞的32种不同方式），每种方法都有相同的最佳解决方案：
x # * *
. # * *
. # # *
. . . g
虽然仍然可以对A *使用templatetypedef的BFS启发式，但每个单元现在可以处于3种状态之一的事实将预计算距离的总数增加到16 * 3 ^ 14 = 76527504，这仍然是可管理的。我们需要表示可以假设3个状态的项目集合作为3的幂的总和，以将索引形成到查找表中，这不像使用2状态项目那样快速或方便，但它并不太难：只有昂贵的操作除以3，可以通过乘以0x55555556并保持64位结果的前32位来完成。
我很快就把一个实现放在一起（如果你感兴趣的话，请参阅here，但这有点乱）。我不确定这是否与@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次移动来解决，这种贪婪的方法似乎不是最好的方法......
我从原始帖子中取出了41根长弦并尝试将其最小化。我发现可以删除4个字符。不多，但我认为值得注意。所以从这个RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD我得到了这个RRDRRDRLDRDRLDLUULRULULLDDRDDDRDURDRD。它通过@Vincent方法生成的每个迷宫。
我还检查了这个帖子的其他结果，但没有任何显着差异。
我使用了一些@Vincent的代码来生成迷宫。
这是代码和示例的链接。 http://ideone.com/9OFr5E
如果我在某个地方犯了错误，请告诉我。
让我们考虑一下这一点。
考虑重复模式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失败的迷宫，也许可以通过尝试一种模式，向后遍历步骤并从另一种可能性开始形成解决方案（即，如果我们从RR开始，那么DD和副反之亦然）。
我希望我有更多的时间来考虑这种需要，在这种情况下，保证向后移动步骤将导致回到起点。
正如评论所指出的那样，两步序列确实失败了很多迷宫。然而，28个DDRRDDRRDDRRLLUURRDDRRDDRRDD的序列，依靠这个想法，3838迷宫中的seems to solve 3456。
改进现有解决方案的想法可以扩展到不仅基于起始字符串进行搜索，而且还具有固定的起始字符串和结束字符串。
这足够快，即使没有并行化，您也可以在几分钟内从32步解决方案转变为29步解决方案。
对于m个移动的结束字符串，您可以找到正方形，从那里开始并应用结束部分序列将到达终点。 （在每个步骤中，您考虑每个点的两个可能的前驱，并添加端点。对于R-move，两个可能的前导S是方形，S，如果有效则为其L邻居，Move （S，L）。只有当Move（S'，R）== S时才会添加其中的每一个。（可以稍后发布整个代码。）
然后它们被给予距离m，并且它们的邻居距离为m + 1等。
然后使用此启发式应用A *搜索。
从RRDRRDRLDRDLDLULLLDDRDDRDURRDRRD（32长）开始需要1分钟，保留前7和后11给RRDRRDRDLDDULDLDLDRDDRDURRDRRD（30长）并保持前15然后花了半分钟找到RRDRRDRDLDDULDLDLDRDRDURDRRDR（29长！）
请注意，有2423个可到达的迷宫，但其中只有2083个需要考虑，因为其他的只有通过终点才能到达的正方形。
这里的Python代码在95分钟内找到了第三个序列RRDRRDRDLDLDULLLDDRDDURDRRDRR，给出了最初的9个方向（注意Christian Sievers在45分钟内找到了他们的second sequence，给出了最初的9个）。这是一个深度优先搜索与一些可能只是幸运的预先计算。 Hans Olsson showed提供了15个初始步骤，我们可以找到更多29个长度的序列（下面的代码在17秒内找到一个）。
允许使用U和L的数量受到限制，这依赖于来自Christian Sievers的answer的序列中的知识，以及像j_random_hacker RLR一样预防RRLL和noted（以及类似的镜像和旋转）模式。此外，还要检查移动是否实际上改变了至少一个迷宫中的某些内容（2432中的内容...精简该检查可能会节省更多时间），以及检查预先计算的最少移动 - 仍然需要小于或等于序列中分配的移动（限制为29）。任何一个迷宫状态的编码都是32位。
另请注意，本页其他地方只有2423个可到达的迷宫，而不是3828。 （后一个列表包括仅在无法到达的地方有所不同的迷宫。）
文件mazes.txt（可用的here）包含所有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's state with 16 bits for the maze and 16 bits for the robot's 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))