List every route through the maze
List all the routes from the top-left to the bottom-right of a maze as strings of moves, trying the directions in a fixed order so the list comes out in dictionary order. About 18 minutes.
A move per step
A maze is a grid of 0s, which are open, and 1s, which are walls. You start at the top-left square and want to reach the bottom-right square, moving down, left, right or up. A route is written as the string of the moves, such as DDRR.
Keep the current route in a list of letters. Each time you step to a neighbouring square, add the letter of the move; if that step goes nowhere, remove it again.
path.append("R")
go(r, c + 1)
path.pop()At the start. Down is a wall, left is outside, so the first possible move is R.
Fixed order, no revisits
Try the moves in the order D, L, R, U. That is alphabetical order, so the routes are found in dictionary order.
A square on the current route must not be entered again, or a route could loop forever. Mark the square when you enter it and clear the mark when you leave. When you stand on the bottom-right square, save the joined string and return.
moves = [("D", 1, 0), ("R", 0, 1)]Why try the directions in the order D, L, R, U?
- AIt is alphabetical order, so the routes come out in dictionary order
- BIt finds routes faster
- CAny order gives the same list
Show the answer
It is alphabetical order, so the routes come out in dictionary order. Routes are compared letter by letter, starting at the first move.
All routes through a maze
You are given an n by n maze of 0s and 1s, where 1 is a wall and 0 is open. A rat starts at the top-left square and wants to reach the bottom-right square. Each move goes down (D), left (L), right (R) or up (U) to an open square, and a route may not visit a square twice. Return every possible route as a string of moves, in dictionary order. If the start or the target is a wall, or no route exists, return an empty list.
maze = [[0, 0, 0], [1, 1, 0], [0, 0, 0]] → ["RRDD"]
2 ≤ n ≤ 5