Solve all 4x4 mazes simultaneously with least moves

Question

I came across this quite interesting problem, where we have a 4x4 maze and a robot in it trying to get to the goal. The thing is, you have to find a sequence of predefined commands that will always result in the robot reaching the goal.

Let's say we have a maze like this:

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

This particular maze can be solved with, for example, the command sequences DDDRRR or RRRDDD, where R = right, L = left, U = up and D = down (duh).

Neither of those sequences would, however, solve this maze:

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

---

The robot always starts at the top left, the goal is always at the bottom right, and the maze is always a 2D 4x4 matrix.

I have already implemented an algorithm that got me a winning sequence of 78 commands. I know for sure there at least exists a solution for 29 commands (someone else accomplished this).

This problem is in fact a few years old and so I've lost the algorithm I used at the time, however the basic idea was to run a search through all the mazes I generated, and always choose the route that results in the most solved mazes. This actually got me a sequence that was slightly more than 78 in length; I reduced some commands by hand that I noticed were redundant.

Yes, brute-forcing will take years as per usual.

If my memory serves, there are less than 4000 possible mazes (possible maze being that a path between top left and bottom right exists).

OH! it's sufficient that the robot simply visits the goal at least once during the execution of the commands. That is, it doesn't have to be sitting on the goal after the last command.

Did I catch anyone's interest? How should I approach this problem for a more efficient answer? Thanks for considering :)

---

Something Fun: Pastebin

It's a (very) hastily put together piece of Java. It should compile and run :) The program kinda plays ~4000 mazes at the same time. The program takes an input (w, a, s, d) for UP, LEFT, DOWN and RIGHT, and then simulates the move, showing some statistics. What you can see on the screen, should you try it, is the total amount of obstacles in every maze in each position, and the total amount of current positions of each maze. It's hard to explain :) Ask me if you have questions.

Again... don't mind the horrible code. It was written in 20 minutes..ish

---

Progress

I got this idea indirectly from this user's answer, and further modeled it with Mooing Duck in a chat. The idea is to find a sequence that solves the right side of the maze. That is, a solution that solves at least a half of all the mazes, and when mirrored and run again from the start solves the remaining mazes.

Illustration:

first find a sequence, whose first command is RIGHT, that solves, for example, this maze:

0 1 0 0
0 1 0 0
0 0 0 0
0 1 0 0

one such a sequence is RDDRRRD. The mirrored counterpart of this sequence is one such that

R -> D
D -> R
L -> U
U -> L

Which means RDDRRRD -> DRRDDDR

Now, does this mirrored sequence solve the maze? No, it gets stuck. Therefore it's not a valid sequence even for this one maze. We have to find such a sequence that it solves at least half of all the mazes, and it's mirrored counterpart solves the rest when run again from the start.

After simply brute forcing all the possible permutations of R, D and L, I got a few possible sequences.

One such sequence is RRDRRRDRLDRDR

Now the next problem is, that after running this sequence, the remaining mazes are in a random chaos. We need to get the shortest (optimal) possible sequence that will get all the remaining mazes back to the starting position (0, 0). This part I did simply by hand (for now). My answer for this is by no means optimal, but it gets all the mazes back to the beginning.

This sequence is LDLUULURUUULULL

After this we simply run the mirrored sequence, DDRDDDRDURDRD, and we have solved all the mazes.

This particular sequence in it's entirety:

RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD - 41 moves

While this is a promising and awarding milestone, it's still 12 moves away from the best proved solution. Any insight is very welcome! Also, thanks to everyone who helped me so far :)

The sequence shrinks

I've been as of yet unable to programmatically get a better answer than a 58 moves long sequence. However with the method described above and just grinding the characters by hand, I've been able to shrink the sequence to be only 33 characters long. This sequence is below:

RRDRRDRLDRDLDLULLLDDRDDRDRURRRDDR - 33 moves

While the sequence is now very close to the 29 goal, I'm still kind of looking for a programmatically aquired solution of the same caliber. There's no logic that I used when removing characters from the sequence - I just simply removed a character and checked if it solves all mazes, rinse and repeat.

Answer 1

Not exactly an answer but others might find it useful towards coming up with an answer.

Seems like the best approach overall is to move diagonally. However, I come across a number of tricky situations, which I list below that seem to trip up the approaches I come up with by hand.

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

Where: 1 is the start/end. 0 is an empty spot, # is a wall, Z is either a wall or empty and X is the troublesome spots, from either getting stuck or difficulty getting to them.

An approach that can solve the above mazes with the smallest number of commands should be rather close to solving any maze.

Answer 2

A few ideas:

