Prolog is aMAZEing

Write a Prolog agent to find a path from the entrance to the exit of a maze. Your agent does not know the layout of the maze in advance, and must explore the maze using its sensors. The goal is to find a path from the entrance to the exit making as few moves as possible. Of course shorter paths are preferred, but that is a secondary goal.

A maze is described as terms in a file that your program reads. The file has one line for each usable square of the maze. Each line is a . terminated Prolog term of the form:
square(X-coordinate,Y-coordinate,Status).
where the coordinates have the North-West corner as 0,0. The status value is either entrance, exit, or unknown. The order in which the squares are listed in the file is arbitrary. For example, the (very simple) 3x3 maze:

     X 0 1 2
    Y+------+
    0| EWW  |
    1|      |
    2|  WW X|
     +------+

can be represented by:

    square(0, 0, entrance).
    square(2, 0, unknown).
    square(0, 1, unknown).
    square(1, 1, unknown).
    square(2, 1, unknown).
    square(0, 2, unknown).
    square(2, 2, exit).

These mazes are solved by taking steps to usable adjacent squares, in one of the four directions. The solution to the above maze is 0,0->0,1->0,2->1,1->2,1->2,0->2,2.

Agents' actions must be implemented by calling procedures in the maze controller module. The controller provides six actions that agents can perform:

read_maze(MazeFile,Entrance,Exit)
Loads the maze from the MazeFile. The Entrance and Exit square/3 terms are returned.
draw_maze(Path)
Draws the maze, highlighting the Path (a list of square/3 terms). The location of the agent is marked with a *. The location of the entrance is marked with a E. The location of the exit is marked with a X. Squares on the Path are marked with a -. Squares that have been visited are marked with a +. Squares that have not been visited are unmarked.
my_state(CurrentSquare,MovesMade)
Returns the CurrentSquare and the number of MovesMade by the agent.
sense(North,South,West,East)
Returns the four square/3 terms, listing the adjacent squares.
move(Square)
Moves the agent to the adjacent Square. When the agent moves into a square with unknown status, the status changes to been_there.
exit(Path)
Allows the agent to exit the maze if it is at the exit, and the Path is a valid path from the entrance to the exit. This must be called exactly once by the agent when it is complete.

In order to use the controller module, it is compiled with yout agent program, and calls to the controller procedures are prefixed with controller:, e.g., controller:my_state(CurrentSquare,MovesMade). You may not modify the controller in any way.

Your program's entry point must be a clause maze/2, where the first argument is the name of the file containing the maze, and the second returns the path as a list of square/3 terms, from the entrance to the exit. Your agent may not read the maze file - it must use the controller read_maze procedure and gain knowledge of the maze using the controller's sense procedure.

It's really easy to write a depth first search maze solver that reports the first path it finds. Here's a sample run, with the user's keyboard input in italics:

    [eclipse 1]: compile('MazeSolverDFS').
    MazeController compiled traceable 10160 bytes in 0.02 seconds
    MazeSolverDFS compiled traceable 2064 bytes in 0.03 seconds
    
    Yes (0.03s cpu)
    [eclipse 2]: maze('Mazes/Maze0',Path).
     X 0 1 2
    Y+------+
    0|*EWW  |
    1|      |
    2|  WW X|
     +------+
    ------------------------------------------------------
     X 0 1 2
    Y+------+
    0| EWW -|
    1| + + +|
    2| -WW*X|
     +------+
    SUCCESS: 8 moves, path length 4 - 0,0->0,1->1,1->2,1->2,2
    
    Path = [square(0, 0, entrance), square(0, 1, unknown), square(1, 1, unknown), square(2, 1, unknown), square(2, 2, exit)]

You must submit your program file(s) using the submit2 program:

    ~csc545/bin/submit2 csc545 MazeSolver your_file_name

by 7am on 7th April. Your program must run under Eclipse Prolog. Your program will be assessed by testing it on ten test mazes - these five ... TestMaze1, TestMaze2, TestMaze3, TestMaze4, TestMaze5, and five other unseen mazes. The marks are distributed as follows:

Moves made to find path - 50%
Length of path found - 30%
Prolog programming style - 20%

It is worth 20% of the subject's assessment. Please review the policies on assessment in the administration document.

Solution

MazeSolver

If you would like to make some mazes of your own, you may like to use the MazeMaker program (which also requires the MazeController). It has the entry point make(Filename), where the Filename is the name of a file containing a maze in raw form, e.g.,

E  W   W    WXW
 W   W   WW W W
 WWW W WWWW W W
            W W
WWWW WWWWWW W W
W             W
WWWWWWWWWWWWWWW

is the raw form of TestMaze1.