Solving Mazes

Problem: Given an initial maze, how can we find the finish

• border cells marked by "#"
• start in the top left corner
• finish is marked by "F"

Example

    #############
    #+      ### #
    # # ###  #  #
    #####   ### #
    # ### ####  #
    #     #    ##
    # ### #######
    # #   #    ##
    #F# #   ##  #
    #############

First try right

    #############
    #++     ### #
    # # ###  #  #
    #####   ### #
    # ### ####  #
    #     #    ##
    # ### #######
    # #   #    ##
    #F# #   ##  #
    #############

        ...

    #############
    #+++++++### #
    # # ###  #  #
    #####   ### #
    # ### ####  #
    #     #    ##
    # ### #######
    # #   #    ##
    #F# #   ##  #
    #############

when you cannot try right, try left (unless that's been tried)
failing that, try up
next try down

    #############
    #+++++++### #
    # # ###+ #  #
    #####   ### #
    # ### ####  #
    #     #    ##
    # ### #######
    # #   #    ##
    #F# #   ##  #
    #############

always try right whenever possible

    #############
    #+++++++### #
    # # ###++#  #
    #####   ### #
    # ### ####  #
    #     #    ##
    # ### #######
    # #   #    ##
    #F# #   ##  #
    #############

if you reach a dead end, go back to the last intersection

    #############
    #+++++++### #
    # # ###+ #  #
    #####   ### #
    # ### ####  #
    #     #    ##
    # ### #######
    # #   #    ##
    #F# #   ##  #
    #############

now try the next option (down)

    #############
    #+++++++### #
    # # ###+ #  #
    #####  +### #
    # ### ####  #
    #     #    ##
    # ### #######
    # #   #    ##
    #F# #   ##  #
    #############

Continue the pattern:

1. try right (if you can, and it hasn't been tried already)
2. else try left (if you can, and it hasn't been tried already)
3. else try up (if you can, and it hasn't been tried already)
4. else try down (if you can, and it hasn't been tried already)
5. if dead end reached, backtrack to intersection

After a few more moves:

    #############
    #+++++++### #
    # # ###+ #  #
    #####+++### #
    # ###+####  #
    #    +#    ##
    # ### #######
    # #   #    ##
    #F# #   ##  #
    #############
 

SUCCESS

    #############
    #+++++++### #
    # # ###+ #  #
    #####+++### #
    # ###+####  #
    #+++++#    ##
    #+### #######
    #+#   #    ##
    #F# #   ##  #
    #############

Maze Code

with TEXT_IO;
procedure mazes is
    package int_io is new TEXT_IO.INTEGER_IO(INTEGER);
    use TEXT_IO,int_io;
    LENGTH: constant integer:=13;
    HEIGHT: constant integer:=10;

    type mazes is array(1..LENGTH,1..HEIGHT) of character;
    maze:mazes;
    success:boolean:=false;

    procedure getmaze(maze: out mazes) is
        filevar: TEXT_IO.FILE_TYPE;
    begin
                 
        open(FILE=>filevar,MODE=>IN_FILE,NAME=>"mazeinfo");  
        for y in 1..HEIGHT loop    
            for x in 1..LENGTH loop      
                get(filevar,maze(x,y));    
            end loop;    
            skip_line(filevar);  
        end loop;  
        close(filevar);
    end getmaze;

    procedure printmaze(maze: in mazes) is
    begin  
        for y in 1..HEIGHT loop
            for x in 1..LENGTH loop
                put(maze(x,y));
            end loop;
            new_line;
        end loop;
    end;

    procedure solvemaze(maze: in out mazes;
			x,y : integer;
			success:in out boolean) is

    begin
        printmaze(maze);
        if (maze(x,y)='F') then
            printmaze(maze);
            success:=true;
        end if;
        maze(x,y):='+';
        if (not success) and (maze(x+1,y)=' ' or maze(x+1,y)='F')   
		then solvemaze(maze,x+1,y,success);
        end if;
        if (not success) and (maze(x-1,y)=' ' or maze(x-1,y)='F') 
		then solvemaze(maze,x-1,y,success);
        end if;
        if (not success) and (maze(x,y-1)=' ' or maze(x,y-1)='F')  
		then solvemaze(maze,x,y-1,success);
        end if;
        if (not success) and (maze(x,y+1)=' ' or maze(x,y+1)='F')  
		then solvemaze(maze,x,y+1,success);
        end if;
        maze(x,y):=' ';
    end;
	
begin
    getmaze(maze);
    Solvemaze(maze,2,2,success);
    if (not success) then 
        printmaze(maze);
        put_line("There is no solution to this maze");
    else
        put_line("Success");
    end if;
end;