• None of the substrings RLR, LRL, UDU or DUD can appear in any optimal solution, since in every maze they leave the robot either in the same position (if the first move is blocked by a wall) or one step in the direction of the first move (otherwise), which in each case is the same as the result of performing just the first move in the sequence. The same goes for RRLLRR, LLRRLL, etc. (and probably for all longer patterns, though I haven't verified that, and they yield diminishing returns in terms of pruning the search). [EDIT: This is not quite right -- it applies only if no robot that has not yet reached g would reach g on the second of the three moves. Tricky!]
• In any valid solution, if all Ds and Rs are swapped, and all Ls and Us are swapped, we get another valid solution, since this "flipped" solution will solve all mazes which have been "flipped" around the leading diagonal -- which is just the set of all mazes. The upshot is that we need only consider solutions in which the first move is, say, R.
• One way to proceed with A* search (or branch and bound, or full enumeration) is to record, at each node in the search tree, the state of the robot in all ~4000 valid mazes. But we can save quite a bit of time and space by combining the states of all mazes that could not have been distinguished by our moves so far. We can do this by recording a third, "unknown" cell state, *. Whenever we try to make a move into a * cell, this state splits into 2 sub-states: the state in which it becomes an empty cell (and our move completes successfully), and the state in which it becomes a wall (and we remain in the same position). If revealing this cell to be a wall would mean that it's no longer possible to reach the goal cell, then that sub-state is not generated.

So for example, after attempting the very first move (R), the complete state information in the search tree node consists of the following two partial mazes:

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

If we then try a D move, we wind up with:

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

Note that the move from the state on the left had to succeed, because otherwise the robot would have been boxed into the (1, 1) cell.

For another example, the following partial maze represents 32 different full mazes (corresponding to the 32 different ways that the * cells could be resolved), each of which has the same optimal solution:

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

While it's still possible to use templatetypedef's BFS heuristic for A*, the fact that each cell can now be in one of 3 states increases the total number of precomputed distances to 16*3^14 = 76527504, which is still manageable. We need to represent sets of items that can assume 3 states as sums of powers of 3 to form indexes into lookup tables, and this isn't as fast or convenient as working with 2-state items, but it's not too hard: the only expensive operation is division by 3, which can be done by multiplying by 0x55555556 and keeping the top 32 bits of the 64-bit result.

Answer 3

I quickly threw an implementation together (see here if you're interested, it's a bit of a mess though). I am not sure if this is a similar approach to what @templatetypedef described. I basically do the following:

1. Generate all mazes and compute the distance from each cell to the final cell (filter out all mazes that have unreachable areas, because those are equivalent to mazes that have walls in those spots).
2. Start walking through all mazes simultaneously. The current score is the total distance until the final cell over all mazes that have not reached the final cell yet.
3. Compute the score for each of the four possible directions. Greedily move to the direction which has the best (lowest) score.

This approach converges, but it takes 103 steps. I then tried to have a bigger look-ahead, so instead of greedily picking the best next step, greedily pick the best sequence of k next steps.

I ran this approach up to k = 10, with the following results:

 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

Of course, this approach becomes unfeasible for large k. Since the OP states the problem can be solved with only 29 moves, this greedy approach seems not the best way to go...

Answer 4

It sounds like you could use A* search here, taking as the heuristic the maximum heuristic out of all the mazes. That conservatively approximates the distance to the solution and probably would give a reasonable first approach.

Since all the mazes are small, you could build a perfect heuristic for each by running BFS in reverse from the end of each maze to precompute the distance from each point to the goal of each maze. If you cached this in lookup tables, you could have a per-maze heuristic that perfectly told you the minimum number of moves left.

I haven't actually tried this, so this remains to be experimentally validated, but I think it would be a great starting point for a solution.

EDIT I just read the note that says each robot has to visit the goal at least once and not necessarily end on the goal. In that case, modify the heuristic to be the maximum distance from any robot that hasn't yet hit the goal to the goal.

Hope this helps!

Answer 5

Let's think about this for a minute.

Consider the repeated pattern DRDRDRDRDRDR. We can trip up the robot by presenting something like,

xx#x
x#xx
xxxx
xx#x

where neither starting with Right (RDRDRDRDRDRD) nor starting with Down (DRDRDRDRDRDR) would work.

However, let's consider the repeated pattern RRDDRRDDRRDD. In order to trip up the robot, we need a dead end somewhere. Let's consider the possibilities and see if we can find a pattern that would fail both kinds of starting moves (i.e., either RR or DD).

1

x#xx
#xxx
xxxx
xxxx 

Clearly not a solvable maze.

2

xx#x
x#xx
xxxx 
xxxx 

This trips up RRDDRRDDRRDD. Now, which blocks could we add to make it also fail DDRRDDRRDDRR? Try it and see that there is no way to add blocks that would also block DDRRDDRRDDRR and remain a solvable maze.

3

xxx#
xx#x
xxxx
xxxx

Same as 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

Don't trip.

7

xxxx
xxx#
xx#x
xxxx

Clearly no way to add blocks such that DDRRDDRRDDRRDDRR will also fail and remain solvable.

11 12

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

Not solvable mazes.

Considering that there seem to be no mazes that can fail both RRDDRRDDRRDDRRDD and DDRRDDRRDDRRDDRR, perhaps a solution can be formed by trying one pattern, traversing the steps backwards and starting off with the other possibility (i.e., if we started with RR then DD and vice versa).

I hope I will have more time to think about the need, in this case, to guarantee that traversing the steps backwards would lead back to the start.

UPDATE

As the comments pointed out then, the two-step sequences do fail quite a few mazes. However, a sequence of 28, DDRRDDRRDDRRLLUURRDDRRDDRRDD, relying on this idea, seems to solve 3456 out of the 3828 mazes.

Answer 6

I took the 41 long string from the original post and tried minimizing it. I found that 4 characters can be removed. Not much but I think it's worth noting. So from this RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD i got to this RRDRRDRLDRDRLDLUULRULULLDDRDDDRDURDRD. It passes every maze generated by @Vincent's method.

I also checked other results from this thread, but there wasn't any significant difference.

I used a bit of @Vincent's code for generating mazes.

Here's a link to code and example. http://ideone.com/9OFr5E

Please let me know if I made a mistake somewhere.

Answer 7

Using a meta A* algorithm and C#, I found the following 32 and 31 character sequences (so far):

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

I forked Olavi's ideone with the 31 character sequence to make sure I made no errors.

Regarding maze count, I get 3828 valid mazes using a flood fill algorithm.

C# project source code and compiled release binary (in bin\release folder) at Google Drive.

You can enter a start string for the A* search there and a maximum search length. There have been quite some speed optimizations to the code, but there's still place for more. For example, for every expansion, it creates 4 instances of the Candidate class, creating new mazes that run every move of the old candidate, followed by the 4 different directions (left, right, up, down). With a Candidate.Clone() method, performance could be improved a lot, the profiler shows the current hotspot exactly there. Also, there's no multithreading so far and the program uses more and more memory for the visited list (around 2 GB after 10 minutes on my PC). Note that running the program inside the IDE slows it down quite a bit even in release mode, so better start it outside.

The basic meta algorithm that lead to the sequences above is:

• A* search for a known string of length N with maximum length M, removing more and more chars from the end, e.g.

  A* search for RRDRRDRLDRDLDLULLLDDRDDRDRURRRDD (32 chars), M = 33

  A* search for RRDRRDRLDRDLDLULLLDDRDDRDRURRRD (31 chars), M = 33

  A* search for RRDRRDRLDRDLDLULLLDDRDDRDRURRR (30 chars), M = 33

  A* search for RRDRRDRLDRDLDLULLLDDRDDRDRURR (29 chars), M = 33

  ...

• Once a shorter string than N is found, use this as the new maximum length for the A* search to make it faster and take less memory.

The actual combinations I tried can be seen in the source code, see the code snippet below. The timings are from an older unoptimized version and the current version should be around 6 times faster.

        //// 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 

Answer 8

I encoded this problem as a SAT problem with 4280308 variables and 21975717 clauses (including a lot of redundant but seemingly helpful ones) which treengeling solved after about 100 1/2 hours, finding this solution string of length 29:

RRDRRDRDLDLDULLDLDRDDURDRRDRR

A similar computation concluded after almost 85 hours that no solution of length 28 exists.

Here is the quick and dirty Haskell program I used to create the SAT problem:

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)

