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.

Nitpicking

With this problem space, brute force will definitely not take years - minutes at most, and probably seconds. You have at most 2 to the power of 14 possible configurations (that's 4*4 squares minus the start and goal), and some of those will be invalid (goal can't be reached). That is not to say there couldn't exist a heuristic that beats the brute force search. – Postal

@500-InternalServerError There are 4000^16 possible configurations, since in each of the 4000 mazes you can be in one of at most 16 different positions. That's vastly beyond what can be brute-forced. – Fathometer

@templatetypedef: How many unique paths are there from top left square to bottom right in an otherwise empty 4x4 matrix - surely not 4000^16? – Postal

@500-InternalServerError My apologies, I was thinking about it differently. I'm not completely convinced that you can solve every maze concurrently with a path that doesn't repeat itself. Consider four mazes where in one you have to diagonally zig-zag up and right, one in which you have to diagonally zig-zag up and left, on in which you have to zig-zag down and right, and one where you have to zig-zag down and left. I think you'd need at least 28 moves total, since each sequence of moves can only make progress in one of the mazes. – Fathometer

Please explain how one sequence can solve both of the example mazes in your question. A move to (1,1) (zero-based) is absolutely necessary in the second maze, and absolutely impossible in the first. – Vandal

@גלעדברקן בר Well... for example DRDRDRRR – Nitpicking

@OlaviMustanoja the second move is impossible in the first maze, that square is blocked. – Vandal

@גלעדברקן Ah, sorry for not mentioning: moving to blocked squares simply makes the robot not go there. – Nitpicking

@500-InternalServerError I think there are indeed way fewer than 2^14 mazes: we can ignore the ones that have no path from start to finish and the ones that are equivalent to others, because certain non-wall cells are not reachable. I bruteforced all possible mazes and came to a grand total of 2423 different mazes, modulo mistakes on my side of course... – Katzenjammer

@OlaviMustanoja can you provide one example only where UP must be used? – Vandal

@above The path must start with either down or right. Suppose it starts with down and gets trapped there (no down and right possible). Then up is required. – Katzenjammer

@above I see what you mean - I meant one maze where UP must be used. – Vandal

@above There is no one maze where UP must be used. If we had just a single maze we would only ever need RIGHT and DOWN – Nitpicking

See edits. Linked a pastebin. – Nitpicking

I used some lose reasoning and sketchy diagrams that seem to imply there are a mere 2176 solvable mazes. Using more solid math I can prove it's lower than 10240. – Demark

No wait, I figured out an ordering. I'm pretty sure there's 3104 solvable 4x4 mazes from top left to bottom right. ideone.com/0mrNH8 – Demark

@MooingDuck what do ! and ? indicate? – Nitpicking

@OlaviMustanoja: Both indicate squares that could be either # or .. I ordered the mazes by the "leftmost lowest" path of 6 moves that could solve them, and beneath are the number of mazes in each category. The ! mirror the #, because I thought that would be needed, but it turns out to be irrelevant. – Demark

@MooingDuck How did you decide where to place the #s and ?s ? – Nitpicking

Let us continue this discussion in chat. – Demark

Nice to see you made progress with my idea, I doubt I could've done that much. (I deleted the answer when I realized that I overlooked some things, and I was also annoyed that people downvoted the answer without appreciating it's positive creative aspects, case in point.) – Vandal

by the way, do you have the 29 move solution? – Vandal

@גלעדברקן בר I don't :/ – Nitpicking

@גלעדברקן Btw if you post your answer again, I'll surely upvote it :) – Nitpicking

@OlaviMustanoja do you have some code that you wouldn't mind sharing, where one could type in a sequence to test if it works? I have some more ideas... – Vandal

@גלעדברקן Sure, here is my complete code right now: pastebin.com/C1NV6F6q It's a complete chaos, since there's a lot of tests and temporary stuff going on. I commented the relevant methods in main() – Nitpicking

@OlaviMustanoja Thanks - would it be too much trouble for you to make an Ideone.com version, where it would also compile the code? I'm not too experienced with Java and was not sure how to fix the compilation errors i got, but wouldn't mind trying a few sequences... – Vandal

@גלעדברקן Sure, here's the link: ideone.com/Ej9Ntt – Nitpicking

