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

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