About

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

CategorySnippet