Not sure if it's helpful, but there is a xkcd forum thread from 2013 that discusses a similar problem with a larger maze (2013x2013): forums.xkcd.com/viewtopic.php?f=3&t=99535 – Larimore

Also, having a base solution string and a score (number of mazes solved) seems like a perfect application for a genetic algorithm. – Larimore

@Larimore Nice find! I didn't find any of the discussion helpful, though. They don't seem to be interested in generating the smallest possible sequence - only one that works – Nitpicking

@Fathometer these might interest you: pdfs.semanticscholar.org/4b3b/… and ics.uci.edu/~eppstein/pubs/Epp-SJC-90.pdf The first paper doesn't find a solution for 4x4, interestingly, but they suggest that the problem can be modeled as finding a synchronizing sequence for a graph, for which the second paper provides a polynomial time algorithm. – Vandal

@Fathometer the first paper also offers a discussion vis a vis SAT. – Vandal

@גלעדברקן The first paper only mentions SAT when it reduces it to the problem (similar to ours) "given a set of mazes, is there a simultaneous solution of given length?", in order to show that that problem is NP-complete. – Blur

Answer 1

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.

Blur

Is there more than one length-29 solution? – Vandal

Can you show us how you encoded this as a SAT instance? – Fathometer

@גלעדברקן Yes I made a mistake sorry, my point is that you should be able to mirror each solution and it has to be one too. (Substitute R=>D, D=>R, L=>U and U=>L). – Feudalism

@גלעדברקן It would be DDRDDRDRURURLUURURDRRLDRDDRDD, this time 29 characters, no one missing I think. – Feudalism

@Feudalism cool, it works. Now my question becomes, Is there more than one length-29 solution (aside from the mirrored one)? – Vandal

It's interesting how few U and L there are in the sequence. – Vandal

It's also of note that at least one maze ends exactly on the twenty ninth move. I wonder if that can be a useful heuristic. – Vandal

That's awesome. If you could add words to describe basically how the problem can be formulated logically that would be great. By the way, I'm not sure if it's relevant to your formulation but I just enumerated only 2423 reachable paths, which is significantly less than the 3828 reported on this page, noting that many mazes in that list differ in areas that are unreachable. – Vandal

@גלעדברקן Yes, nicereachable checks that all positions are either reachable or walls. Computing length [ r | Just r <- map nicereachable [0..2^14-1]] gives 2423. – Blur

@גלעדברקן Other solutions: instead of examining the whole search space, I asked for a solution that starts with the same 9 directions as the old solution, and differs at some other position. After only 45 minutes, I found this amazing solution: RRDRRDRDLDDULDLLDDRDDDURDRRDR. Note the triple repetition! – Blur

That's really cool! Interesting that it also does not include any dduu or rrll, as j_random_hacker suggested. – Vandal

My code found this one: RRDRRDRDLDLDULLLDDRDDURDRRDRR just now in 95 minutes, given the initial 9. – Vandal

@Fathometer I finally described the encoding. – Blur

@גלעדברקן You were also interested in the encoding that I now added. – Blur

Answer 2

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 

Larimore

A nice idea and impressive results! If I understood it correctly, finding shorter solutions becomes hard if changes have to be made nearer to the beginning of the sequence, yes? – Nitpicking

No, making changes at the beginning of the sequence would indeed be the next thing worth a try. It's all about the search space. With a 20-31 chars starting sequence and a maximum length of 33 or less, the A* search finishes quickly and as it turns out, gives quite good results. On the contrary, starting with a short starting sequence (e.g. "R") as you would usually quickly eats up memory and time as Ilmari said. Of course, it all depends on the quality of the starting sequence and it turns out your 33 character solution is a good start. So it's 20% using A* a bit differently and 80% luck :) – Larimore

Answer 3

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!

Fathometer

I went and tried to get the minimum steps of all the mazes at their respective current position and sum all of those and make a move that results in the lowest sum. It didn't work because of endless ties between Right and Down – Nitpicking

I'll try A* next, though I think my previous score (78 commands) came from this very idea :D – Nitpicking

I tried solving this with A*, but while it easily solves the 3x4 case, it doesn't scale well to 4x4: the branching factor is too high, the heuristic is not discriminating enough, and it just ends up using way too much memory (I ran out at 15GB, even after hashing the visited states down to 64 bits). I think something like a heuristic-guided IDDFS might work better here. – Shalna

