<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">% Explanation
% My heuristic: follow either the left or the right wall by choosing the closer side
% This heuristic is inspired by Part 1, which is the follow the left wall one. While doing that one, I was looking
% at the image of the maze, and I noticed that the left wall is so long. The right wall is, however, way shorter. 
% So if we are able to choose the shorter wall to follow, we can solve the maze faster. The way I determine which 
% side to follow is by looking at the horizontal distance between the starting point and the two sides of the maze.
% If the start point is closer to the left of the maze, we follow the left wall; else we follow the right wall.
% I think this heuristic was successful especially when compared to the left-wall-only-approach. However, there are
% several things that can be improved further:
% (1) Take the starting direction into consideration: right now I just set the starting direction as south directly in 
%     the parameter, so I know I have to look at the width of the maze to determine the distance. But I can make more   
%     cases so that different directions would work and the criteria of determining the distance would be different 
%     for each direction.
% (2) Walls with weird shape may cause trouble: let's say if I choose to follow the right wall. There is a possibility 
%     that right wall has a really weird shape that may cause us more work to solve the maze. Maybe I can find a 
%     better way (preferably mathematically) to determine which wall is a better option to follow?

% Row 1
wall([X,1]) :- X =\= 2.
% Row 2
wall([X,2]) :- X = 1; X = 4; X = 6.
% Row 3
wall([X,3]) :- X = 1; X = 2; X = 6.
% Row 4
wall([X,4]) :- X =\= 3,X =\= 5.
% Row 5
wall([X,5]) :- X = 1; X = 4; X = 6.
% Row 6
wall([X,6]) :- X =\= 2.
% Start / end
start([2,1]).
end([2,6]).
% Maze Size
mazeSize([6,6]).

% Directions
direction(n).
direction(e).
direction(s).
direction(w).
right_turn(n,e).
right_turn(e,s).
right_turn(s,w).
right_turn(w,n).
left_turn(n,w).
left_turn(e,n).
left_turn(s,e).
left_turn(w,s).

% Left wall check - direction matters
has_left_wall([CurrX, CurrY, e]) :- WallY is CurrY - 1, wall([CurrX, WallY]).
has_left_wall([CurrX, CurrY, s]) :- WallX is CurrX + 1, wall([WallX, CurrY]).
has_left_wall([CurrX, CurrY, w]) :- WallY is CurrY + 1, wall([CurrX, WallY]).
has_left_wall([CurrX, CurrY, n]) :- WallX is CurrX - 1, wall([WallX, CurrY]).

% Right wall check - direction matters
has_right_wall([CurrX, CurrY, e]) :- WallY is CurrY + 1, wall([CurrX, WallY]).
has_right_wall([CurrX, CurrY, s]) :- WallX is CurrX - 1, wall([WallX, CurrY]).
has_right_wall([CurrX, CurrY, w]) :- WallY is CurrY - 1, wall([CurrX, WallY]).
has_right_wall([CurrX, CurrY, n]) :- WallX is CurrX + 1, wall([WallX, CurrY]).

badSpot([X,Y]) :- wall([X,Y]).
badSpot([X,Y]) :- X &lt; 1; Y &lt; 1.
badSpot([X,Y]) :- mazeSize([W, H]), (X &gt; W; Y &gt; H).

%up
move([CurrX, CurrY, n], [CurrX, NextY, n]) :- NextY is CurrY - 1.
%down
move([CurrX, CurrY, s], [CurrX, NextY, s]) :- NextY is CurrY + 1.
%left
move([CurrX, CurrY, w], [NextX, CurrY, w]) :- NextX is CurrX - 1.
%right
move([CurrX, CurrY, e], [NextX, CurrY, e]) :- NextX is CurrX + 1.
%turn left
move([CurrX, CurrY, CurrDir], [CurrX, CurrY, NextDir]) :- left_turn(CurrDir, NextDir).
%turn right
move([CurrX, CurrY, CurrDir], [CurrX, CurrY, NextDir]) :- right_turn(CurrDir, NextDir).




% A solution of the maze from our current location is [] if our current location is the end.
leftSolve([EndX, EndY, s], _, Path) :- end([EndX, EndY]), Path = [[EndX, EndY]].
rightSolve([EndX, EndY, s], _, Path) :- end([EndX, EndY]), Path = [[EndX, EndY]].

% left wall case - if there is a wall to our left
leftSolve([CurrX, CurrY, CurrDir], BeenThere, Path) :- move([CurrX, CurrY, CurrDir], [NextX, NextY, CurrDir]), 
        \+badSpot([NextX, NextY]),
        %\+member([NextX, NextY, CurrDir], BeenThere),
		has_left_wall([CurrX, CurrY, CurrDir]),
        leftSolve([NextX, NextY, CurrDir], [[NextX, NextY, CurrDir] | BeenThere], RestOfPath), 
        Path = [[CurrX, CurrY] | RestOfPath].