It takes one command line argument, an integer stating the length of the solution string. The output is a CNF SAT problem with one clause per line, symbolic literals and tilde for negation. It's the format that Donald Knuth uses for his SAT solvers here. I turned this into the more usual DIMACS format using his SAT-TO-DIMACS program. It is written in CWEB, so you have to turn it into a C program with ctangle. You'll also need gb_flip.w. The program reads from stdin and writes to stdout, and you'll want to give it an option like h20 to increase its hash table size.

To break the symmetry, I added the unit clause D0E to force the first step to go right. (Note that I used NESW instead of URDL, because I previously read about a similar problem using those as directions.)

The program considers all the 2423 mazes where each position is either reachable or a wall. As @Hans_Olsson observed, it is sufficient to only consider the 2083 mazes where each position is either a wall or reachable without passing the goal. To optimize the program to only consider these mazes, add p /= stop, after p <- front, in the definition of reachable.

The encoding

(I'll add remarks relating the description to what the program does. They can savely be ignored if you are only interested in the encoding.)

Let len be the length of the solution that we are searching for, let i be an integer with range 0<=i<=len (unless noted otherwise). Let m range over all the considered mazes and let p range over the reachable positions of a particular maze. The reachable positions include the values start and stop for the start position and the goal. Let d range over the four possible directions.

(The program outputs m as hexadecimal 14 bit number encoding the wall positions, and p as upper case letter. It uses variable names inconsistently: n for m or for i or for len, w (walls) for m, s (step) for i, and in one case h (helper) for d.)

For each i<len and each d, there is a variable D<i><d> indicating that the i-th step of the solution is to go in direction d. (The program creates them with the dir function.)

For each i0<len, there are clauses demanding that at most one of the four variables D<i0><d> is true.

For each m, i and p, there is a variable P<m><i><p> indicating that in maze m, at time i position p is reached. (The program creates them with the pos function.)

For each maze m0, there is a unit clause P<m0><0><start> establishing the start position.

For each m0 and i0, there are clauses demanding that at most one of the variables P<m0><i0><p> is true (we cannot be in two different positions). These are redundant except for the case i0=0 (where they could be replaced by unit clauses ~P<m0><0><p> for all p!=start), but seem to help.

The progression from the mazes at time i0 to time i0+1 according to the direction given in D<i0><d> is described using helper variables. For each m, i>0, p and d, there is the variable P<m><i><p><d>. (The program creates them with the posh function. It prints them as <d><m><i><p> in order to keep the variable name length within the limit of 8 characters imposed by Knuth's programs.)

The idea is that each direction gives a possible reason why a position may be reached. The variable indicates that in maze m, at time i position p is reached "because of" d. If we consider going in some direction, hitting a wall and bouncing off from it as coming from that direction, then we can interpret the variables as reaching that position by coming from direction d.

So let's consider some fixed m, i<len, p and d. How can P<m><i+1><p> be true because of d? If there is no wall in direction d (coming from p), then we may have come from there; let's call that position np. If there is a wall, then we may have been here before, tried to go there and hit the wall.

Therefore we need clauses establishing that P<m><i+1><p><d> is equivalent to the conjunction (logical and) of P<m><i><p'> and D<i><d'>, where p'=np and d' is the opposite direction of d if there is no wall, and p'=p and d'=d if there is a wall. (The program does this in the function mazestepdirposconds.)

Then, we just need clauses establishing that, for each m0, i0>0 and p0, the variable P<m0><i0><p0> is equivalent to the disjunction (logical or) of the four variables P<m0><i0><p0><d>.

Finally, we need to add the condition that the mazes are solved. So, for each maze m0, we need a clause demanding that one of the variables P<m0><i><stop> is true. Since a maze cannot be solved in less than 6 steps, we need only consider i>=6.

Answer 9

Here's Python code that found a third sequence, RRDRRDRDLDLDULLLDDRDDURDRRDRR, in 95 minutes, given the initial 9 directions (note that Christian Sievers found their second sequence in 45 minutes given the initial 9). It's a depth first search with some precalculations that probably just got lucky. Hans Olsson showed that provided with 15 initial steps, we can find many more 29-length sequences (the code below found one in 17 seconds).

There are restrictions on the number of U and L allowed, which is relying on knowledge from the sequence in Christian Sievers' answer, and also prevention of the patterns RLR and RRLL (and comparable mirrored and rotated) as j_random_hacker noted. Also, there's a check on whether a move actually changes something in at least one maze (out of 2432... streamlining that check might save a little more time), as well as a check that the precalculated least-moves-still-needed is less than or equal to the allotted moves in the sequence (limited to 29). The encoding of any one maze state is in 32 bits.

Also note that there are only 2423 reachable mazes, not 3828 as has appeared elsewhere on this page. (The latter list includes mazes that differ only in unreachable places.)

The file, mazes.txt (available here), contains all 3828 and the code reduces it.

"""
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))

Answer 10

The idea of improving existing solutions can be extended to not only search based on a starting string, but to have both a fixed starting and ending string.

That is sufficiently fast that even without parallelization you can go from the 32-step solutions to 29-step solution in a few minutes.

For the end string of m moves you find the squares such that starting there and applying the end-part sequence will hit the end-point. (In each step you consider the two possible predecessors of each point, and add the end-point. The two possible predecessors for a square S, for an R-move is the square, S, and its L-neighbour if valid, Move(S, L). Each of these is only added if Move(S', R)==S.) (Could post entire code later.)

They are then given the distance m, and their neighbours distance m+1, etc.

Then you apply a A*search using this heuristic.

That took 1 minutes to go from RRDRRDRLDRDLDLULLLDDRDDRDURRDRRD (32 long) keeping first 7 and last 11 giving RRDRRDRDLDDULDLDLDRDDRDURRDRRD (30 long) and keeping first 15 then took half a minute to find RRDRRDRDLDDULDLDLDRDRDURDRRDR (29 long!)

And note that there are 2423 reachable mazes, but only 2083 of them need to be considered, as the others have squares that can only be reached by passing through the end-point.