A finer-grained heuristic would be to sum the minimal distances for each maze, and then divide by the number of mazes. This will favour moves that bring some mazes closer to solution, but it's still a valid heuristic since it must come to less than the maximum of these minimums. Also if two partial solutions differ only in their maximum min-path, then it will order them the same way as the original heuristic. Variations are possible, e.g. taking a*(max-min-path) + (1-a)*(min-min-path), for some 0 <= a < 1. – Suit

@IlmariKaronen: Alternatively you might be able to get much stronger lower bounds by exactly computing the minimum number of moves required to solve some chosen subset of k mazes. This is Shortest Path in a 16^k-vertex graph of k-tuples of robot positions -- for k=2 this is already too big for a lookup table, but still fast to compute exactly with Dijkstra. I would use k=2 and pick the 2 mazes with largest individual distances to the goal. Also don't forget to throw away all solutions with LB > best-UB-so-far (currently 29) :) – Suit

Answer 4

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.

Suit

+1, your first point could be used to easily speed up @Vincent's implementation (he gets all permutations of moves of length k) – Nitpicking

@MooingDuck: I think you misunderstood my point: We need to try all mazes; we don't need to try any sequence of moves starting with D. – Suit

Oh right, I get it, I interpreted "solution" as "current path", but that's not what you said. – Demark

This is useful for generating all possible mazes, but doesn't say much about all possible paths. Even assuming the first move is R, if you look at the R->D that had to succeed, is that RD, RRD, RRRD, RURD, RRUD, RURRD, RRURD, or... and that doesn't include any Ls! Actually, we can discard any paths that have UD, DU, LR, RL when the first couldn't possibly be the end point, and discard all U before the first D too... – Demark

@MooingDuck: That is true, but only provided it holds across every maze. E.g. in the R->D example, while it holds for the leftmost maze, it doesn't hold for the rightmost maze: the robot in that maze makes progress on the D step. – Suit

@MooingDuck: Actually forget the second sentence in my previous comment, that's not quite the right example. But it's still the case that your condition has to hold across the robot's current position in each possible maze (that we haven't reached g on yet) for this to be a safe pruning step. IOW if any robot can make progress in some direction, we have to consider moving in that direction. – Suit

Answer 5

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

Katzenjammer

Would you post the solutions you have? – Subtropical

@Olavi I updated the algorithm a tiny bit, which leads to slightly better results. Still nothing compared to your 41. Good job! – Katzenjammer

@VincentvanderWeele Good job! I'll study your changes later today :) – Nitpicking

Answer 6

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.

Severson

@MooingDuck beat me :D Anyway I composed a small list of failing cases: pastebin. I like your idea however! If we have a sequence that definitely gets to the goal when done twice (but mirrored on the second run), it would explain the answer with only 29 moves! – Nitpicking

With such a limited subset of failing cases, one could probably just tack on an "escape" out of those five, and then continue the original pattern to the exit: URURRDLDL-DDDRR? That's what? 30? Assuming I had no errors? – Demark

@MooingDuck I just picked some randomly from all the failed cases. There were about 800 that failed. – Nitpicking

@MooingDuck 880 to be exact – Nitpicking

Answer 7

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.

Andreasandree

I was just actually doing this. With a slightly different sequence, which was 39 characters long, I was able to reduce it (by hand) to be 33 characters long. I'm editing my post in a second. – Nitpicking

Answer 8

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

Severson

Answer 9

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.

Adest

Huh. I saw the 2083 number when I accidentally enumerated mazes without the endpoint. I wasn't sure if it would be correct so I kept with 2423. – Vandal

The code I posted in my answer worked in 17 seconds (referencing 2423, not 2083 mazes) provided with the first 15 of RRDRRDRDLDDULDLDLDRDDRDURRDRRD. – Vandal

It's a nice observation that only 2083 mazes need to be considered! – Blur

Answer 10

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.

Subtropical

basically DRDRDRDRD :D – Nitpicking

Rows/columns can be swapped so it could be RDRDRDRDR :D. Seems like the wall follower maze solver algorithm might be useful as well. – Subtropical

@OlaviMustanoja: The suggested solution is to "go diagonal down right" x8. My escape on גלעד ברקן's answer appears to be "go diagonal up right"x2.5, "go diagonal down right" x1, "go diagonal down left" x2.5, then "go diagonal down right" x2. I bet there's a hint there. – Demark