Friday, January 07, 2005

ASCII A-maze-ment Puzzle

ITASoftware put up a little puzzle to write a program that can solve some ascii mazes. Finding it fun I sat down for an evening and wrote up a solution. The source contains two programs (solmaze and genmaze). genmaze will generate a maze of any size in two different ASCII styles. solmaze will solve the above problem. solmaze's solution uses a recursive back track solution and will uses stack space up to the size of the maze. genmaze will only use the amount of memory equivalent to two rows in generating the maze. For much more detail see the source code files.

You can download the source code off github.

The original problem text:
ASCII Maze. Write a program that reads in a simple 2-D ASCII maze and outputs the same maze, but with the solution filled in.

The input is guaranteed to be a well-formed maze and to have a unique solution path from the bottom left grid cell to the top right grid cell. Your program should re-output the maze with the solution path filled in.
Input:

_______________________END
| | | |
|__ |_____ | ______|
| | | |
| ___ |_____ | |
| | | | | |
| | | ___ | | |
| | | | | | |
| |_____ |__|__|__| |
| | |
Start|__|____________________|

Output:

_______________________END
| | |XX XX XX|
|__ |_____ | ______|
|XX XX XX| XX| |
| ___ |_____ | |
|XX| |XX XX XX XX| | |
| | | ___ | | |
|XX| | | | | |
| |_____ |__|__|__| |
|XX| |
Start|__|____________________|

No comments:

Popular Posts