Code Golf: Solve a Maze

Question

Here's an interesting problem to solve in minimal amounts of code. I expect the recursive solutions will be most popular.

We have a maze that's defined as a map of characters, where '=' is a wall, a space is a path, '+' is your starting point, and '#' is your ending point. An incredibly simple example is like so:

====
+  =
= ==
=  #
====

Can you write a program to find the shortest path to solve a maze in this style, in as little code as possible?

Bonus points if it works for all maze inputs, such as those with a path that crosses over itself or with huge numbers of branches. The program should be able to work for large mazes (say, 1024x1024 - 1 MB), and how you pass the maze to the program is not important.

UPDATE: The "player" may move diagonally. The input maze will never have a diagonal passage, so your base set of movements will be up, down, left, right. A diagonal movement would be merely looking ahead a little to determine if a up/down and left/right could be merged.

UPDATE #2: Fixed maximum size.

UPDATE #3: Output must be the maze itself with the shortest path highlighted using the asterisk character (' * ').

Answer 1

Guess its a simple A.I. problem. Read A* ("A Star") search algorithm.

Answer 2

Works for any (fixed-size) maze with a minimum of CPU cycles (given a big enough BFG2000). Source size is irrelevant since the compiler is incredibly efficient.

while curr.x != target.x and curr.y != target.y:
    case:
        target.x > curr.x : dx =  1
        target.x < curr.x : dx = -1
        else              : dx =  0
    case:
        target.y > curr.y : dy =  1
        target.y < curr.y : dy = -1
        else              : dy =  0
    if cell[curr.x+dx,curr.y+dy] == wall:
        destroy cell[curr.x+dx,curr.y+dy] with patented BFG2000 gun.
   curr.x += dx
   curr.y += dy
survey shattered landscape

Answer 3

I'd say have a look here:

http://www.astrolog.org/labyrnth/algrithm.htm

The maze solving section has plenty of differnet algorithms (including the "recursive backtracker" mentioned by the author)

Shortest path finder implementation:

http://www.codeproject.com/KB/recipes/mazesolver.aspx

Answer 4

F#, not very short (72 non-blank lines), but readable. I changed/honed the spec a bit; I assume the original maze is a rectangle fully surrounded by walls, I use different characters (that don't hurt my eyes), I only allow orthogonal moves (not diagonal). I only tried one sample maze. Except for a bug about flipping x and y indicies, this worked the first time, so I expect it is right (I've done nothing to validate it other than eyeball the solution on the one sample I gave it).

open System

[<Literal>]
let WALL  = '#'
[<Literal>]
let OPEN  = ' '
[<Literal>]
let START = '^'
[<Literal>]
let END   = '$'
[<Literal>]
let WALK  = '.'

let sampleMaze = @"###############
#  # #        #
# ^# # # ###  #
#  # # # # #  #
#      #   #  #
############  #
#    $        #
###############"

let lines = sampleMaze.Split([|'\r';'\n'|], StringSplitOptions.RemoveEmptyEntries)
let width = lines |> Array.map (fun l -> l.Length) |> Array.max 
let height = lines.Length 
type BestInfo = (int * int) list * int // path to here, num steps
let bestPathToHere : BestInfo option [,] = Array2D.create width height None

let mutable startX = 0
let mutable startY = 0
for x in 0..width-1 do
    for y in 0..height-1 do
        if lines.[y].[x] = START then
            startX <- x
            startY <- y
bestPathToHere.[startX,startY] <- Some([],0)

let q = new System.Collections.Generic.Queue<_>()
q.Enqueue((startX,startY))
let StepTo newX newY (path,count) =
    match lines.[newY].[newX] with
    | WALL -> ()
    | OPEN | START | END -> 
        match bestPathToHere.[newX,newY] with
        | None ->
            bestPathToHere.[newX,newY] <- Some((newX,newY)::path,count+1)
            q.Enqueue((newX,newY))
        | Some(_,oldCount) when oldCount > count+1 ->
            bestPathToHere.[newX,newY] <- Some((newX,newY)::path,count+1)
            q.Enqueue((newX,newY))
        | _ -> ()
    | c -> failwith "unexpected maze char: '%c'" c
while not(q.Count = 0) do
    let x,y = q.Dequeue()
    let (Some(path,count)) = bestPathToHere.[x,y]
    StepTo (x+1) (y) (path,count)
    StepTo (x) (y+1) (path,count)
    StepTo (x-1) (y) (path,count)
    StepTo (x) (y-1) (path,count)

let mutable endX = 0
let mutable endY = 0
for x in 0..width-1 do
    for y in 0..height-1 do
        if lines.[y].[x] = END then
            endX <- x
            endY <- y

printfn "Original maze:"
printfn "%s" sampleMaze
let bestPath, bestCount = bestPathToHere.[endX,endY].Value
printfn "The best path takes %d steps." bestCount
let resultMaze = Array2D.init width height (fun x y -> lines.[y].[x])
bestPath |> List.tl |> List.iter (fun (x,y) -> resultMaze.[x,y] <- WALK)
for y in 0..height-1 do
    for x in 0..width-1 do
        printf "%c" resultMaze.[x,y]
    printfn ""

//Output:
//Original maze:
//###############
//#  # #        #
//# ^# # # ###  #
//#  # # # # #  #
//#      #   #  #
//############  #
//#    $        #
//###############
//The best path takes 27 steps.
//###############
//#  # #....... #
//# ^# #.# ###. #
//# .# #.# # #. #
//# .....#   #. #
//############. #
//#    $....... #
//###############

Answer 5

Python

387 Characters

Takes input from stdin.

import sys
m,n,p=sys.stdin.readlines(),[],'+'
R=lambda m:[r.replace(p,'*')for r in m]
while'#'in`m`:n+=[R(m)[:r]+[R(m)[r][:c]+p+R(m)[r][c+1:]]+R(m)[r+1:]for r,c in[(r,c)for r,c in[map(sum,zip((m.index(filter(lambda i:p in i,m)[0]),[w.find(p)for w in m if p in w][0]),P))for P in zip((-1,0,1,0),(0,1,0,-1))]if 0<=r<len(m)and 0<=c<len(m[0])and m[r][c]in'# ']];m=n.pop(0)
print''.join(R(m))

Answer 6

I did this sort of thing for a job interview once (it was a pre-interview programming challenge)

Managed to get it working to some degree of success and it's a fun little challenge.