% left wall case - if there is no wall to our left -&gt; gotta turn left and go forward
leftSolve([CurrX, CurrY, CurrDir], BeenThere, Path) :- move([CurrX, CurrY, CurrDir], [CurrX, CurrY, NextDir]), 
		left_turn(CurrDir, NextDir), 
    	\+has_left_wall([CurrX, CurrY, CurrDir]),
        %\+member([CurrX, CurrY, NextDir], BeenThere),
		move([CurrX, CurrY, NextDir], [NextX, NextY, NextDir]),
        \+badSpot([NextX, NextY]),
        %\+member([NextX, NextY, NextDir], BeenThere),
        leftSolve([NextX, NextY, NextDir], [[NextX, NextY, NextDir], [CurrX, CurrY, NextDir] | BeenThere], RestOfPath), 
        Path = [[CurrX, CurrY] | RestOfPath].

% left wall case - if there is a wall to our left but we can't go forward -&gt; turn around
leftSolve([CurrX, CurrY, CurrDir], BeenThere, Path) :- move([CurrX, CurrY, CurrDir], [BadX, BadY, CurrDir]),
    	badSpot([BadX, BadY]),
    	move([CurrX, CurrY, CurrDir], [CurrX, CurrY, NextDir]), 
        right_turn(CurrDir, NextDir),
        %\+member([CurrX, CurrY, NextDir], BeenThere),
		has_left_wall([CurrX, CurrY, CurrDir]),
        leftSolve([CurrX, CurrY, NextDir], [[CurrX, CurrY, NextDir] | BeenThere], RestOfPath), 
        Path = [[CurrX, CurrY] | RestOfPath].

% right wall case - if there is a wall to our right
rightSolve([CurrX, CurrY, CurrDir], BeenThere, Path) :- move([CurrX, CurrY, CurrDir], [NextX, NextY, CurrDir]), 
        \+badSpot([NextX, NextY]),
        %\+member([NextX, NextY, CurrDir], BeenThere),
		has_right_wall([CurrX, CurrY, CurrDir]),
        rightSolve([NextX, NextY, CurrDir], [[NextX, NextY, CurrDir] | BeenThere], RestOfPath), 
        Path = [[CurrX, CurrY] | RestOfPath].

% right wall case - if there is no wall to our right -&gt; gotta turn right and go forward
rightSolve([CurrX, CurrY, CurrDir], BeenThere, Path) :- move([CurrX, CurrY, CurrDir], [CurrX, CurrY, NextDir]), 
		right_turn(CurrDir, NextDir), 
    	\+has_right_wall([CurrX, CurrY, CurrDir]),
        %\+member([CurrX, CurrY, NextDir], BeenThere),
		move([CurrX, CurrY, NextDir], [NextX, NextY, NextDir]),
        \+badSpot([NextX, NextY]),
        %\+member([NextX, NextY, NextDir], BeenThere),
        rightSolve([NextX, NextY, NextDir], [[NextX, NextY, NextDir], [CurrX, CurrY, NextDir] | BeenThere], RestOfPath), 
        Path = [[CurrX, CurrY]| RestOfPath].

% right wall case - if there is a wall to our right but we can't go forward -&gt; turn around
rightSolve([CurrX, CurrY, CurrDir], BeenThere, Path) :- move([CurrX, CurrY, CurrDir], [BadX, BadY, CurrDir]),
    	badSpot([BadX, BadY]),
    	move([CurrX, CurrY, CurrDir], [CurrX, CurrY, NextDir]), 
        left_turn(CurrDir, NextDir),
        %\+member([CurrX, CurrY, NextDir], BeenThere),
		has_right_wall([CurrX, CurrY, CurrDir]),
        rightSolve([CurrX, CurrY, NextDir], [[CurrX, CurrY, NextDir] | BeenThere], RestOfPath), 
        Path = [[CurrX, CurrY] | RestOfPath].
	
% determine to follow the right or left wall by choosing the closer side
leftOrRightWall(StartX, StartY, W, Path) :- StartX =&lt; W/2, rightSolve([StartX, StartY, s], [[StartX, StartY, s]], Path).
leftOrRightWall(StartX, StartY, W, Path) :- StartX &gt; W/2, leftSolve([StartX, StartY, s], [[StartX, StartY, s]], Path).
	
% Convenience rule
solve(Path) :- start([StartX, StartY]), mazeSize([W, H]), leftOrRightWall(StartX, StartY, W, Path).

drawCell(Column, Row, _) :- wall([Column, Row]), write("X"), !.
drawCell(Column, Row, _) :- start([Column, Row]), write("S"), !.
drawCell(Column, Row, _) :- end([Column, Row]), write("E"), !.
drawCell(Column, Row, Path) :- member([Column, Row], Path), write("P"), !.
drawCell(_, _, _) :- write("O").

drawRow(Row, Path) :- drawCell(1, Row, Path), tab(1), drawCell(2, Row, Path), tab(1), 
        drawCell(3, Row, Path), tab(1), drawCell(4, Row, Path), tab(1), 
        drawCell(5, Row, Path), tab(1), drawCell(6, Row, Path), nl.
                
draw :- drawRow(1, []), drawRow(2, []), drawRow(3, []), drawRow(4, []), drawRow(5, []), 
        drawRow(6, []).
draw(Path) :- drawRow(1, Path), drawRow(2, Path), drawRow(3, Path), drawRow(4, Path),
        drawRow(5, Path), drawRow(6, Path).</pre></body></html>