Solving the Maze

One of the more intriguing challenges I've come across is finding your way out of a maze. Recently I played around with this in a Ruby class.

Firstly, how do we even simulate a maze? Without being too existential a maze can be thought of as a collection of steps, & with each step decisions have to be made. For this an array seems the right choice. In each value of the array we have a different location in the maze. Each location can have unique characters as to what is possible for that space.

"." - valid space
"G" - goal, end of maze
"#" - impassable barrier

For a 6x6 maze then we'd need an array with 36 spaces. This could be done with a simple function.

def reset
    @maze = []
    36.times { @maze << '#' }
    path = [0,6,7,8,9,10,13,15,19,24,25,26,32,33,34,28]
    path.each { |x| @maze[x] = '.' }
    @maze[29] = 'G'
end

Here we declare the array and fill it with impassable barriers. Next we take a number of locations and assign them as valid spaces, carving out a number of paths. Finally we mark one space as the end of the maze.

Another simple function could be used to draw a map of the maze.

def draw
    i = 0
    6.times {
        6.times {
            print @maze[i]
            i += 1
        }
        print "\n"
    }
end

Which now gives us this:

.#####
.....#
#.#.##
#.####
...#.G
##...#

So we have our maze! Now to find a path from the array's first location to the goal.

From the start, we have to ask ourselves a few questions. Firstly, am I even in the maze? Checking to see if the array's location isn't nil should be good for us for now. Next, are we at the goal? If not then it's best to keep going. But CAN we go? Checking to see if we're in a valid space can solve this. Ok, we can go but HOW do we move about? Adding one value to the array's index can move us to the left, subtracting one value moves us right. Subtracting six will us up one space (as we're in a six by six maze) & adding the same will move us down.

With this we can now construct another method.

def find_path(path)
    return false if @maze[path] == nil
    return true if @maze[path] == 'G'
    return false if @maze[path] != '.'
    @maze[path] = '+'
    return true if find_path(path - 6) == true
    return true if find_path(path + 1) == true
    return true if find_path(path + 6) == true
    return true if find_path(path - 1) == true
    @maze[path] = 'x'
    return false
end

After our initial checks we mark the space with a "+" to denote having come to that space. Then we try to move, each time repeating the same checks. If up doesn't go try right. If that doesn't work try down. If we come to a dead end mark the space with an "x" and return to the last call with additional choices. If the final call comes to another dead end the method returns false.

If not?

+#####
++xxx#
#+#x##
#+####
.++#+G
##+++#

Here we can see the method tried going one way and failed twice, reaching two dead ends. From there it returned to the previous call which allowed down as a viable direction & subsequently reached the goal!