# Labyrinth Solver

Creating code for labyrinth solvers is a quite traditional exercise. The following snippets provide versions in Python and in C of a concise labyrinth solver.

## Sample output

When run with the sample maze, the Python version will output the following result:

```###############
B+#     #   # #
#+# ### ### # #
#+# #+++++++# #
#+#+++### #+# #
#+#+#.#   #+#+F
#+++#.# # #+#+#
#####.# # #+#+#
#.....# # #+++#
###############```

## Snippet in Python

```NONE, WALL, BEGN, FNSH, SEEN, GOOD = tuple(' #BF.+')

SAMPLE = """
###############
B #     #   # #
# # ### ### # #
# # #       # #
# #   ### # # #
# # # #   # # F
#   # # # # # #
##### # # # # #
#     # # #   #
###############
"""

def solve(maze, posx, posy, sizex, sizey):
found = 0
if 0 <= posx < sizex and 0 <= posy < sizey:
if maze[posy][posx] in (NONE, BEGN):
if maze[posy][posx] == NONE:
maze[posy][posx] = SEEN
if (solve(maze, posx+1, posy, sizex, sizey) or
solve(maze, posx-1, posy, sizex, sizey) or
solve(maze, posx, posy+1, sizex, sizey) or
solve(maze, posx, posy-1, sizex, sizey)):
if maze[posy][posx] == SEEN:
maze[posy][posx] = GOOD
found = 1
elif maze[posy][posx] == FNSH:
found = 1
return found

def main():
maze = [list(x) for x in SAMPLE.splitlines() if x]
solve(maze, 0, 1, len(maze[0]), len(maze))
for line in maze:
print "".join(line)

if __name__ == "__main__":
main()```

## Snippet in C

```#include <stdio.h>

#define NONE 0
#define WALL 1
#define BEGN 2
#define FNSH 3
#define SEEN 4
#define GOOD 5

#define SIZEX 15
#define SIZEY 10

int maze[SIZEY][SIZEX] = {
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{2,0,1,0,0,0,0,0,1,0,0,0,1,0,1},
{1,0,1,0,1,1,1,0,1,1,1,0,1,0,1},
{1,0,1,0,1,0,0,0,0,0,0,0,1,0,1},
{1,0,1,0,0,0,1,1,1,0,1,0,1,0,1},
{1,0,1,0,1,0,1,0,0,0,1,0,1,0,3},
{1,0,0,0,1,0,1,0,1,0,1,0,1,0,1},
{1,1,1,1,1,0,1,0,1,0,1,0,1,0,1},
{1,0,0,0,0,0,1,0,1,0,1,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
};

int _solve(int maze[SIZEY][SIZEX], int posx, int posy)
{
int found = 0;
if (posx >= 0 && posx < SIZEX && posy >= 0 && posy < SIZEY) {
int curpos = maze[posy][posx];
if (curpos == NONE || curpos == BEGN) {
if (curpos == NONE)
maze[posy][posx] = SEEN;
if (_solve(maze, posx+1, posy) ||
_solve(maze, posx, posy+1) ||
_solve(maze, posx, posy-1) ||
_solve(maze, posx-1, posy)) {
if (curpos == NONE)
maze[posy][posx] = GOOD;
found = 1;
}
} else if (curpos == FNSH || curpos == GOOD) {
found = 1;
}
}
return found;
}

int solve(int maze[SIZEY][SIZEX])
{
int x, y;
int found = 0;
for (y = 0; y < SIZEY; y++)
for (x = 0; x < SIZEX; x++)
if (maze[y][x] == BEGN)
found |= _solve(maze, x, y);
return found;
}

void print(int maze[SIZEY][SIZEX])
{
int x,y;
for (y = 0; y < SIZEY; y++) {
for (x = 0; x < SIZEX; x++)
printf("%d ", maze[y][x]);
printf("\n", maze[y][x]);
}
}

int main()
{
solve(maze);
print(maze);
return 0;
}

/* vim:ts=4:sw=4:et
*/```

snippets/labsolver (last edited 2005-10-07 01:45:53 by 200)