% This heuristic finds the path with the least amount of turns preferring to go stright.

% 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, south]).
end([2,6, _]).
% Maze Size
mazeSize([6,6]).

badSpot([X,Y, _]) :- wall([X,Y]).
badSpot([X,Y, _]) :- X < 1; Y < 1.
badSpot([X,Y, _]) :- mazeSize([W, H]), (X > W; Y > H).


% go stright
move([CurrX, CurrY, north], [CurrX, NextY, NewDir]) :- NextY is CurrY - 1, NewDir = north.
move([CurrX, CurrY, south], [NextX, NextY, NewDir]) :- NextY is CurrY + 1, NextX = CurrX, NewDir = south.
move([CurrX, CurrY, east], [NextX, NextY, NewDir]) :- NextY = CurrY, NextX is CurrX + 1, NewDir = east.
move([CurrX, CurrY, west], [NextX, NextY, NewDir]) :- NextY = CurrY, NextX is CurrX - 1, NewDir = west.
% left turn
move([CurrX, CurrY, north], [NextX, NextY, NewDir]) :- NextY = CurrY, NextX is CurrX - 1, NewDir = west, write("turn ").
move([CurrX, CurrY, south], [NextX, NextY, NewDir]) :- NextY = CurrY, NextX is CurrX + 1, NewDir = east, write("turn ").
move([CurrX, CurrY, east], [CurrX, NextY, NewDir]) :- NextY is CurrY - 1, NewDir = north, write("turn ").
move([CurrX, CurrY, west], [NextX, NextY, NewDir]) :- NextY is CurrY + 1, NextX = CurrX, NewDir = south, write("turn ").
% right turn
move([CurrX, CurrY, north], [NextX, NextY, NewDir]) :- NextY = CurrY, NextX is CurrX + 1, NewDir = east, write("turn ").
move([CurrX, CurrY, south], [NextX, NextY, NewDir]) :- NextY = CurrY, NextX is CurrX - 1, NewDir = west, write("turn ").
move([CurrX, CurrY, east], [NextX, NextY, NewDir]) :- NextY is CurrY + 1, NextX = CurrX, NewDir = south, write("turn ").
move([CurrX, CurrY, west], [CurrX, NextY, NewDir]) :- NextY is CurrY - 1, NewDir = north, write("turn ").
% backwords
move([CurrX, CurrY, north], [NextX, NextY, NewDir]) :- NextY is CurrY + 1, NextX = CurrX, NewDir = south.
move([CurrX, CurrY, south], [CurrX, NextY, NewDir]) :- NextY is CurrY - 1, NewDir = north.
move([CurrX, CurrY, east], [NextX, NextY, NewDir]) :- NextY = CurrY, NextX is CurrX - 1, NewDir = west.
move([CurrX, CurrY, west], [NextX, NextY, NewDir]) :- NextY = CurrY, NextX is CurrX + 1, NewDir = east.



solve(CurrentLocation, _ , Path) :- end(CurrentLocation), Path = [CurrentLocation].

solve(CurrentLocation,BeenThere, Path) :- move(CurrentLocation, NewLocation),
        \+badSpot(NewLocation),
        \+member(NewLocation, BeenThere),
        solve(NewLocation, [NewLocation | BeenThere], RestOfPath),
        Path = [CurrentLocation | RestOfPath].


solve(Path) :- start(Start), solve(Start, [Start], Path).
