%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                        %
% Franziska John, 738163, fjohn@...144...                           %
% Maximilian Moeller, 731283, miliano@...145...                    %
% Martin Wegner, 730430, mawegner@...144...                         %
%                                                                        %
% Verwendetes Prolog-System: "ECLiPSe"                                   %
%                                                                        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ihre Loesung                                                           %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- set_flag(debug_compile, off).

% arukone(+Puzzle, -Paths)
arukone(p(Width,Height,Config),Path) :-	!, generateVisited(Config,Visited), !,
										forceRangeOne([],Width,Height,Config,Visited,[],ForcedConfig,ForcedVisited,ForcedPaths), !,
										number_sort(1,<,ForcedConfig,SortedForcedConfig), !,
										parsePuzzle(Width,Height,SortedForcedConfig,ForcedVisited,ForcedPaths,Path).

% Hauptfunktion zur Berechnung einer Loesung des arukone Puzzles
parsePuzzle(_Width,_Height,[],_Visited,VisitedPaths,VisitedPaths) :- !.
parsePuzzle(Width,Height,[l(Number,SX,SY,FX,FY)|ConfigTail],Visited,VisitedPaths,Paths) :-

										!, legalMove((SX,SY),(FX,FY),Visited,Width,Height,(NewSX,NewSY)),
										forceRangeOne([],Width,Height,[l(Number,NewSX,NewSY,FX,FY)|ConfigTail],[(NewSX,NewSY)|Visited],[n(SX,SY,NewSX,NewSY)|VisitedPaths],ForcedConfig,ForcedVisited,ForcedPaths),
										reachTest(Width,Height,ForcedConfig,ForcedVisited),
										number_sort(1,<,ForcedConfig,SortedForcedConfig),
										parsePuzzle(Width,Height,SortedForcedConfig,ForcedVisited,ForcedPaths,Paths).

findMinimumRange([l(Number,SX,SY,FX,FY)],Width,Height,Visited,Minimum,Number) :-	!, findall(Move,legalMove((SX,SY),(FX,FY),Visited,Width,Height,Move),Moves), !,
																					length(Moves,Minimum), !.
findMinimumRange([l(Number,SX,SY,FX,FY)|ConfigTail],Width,Height,Visited,Minimum,NumberOfMin) :- 	!, findall(Move,legalMove((SX,SY),(FX,FY),Visited,Width,Height,Move),Moves), !,
																									length(Moves,FreedomNumber), !,
																									findMinimumRange(ConfigTail,Width,Height,Visited,Minimum2,NumberOfMin2), !,
																									((Minimum2 > FreedomNumber) ->
																										(Minimum = FreedomNumber, !, NumberOfMin = Number, !)
																										;
																										(Minimum = Minimum2, !, NumberOfMin = NumberOfMin2, !)), !.

% Freiheitsgrad 1 suchen und feste Felder setzen
forceRangeOne(ForcedConfig,_Width,_Height,[],ForcedVisited,ForcedPaths,ForcedConfig,ForcedVisited,ForcedPaths) :- !.
forceRangeOne(DoneConfig,Width,Height,[l(_Number,FX,FY,FX,FY)|ConfigTail],Visited,Paths,ForcedConfig,ForcedVisited,ForcedPaths) :- !, forceRangeOne(DoneConfig,Width,Height,ConfigTail,Visited,Paths,ForcedConfig,ForcedVisited,ForcedPaths), !.
forceRangeOne(DoneConfig,Width,Height,[l(Number,SX,SY,FX,FY)|ConfigTail],Visited,Paths,ForcedConfig,ForcedVisited,ForcedPaths) :-

										!, delete((FX,FY),Visited,VisitedWithoutFinish), !,
										delete((SX,SY),Visited,VisitedWithoutStart), !,
										append(DoneConfig,ConfigTail,DoneNTailConfig), !,
										(freedomRangeOne((SX,SY),VisitedWithoutFinish,Width,Height,(X1,Y1)) ->
											(StartForceable = true, !)
											;
											(StartForceable = fail, !)), !,
										(freedomRangeOne((FX,FY),VisitedWithoutStart,Width,Height,(X2,Y2)) ->
											(FinishForceable = true, !)
											;
											(FinishForceable = fail, !)), !,
										((StartForceable, FinishForceable, !,
										((X1 == X2, Y1 == Y2) ->
											(forceRangeOne(DoneConfig,Width,Height,ConfigTail,[(X1,Y1)|Visited],[n(SX,SY,X1,Y1),n(X2,Y2,FX,FY)|Paths],ForcedConfig,ForcedVisited,ForcedPaths), !)
											;
											(((X1 == FX, Y1 == FY, X2 == SX, Y2 == SY) ->
												(forceRangeOne(DoneConfig,Width,Height,ConfigTail,Visited,[n(SX,SY,X1,Y1)|Paths],ForcedConfig,ForcedVisited,ForcedPaths), !)
												;
												(forceRangeOne([],Width,Height,[l(Number,X1,Y1,X2,Y2)|DoneNTailConfig],[(X1,Y1),(X2,Y2)|Visited],[n(SX,SY,X1,Y1),n(X2,Y2,FX,FY)|Paths],ForcedConfig,ForcedVisited,ForcedPaths), !))), !), !)
										;
										(StartForceable, not(FinishForceable), !,
										((X1 == FX, Y1 == FY) ->
											(forceRangeOne(DoneConfig,Width,Height,ConfigTail,Visited,[n(SX,SY,X1,Y1)|Paths],ForcedConfig,ForcedVisited,ForcedPaths), !)
											;
											(forceRangeOne([],Width,Height,[l(Number,X1,Y1,FX,FY)|DoneNTailConfig],[(X1,Y1)|Visited],[n(SX,SY,X1,Y1)|Paths],ForcedConfig,ForcedVisited,ForcedPaths), !)), !)
										;
										(not(StartForceable), FinishForceable, !,
										((X2 == SX,Y2 == SY) ->
											(forceRangeOne(DoneConfig,Width,Height,ConfigTail,Visited,[n(SX,SY,FX,FY)|Paths],ForcedConfig,ForcedVisited,ForcedPaths), !)
											;
											(forceRangeOne([],Width,Height,[l(Number,SX,SY,X2,Y2)|DoneNTailConfig],[(X2,Y2)|Visited],[n(X2,Y2,FX,FY)|Paths],ForcedConfig,ForcedVisited,ForcedPaths), !)), !)
										;
										(not(StartForceable), not(FinishForceable), !,
										forceRangeOne([l(Number,SX,SY,FX,FY)|DoneConfig],Width,Height,ConfigTail,Visited,Paths,ForcedConfig,ForcedVisited,ForcedPaths), !)), !.

% Erreichbarkeitstest
reachTest(_Width,_Height,[],_Visited) :- !.
reachTest(Width,Height,[l(_Number,SX,SY,FX,FY)|ConfigTail],Visited) :-	!, delete((FX,FY),Visited,VisitedWithOutFinish), !,
																		pathFinder((SX,SY),(FX,FY),VisitedWithOutFinish,Width,Height), !,
																		reachTest(Width,Height,ConfigTail,Visited), !.

% Generieren einer Visited Liste
generateVisited([],[]) :- !.
generateVisited([l(_Number,SX,SY,SX,SY)|ConfigTail],[(SX,SY)|Visited]) :- !, generateVisited(ConfigTail,Visited), !.
generateVisited([l(_Number,SX,SY,FX,FY)|ConfigTail],[(SX,SY),(FX,FY)|Visited]) :- !, generateVisited(ConfigTail,Visited), !.

% pathFinder fuer den Erreichbarkeitstest Anfang

% Zielfeld erreicht
pathFinder(Finish,Finish,_Visited,_Width,_Height) :- !.

% linke obere Ecke
pathFinder((1,1),Finish,Visited,Width,Height) :-	!, ((X = 2, Y = 1)
														;
														(X = 1, Y = 2)),
														nonmember((X,Y),Visited),
														pathFinder((X,Y),Finish,[(X,Y)|Visited],Width,Height), !.

% linke untere Ecke
pathFinder((1,Height),Finish,Visited,Width,Height) :-	!, ((X = 2, Y = Height)
															;
															(X = 1, Y is Height - 1)),
															nonmember((X,Y),Visited),
															pathFinder((X,Y),Finish,[(X,Y)|Visited],Width,Height), !.

% rechte obere Ecke
pathFinder((Width,1),Finish,Visited,Width,Height) :-	!, ((X = Width, Y = 2)
															;
															(X is Width - 1, Y = 1)),
															nonmember((X,Y),Visited),
															pathFinder((X,Y),Finish,[(X,Y)|Visited],Width,Height), !.

% rechte untere Ecke
pathFinder((Width,Height),Finish,Visited,Width,Height) :-	!, ((X = Width, Y is Height - 1)
																;
																(X is Width - 1, Y = Height)),
																nonmember((X,Y),Visited),
																pathFinder((X,Y),Finish,[(X,Y)|Visited],Width,Height), !.

% linker Spielfeldrand
pathFinder((1,SY),Finish,Visited,Width,Height) :-	!, ((X = 2, Y = SY)
														;
														(X = 1, Y is SY + 1)
														;
														(X = 1, Y is SY - 1)),
														nonmember((X,Y),Visited),
														pathFinder((X,Y),Finish,[(X,Y)|Visited],Width,Height), !.

% rechter Spielfeldrand
pathFinder((Width,SY),Finish,Visited,Width,Height) :-	!, ((X is Width - 1, Y = SY)
															;
															(X = Width, Y is SY + 1)
															;
															(X = Width, Y is SY - 1)),
															nonmember((X,Y),Visited),
															pathFinder((X,Y),Finish,[(X,Y)|Visited],Width,Height), !.

% oberer Spielfeldrand
pathFinder((SX,1),Finish,Visited,Width,Height) :-	!, ((X = SX, Y = 2)
														;
														(X is SX + 1, Y = 1)
														;
														(X is SX - 1, Y = 1)),
														nonmember((X,Y),Visited),
														pathFinder((X,Y),Finish,[(X,Y)|Visited],Width,Height), !.

% unterer Spielfeldrand
pathFinder((SX,Height),Finish,Visited,Width,Height) :-	!, ((X = SX, Y is Height - 1)
															;
															(X is SX + 1, Y = Height)
															;
															(X is SX - 1, Y = Height)),
															nonmember((X,Y),Visited),
															pathFinder((X,Y),Finish,[(X,Y)|Visited],Width,Height), !.

% irgendwo im Spielfeld, aber nicht im Spielrand
pathFinder((SX,SY),Finish,Visited,Width,Height) :-	!, ((X = SX, Y is SY + 1)
														;
														(X is SX + 1, Y = SY)
														;
														(X = SX, Y is SY - 1)
														;
														(X is SX - 1, Y = SY)),
														nonmember((X,Y),Visited),
														pathFinder((X,Y),Finish,[(X,Y)|Visited],Width,Height), !.

% pathFinder fuer den Erreichbarkeitstest Ende

% legalMove Anfang

% linke obere Ecke
legalMove((1,1),Finish,Visited,_Width,_Height,Move) :-	!, delete(Finish,Visited,VisitedWithoutFinish), !,
														((X = 2, Y = 1)
														;
														(X = 1, Y = 2)),
														nonmember((X,Y),VisitedWithoutFinish),
														Move = (X,Y).

% linke untere Ecke
legalMove((1,Height),Finish,Visited,_Width,Height,Move) :-	!, delete(Finish,Visited,VisitedWithoutFinish), !,
															((X = 2, Y = Height)
															;
															(X = 1, Y is Height - 1)),
															nonmember((X,Y),VisitedWithoutFinish),
															Move = (X,Y).

% rechte obere Ecke
legalMove((Width,1),Finish,Visited,Width,_Height,Move) :-	!, delete(Finish,Visited,VisitedWithoutFinish), !,
															((X = Width, Y = 2)
															;
															(X is Width - 1, Y = 1)),
															nonmember((X,Y),VisitedWithoutFinish),
															Move = (X,Y).

% rechte untere Ecke
legalMove((Width,Height),Finish,Visited,Width,Height,Move) :-	!,  delete(Finish,Visited,VisitedWithoutFinish), !,
																((X = Width, Y is Height - 1)
																;
																(X is Width - 1, Y = Height)),
																nonmember((X,Y),VisitedWithoutFinish),
																Move = (X,Y).

% linker Spielfeldrand
legalMove((1,SY),Finish,Visited,_Width,_Height,Move) :-	!,  delete(Finish,Visited,VisitedWithoutFinish), !,
														((X = 2, Y = SY)
														;
														(X = 1, Y is SY + 1)
														;
														(X = 1, Y is SY - 1)),
														nonmember((X,Y),VisitedWithoutFinish),
														Move = (X,Y).

% rechter Spielfeldrand
legalMove((Width,SY),Finish,Visited,Width,_Height,Move) :-	!, delete(Finish,Visited,VisitedWithoutFinish), !,
															((X is Width - 1, Y = SY)
															;
															(X = Width, Y is SY + 1)
															;
															(X = Width, Y is SY - 1)),
															nonmember((X,Y),VisitedWithoutFinish),
															Move = (X,Y).

% oberer Spielfeldrand
legalMove((SX,1),Finish,Visited,_Width,_Height,Move) :-	!, delete(Finish,Visited,VisitedWithoutFinish), !,
														((X = SX, Y = 2)
														;
														(X is SX + 1, Y = 1)
														;
														(X is SX - 1, Y = 1)),
														nonmember((X,Y),VisitedWithoutFinish),
														Move = (X,Y).

% unterer Spielfeldrand
legalMove((SX,Height),Finish,Visited,_Width,Height,Move) :-	!, delete(Finish,Visited,VisitedWithoutFinish), !,
															((X = SX, Y is Height - 1)
															;
															(X is SX + 1, Y = Height)
															;
															(X is SX - 1, Y = Height)),
															nonmember((X,Y),VisitedWithoutFinish),
															Move = (X,Y).

% irgendwo im Spielfeld, aber nicht im Spielrand
legalMove((SX,SY),Finish,Visited,_Width,_Height,Move) :-	!, delete(Finish,Visited,VisitedWithoutFinish), !,
														((X = SX, Y is SY + 1)
														;
														(X is SX + 1, Y = SY)
														;
														(X = SX, Y is SY - 1)
														;
														(X is SX - 1, Y = SY)),
														nonmember((X,Y),VisitedWithoutFinish),
														Move = (X,Y).

% legalMove Ende

% Freiheitsgrad-1-Test Anfang

% linke obere Ecke
freedomRangeOne((1,1),Visited,_Width,_Height,FreeField) :-	!, (memberchk((2,1),Visited) ->
																(Mc1 = true, !)
																;
																(Mc1 = fail, !)), !,
															(memberchk((1,2),Visited) ->
																(Mc2 = true, !)
																;
																(Mc2 = fail, !)), !, 
															((not(Mc1), Mc2,
															FreeField = (2,1))
															;
															(Mc1, not(Mc2),
															FreeField = (1,2))).

% linke untere Ecke
freedomRangeOne((1,Height),Visited,_Width,Height,FreeField) :-	!, Y is Height - 1, !,
																(memberchk((2,Height),Visited) ->
																	(Mc1 = true, !)
																	;
																	(Mc1 = fail, !)), !,
																(memberchk((1,Y),Visited) ->
																	(Mc2 = true, !)
																	;
																	(Mc2 = fail, !)), !,
																((not(Mc1), Mc2,
																FreeField = (2,Height))
																;
																(Mc1, not(Mc2),
																FreeField = (1,Y))).

% rechte obere Ecke
freedomRangeOne((Width,1),Visited,Width,_Height,FreeField) :-	!, X is Width - 1, !,
																(memberchk((X,1),Visited) ->
																	(Mc1 = true, !)
																	;
																	(Mc1 = fail, !)), !,
																(memberchk((Width,2),Visited) ->
																	(Mc2 = true, !)
																	;
																	(Mc2 = fail, !)), !,
																((not(Mc1), Mc2,
																FreeField = (X,1))
																;
																(Mc1, not(Mc2),
																FreeField = (Width,2))).

% rechte untere Ecke
freedomRangeOne((Width,Height),Visited,Width,Height,FreeField) :-	!, X is Width - 1, !,
																	Y is Height - 1, !,
																	(memberchk((X,Height),Visited) ->
																		(Mc1 = true, !)
																		;
																		(Mc1 = fail, !)), !,
																	(memberchk((Width,Y),Visited) ->
																		(Mc2 = true, !)
																		;
																		(Mc2 = fail, !)), !,
																	((not(Mc1), Mc2,
																	FreeField = (X,Height))
																	;
																	(Mc1, not(Mc2),
																	FreeField = (Width,Y))).

% linker Spielfeldrand
freedomRangeOne((1,Y),Visited,_Width,_Height,FreeField) :-	!, Y1 is Y +1, !,
															Y2 is Y -1, !,
															(memberchk((1,Y1),Visited) ->
																(Mc1 = true, !)
																;
																(Mc1 = fail, !)), !,
															(memberchk((1,Y2),Visited) ->
																(Mc2 = true, !)
																;
																(Mc2 = fail, !)), !,
															(memberchk((2,Y),Visited) ->
																(Mc3 = true, !)
																;
																(Mc3 = fail, !)), !,
															((not(Mc1), Mc2, Mc3,
															FreeField = (1,Y1))
															;
															(Mc1, not(Mc2), Mc3,
															FreeField = (1,Y2))
															;
															(Mc1, Mc2, not(Mc3),
															FreeField = (2,Y))).

% rechter Spielfeldrand
freedomRangeOne((Width,Y),Visited,Width,_Height,FreeField) :-	!, Y1 is Y + 1, !,
																Y2 is Y - 1, !,
																X is Width - 1, !,
																(memberchk((Width,Y1),Visited) ->
																	(Mc1 = true, !)
																	;
																	(Mc1 = fail, !)), !,
																(memberchk((Width,Y2),Visited) ->
																	(Mc2 = true, !)
																	;
																	(Mc2 = fail, !)), !,
																(memberchk((X,Y),Visited) ->
																	(Mc3 = true, !)
																	;
																	(Mc3 = fail, !)), !,
																((not(Mc1), Mc2, Mc3,
																FreeField = (Width,Y1))
																;
																(Mc1, not(Mc2), Mc3,
																FreeField = (Width,Y2))
																;
																(Mc1, Mc2, not(Mc3),
																FreeField = (X,Y))).

% oberer Spielfeldrand
freedomRangeOne((X,1),Visited,_Width,_Height,FreeField) :-	!, X1 is X + 1, !,
															X2 is X - 1, !,
															(memberchk((X1,1),Visited) ->
																(Mc1 = true, !)
																;
																(Mc1 = fail, !)), !,
															(memberchk((X2,1),Visited) ->
																(Mc2 = true, !)
																;
																(Mc2 = fail, !)), !,
															(memberchk((X,2),Visited) ->
																(Mc3 = true, !)
																;
																(Mc3 = fail, !)), !,
															((not(Mc1), Mc2, Mc3,
															FreeField = (X1,1))
															;
															(Mc1, not(Mc2), Mc3,
															FreeField = (X2,1))
															;
															(Mc1, Mc2, not(Mc3),
															FreeField = (X,2))).

% unterer Spielfeldrand
freedomRangeOne((X,Height),Visited,_Width,Height,FreeField) :-	!, X1 is X + 1, !,
																X2 is X - 1, !,
																Y is Height - 1, !,
																(memberchk((X1,Height),Visited) ->
																	(Mc1 = true, !)
																	;
																	(Mc1 = fail, !)), !,
																(memberchk((X2,Height),Visited) ->
																	(Mc2 = true, !)
																	;
																	(Mc2 = fail, !)), !,
																(memberchk((X,Y),Visited) ->
																	(Mc3 = true, !)
																	;
																	(Mc3 = fail, !)), !,
																((not(Mc1), Mc2, Mc3,
																FreeField = (X1,Height))
																;
																(Mc1, not(Mc2), Mc3,
																FreeField = (X2,Height))
																;
																(Mc1, Mc2, not(Mc3),
																FreeField = (X,Y))).

% irgendwo im Spielfeld, aber nicht im Spielrand
freedomRangeOne((X,Y),Visited,_Width,_Height,FreeField) :-	!, X1 is X - 1, !,
															X2 is X + 1, !,
															Y1 is Y - 1, !,
															Y2 is Y + 1, !,
															(memberchk((X1,Y),Visited) ->
																(Mc1 = true, !)
																;
																(Mc1 = fail, !)), !,
															(memberchk((X2,Y),Visited) ->
																(Mc2 = true, !)
																;
																(Mc2 = fail, !)), !,
															(memberchk((X,Y1),Visited) ->
																(Mc3 = true, !)
																;
																(Mc3 = fail, !)), !,
															(memberchk((X,Y2),Visited) ->
																(Mc4 = true, !)
																;
																(Mc4 = fail, !)), !,
															((Mc1, Mc2, Mc3, not(Mc4),
															 FreeField = (X,Y2))
															;
															(Mc1, Mc2, not(Mc3), Mc4,
															 FreeField = (X,Y1))
															;
															(Mc1, not(Mc2), Mc3, Mc4,
															 FreeField = (X2,Y))
															;
															(not(Mc1), Mc2, Mc3, Mc4,
															FreeField = (X1,Y))).

% Freiheitsgrad-1-Test Ende

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Einige Testaufrufe                                                   %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

test :-
  tests([1,2,3,4,5,6,7,8,9,10]).

tests([]).
tests([X | L]) :-
  test(X),
  tests(L).

test(X) :-
  nl, write('Test '), write(X), write(': '),
  puzzle(X, P),
  paths(X, A),
  (A = [] ->
    (arukone(P, S) ->
      (
        write(P), nl,
        write('Failure (Unsolvable)'), nl,
        write('  Expected: No Solution'), nl,
        write('  Obtained: '), write(S)
      )
    ;
      ( nl, write('Success') )
    )
  ;
    (setof(S, sorted(P,S), B) ->
      (A == B ->
        ( nl, write('Success') )
      ;
        (
          write(P), nl,
          write('Failure (Different)'), nl,
          write('  Expected: '), write(A), nl,
          write('  Obtained: '), write(B)
        )
      )
    ;
      (
        write(P), nl,
        write('Failure (Solvable)'), nl,
        write('  Expected: '), write(A), nl,
        write('  Obtained: No Solution')
      )
    )
  ),
  nl.

sorted(P, S) :-
  arukone(P, A),
  sort(A, S).


puzzle(1,  p(5,5,[l(1,1,1,3,4),l(2,1,5,2,3),l(3,2,1,5,1),l(4,2,2,5,5)]) ).
puzzle(2,  p(5,5,[l(1,1,2,4,1),l(2,1,3,5,1),l(3,2,4,3,2),l(4,3,3,4,4)]) ).
puzzle(3,  p(5,5,[l(1,1,2,4,1),l(2,1,3,5,1),l(3,2,4,3,2),l(4,3,3,5,4)]) ).
puzzle(4,  p(6,6,[l(1,2,2,2,5),l(2,3,2,4,6),l(3,3,6,6,1),l(4,5,3,6,6),
                  l(5,5,6,6,2)]) ).
puzzle(5,  p(5,7,[l(1,1,3,5,1),l(2,1,7,3,5),l(3,2,2,4,3),l(4,2,5,3,6),
                  l(5,3,2,4,5),l(6,3,7,5,5)]) ).
puzzle(6,  p(7,5,[l(1,1,5,4,2),l(2,2,1,3,4),l(3,2,3,5,5),l(4,5,2,7,1),
                  l(5,6,5,7,3)]) ).
puzzle(7,  p(7,7,[l(1,1,2,3,6),l(2,1,4,3,2),l(3,1,7,2,4),l(4,2,6,4,5),
                  l(5,4,4,7,7),l(6,4,6,5,6),l(7,6,2,6,4)]) ).
puzzle(8,  p(7,7,[l(1,1,3,4,5),l(2,1,6,2,3),l(3,1,7,2,5),l(4,2,2,5,7),
                  l(5,4,6,7,2),l(6,6,2,6,7),l(7,6,4,6,6)]) ).
puzzle(9,  p(8,8,[l(1,1,1,5,5),l(2,1,4,6,2),l(3,2,1,7,7),l(4,2,2,6,4),
                  l(5,2,4,5,6),l(6,2,7,6,5),l(7,6,1,8,1)]) ).
puzzle(10, p(8,8,[l(1,2,4,7,2),l(2,2,5,5,3),l(3,2,7,7,7),l(4,3,3,5,6),
                  l(5,4,6,7,6),l(6,6,3,6,6)]) ).


paths(1,  [ [n(1,1,1,2),n(1,2,1,3),n(1,3,1,4),n(1,4,2,4),n(1,5,2,5),n(2,1,3,1),
             n(2,2,3,2),n(2,4,3,4),n(2,5,3,5),n(3,1,4,1),n(3,2,4,2),n(3,3,2,3),
             n(3,5,4,5),n(4,1,5,1),n(4,2,5,2),n(4,3,3,3),n(4,4,4,3),n(4,5,4,4),
             n(5,2,5,3),n(5,3,5,4),n(5,4,5,5)] ]).
paths(2,  [ [n(1,1,2,1),n(1,2,1,1),n(1,3,1,4),n(1,4,1,5),n(1,5,2,5),n(2,1,3,1),
             n(2,2,3,2),n(2,3,2,2),n(2,4,2,3),n(2,5,3,5),n(3,1,4,1),n(3,3,3,4),
             n(3,4,4,4),n(3,5,4,5),n(4,2,5,2),n(4,3,4,2),n(4,5,5,5),n(5,2,5,1),
             n(5,3,4,3),n(5,4,5,3),n(5,5,5,4)],
            [n(1,1,2,1),n(1,2,1,1),n(1,3,1,4),n(1,4,1,5),n(1,5,2,5),n(2,1,3,1),
             n(2,2,3,2),n(2,3,2,2),n(2,4,2,3),n(2,5,3,5),n(3,1,4,1),n(3,3,3,4),
             n(3,4,4,4),n(3,5,4,5),n(4,5,5,5),n(5,2,5,1),n(5,3,5,2),n(5,4,5,3),
             n(5,5,5,4)],
            [n(1,1,2,1),n(1,2,1,1),n(1,3,1,4),n(1,4,1,5),n(1,5,2,5),n(2,1,3,1),
             n(2,2,3,2),n(2,3,2,2),n(2,4,2,3),n(2,5,3,5),n(3,1,4,1),n(3,3,4,3),
             n(3,5,4,5),n(4,3,4,4),n(4,5,5,5),n(5,2,5,1),n(5,3,5,2),n(5,4,5,3),
             n(5,5,5,4)] ]).
paths(3,  []).
paths(4,  [ [n(1,1,2,1),n(1,2,1,1),n(1,3,1,2),n(1,4,1,3),n(1,5,1,4),n(1,6,1,5),
             n(2,1,3,1),n(2,2,2,3),n(2,3,2,4),n(2,4,2,5),n(2,6,1,6),n(3,1,4,1),
             n(3,2,3,3),n(3,3,3,4),n(3,4,3,5),n(3,5,4,5),n(3,6,2,6),n(4,1,5,1),
             n(4,2,5,2),n(4,3,4,2),n(4,4,4,3),n(4,5,4,6),n(5,1,6,1),n(5,2,6,2),
             n(5,3,6,3),n(5,4,4,4),n(5,5,5,4),n(5,6,5,5),n(6,3,6,4),n(6,4,6,5),
             n(6,5,6,6)] ]).
paths(5,  [ [n(1,1,2,1),n(1,2,1,1),n(1,3,1,2),n(1,4,2,4),n(1,5,1,4),n(1,6,1,5),
             n(1,7,1,6),n(2,1,3,1),n(2,2,2,3),n(2,3,3,3),n(2,4,3,4),n(2,5,2,6),
             n(2,6,3,6),n(3,1,4,1),n(3,2,4,2),n(3,3,4,3),n(3,4,3,5),n(3,7,4,7),
             n(4,1,5,1),n(4,2,5,2),n(4,4,4,5),n(4,6,5,6),n(4,7,4,6),n(5,2,5,3),
             n(5,3,5,4),n(5,4,4,4),n(5,6,5,5)],
            [n(1,1,2,1),n(1,2,1,1),n(1,3,1,2),n(1,4,2,4),n(1,5,1,4),n(1,6,1,5),
             n(1,7,1,6),n(2,1,3,1),n(2,2,2,3),n(2,3,3,3),n(2,4,3,4),n(2,5,2,6),
             n(2,6,3,6),n(3,1,4,1),n(3,2,4,2),n(3,3,4,3),n(3,4,3,5),n(3,7,4,7),
             n(4,1,5,1),n(4,2,5,2),n(4,4,4,5),n(4,7,5,7),n(5,2,5,3),n(5,3,5,4),
             n(5,4,4,4),n(5,6,5,5),n(5,7,5,6)] ]).
paths(6,  []).
paths(7,  [ [n(1,1,2,1),n(1,2,1,1),n(1,3,2,3),n(1,4,1,3),n(1,5,2,5),n(1,6,1,5),
             n(1,7,1,6),n(2,1,3,1),n(2,2,3,2),n(2,3,2,2),n(2,5,2,4),n(2,6,2,7),
             n(2,7,3,7),n(3,1,4,1),n(3,3,3,4),n(3,4,3,5),n(3,5,3,6),n(3,7,4,7),
             n(4,1,4,2),n(4,2,4,3),n(4,3,3,3),n(4,4,5,4),n(4,6,5,6),n(4,7,5,7),
             n(5,1,6,1),n(5,2,5,1),n(5,3,5,2),n(5,4,5,3),n(5,5,4,5),n(5,7,6,7),
             n(6,1,7,1),n(6,2,6,3),n(6,3,6,4),n(6,5,5,5),n(6,6,6,5),n(6,7,6,6),
             n(7,1,7,2),n(7,2,7,3),n(7,3,7,4),n(7,4,7,5),n(7,5,7,6),n(7,6,7,7)] ]).
paths(8,  [ [n(1,1,2,1),n(1,2,1,1),n(1,3,1,2),n(1,4,2,4),n(1,5,1,4),n(1,6,1,5),
             n(1,7,2,7),n(2,1,3,1),n(2,2,3,2),n(2,4,2,3),n(2,6,2,5),n(2,7,2,6),
             n(3,1,4,1),n(3,2,3,3),n(3,3,3,4),n(3,4,3,5),n(3,5,3,6),n(3,6,3,7),
             n(3,7,4,7),n(4,1,4,2),n(4,2,4,3),n(4,3,4,4),n(4,4,4,5),n(4,6,5,6),
             n(4,7,5,7),n(5,1,6,1),n(5,2,5,1),n(5,3,5,2),n(5,4,5,3),n(5,5,5,4),
             n(5,6,5,5),n(6,1,7,1),n(6,2,6,3),n(6,3,7,3),n(6,4,6,5),n(6,5,6,6),
             n(7,1,7,2),n(7,3,7,4),n(7,4,7,5),n(7,5,7,6),n(7,6,7,7),n(7,7,6,7)] ]).
paths(9,  [ [n(1,1,1,2),n(1,2,1,3),n(1,3,2,3),n(1,4,1,5),n(1,5,1,6),n(1,6,1,7),
             n(1,7,1,8),n(1,8,2,8),n(2,1,3,1),n(2,2,3,2),n(2,3,3,3),n(2,4,2,5),
             n(2,5,2,6),n(2,6,3,6),n(2,7,3,7),n(2,8,3,8),n(3,1,4,1),n(3,2,4,2),
             n(3,3,3,4),n(3,4,3,5),n(3,5,4,5),n(3,6,4,6),n(3,7,4,7),n(3,8,4,8),
             n(4,1,5,1),n(4,2,4,3),n(4,3,4,4),n(4,4,5,4),n(4,5,5,5),n(4,6,5,6),
             n(4,7,5,7),n(4,8,5,8),n(5,1,5,2),n(5,2,5,3),n(5,3,6,3),n(5,4,6,4),
             n(5,7,6,7),n(5,8,6,8),n(6,1,7,1),n(6,3,7,3),n(6,6,6,5),n(6,7,6,6),
             n(6,8,7,8),n(7,1,8,1),n(7,2,6,2),n(7,3,7,4),n(7,4,7,5),n(7,5,7,6),
             n(7,6,7,7),n(7,8,8,8),n(8,2,7,2),n(8,3,8,2),n(8,4,8,3),n(8,5,8,4),
             n(8,6,8,5),n(8,7,8,6),n(8,8,8,7)] ]).
paths(10, [ [n(1,1,2,1),n(1,2,1,1),n(1,3,1,2),n(1,4,1,3),n(1,5,1,4),n(1,6,1,7),
             n(1,7,1,8),n(1,8,2,8),n(2,1,3,1),n(2,2,3,2),n(2,3,2,2),n(2,4,2,3),
             n(2,5,1,5),n(2,6,1,6),n(2,7,3,7),n(2,8,3,8),n(3,1,4,1),n(3,2,4,2),
             n(3,3,3,4),n(3,4,3,5),n(3,5,4,5),n(3,6,2,6),n(3,7,4,7),n(3,8,4,8),
             n(4,1,5,1),n(4,2,4,3),n(4,3,4,4),n(4,4,5,4),n(4,5,5,5),n(4,6,3,6),
             n(4,7,5,7),n(4,8,5,8),n(5,1,5,2),n(5,2,5,3),n(5,4,6,4),n(5,5,5,6),
             n(5,7,6,7),n(5,8,6,8),n(6,1,7,1),n(6,2,6,1),n(6,3,6,2),n(6,4,7,4),
             n(6,5,6,6),n(6,7,7,7),n(6,8,7,8),n(7,1,8,1),n(7,3,7,2),n(7,4,7,3),
             n(7,5,6,5),n(7,8,8,8),n(8,1,8,2),n(8,2,8,3),n(8,3,8,4),n(8,4,8,5),
             n(8,5,7,5),n(8,6,7,6),n(8,7,8,6),n(8,8,8,7)] ]).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Visualisierung                                                       %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

show(p(X,Y,Lines), Paths) :-
  (( X > 0, Y > 0 ) ->
    (
      nl,
      line(1, Y),
      lines(1, 1, 1, X, Y, Lines, Paths),
      dimY(1, Y)
    )
  ;
    true
  ).

dimY(Y, DY) :-
  Y > DY ->
    nl
  ;
    (
      write(' '),
      Y2 is Y // 10,
      Y3 is Y // 100,
      (Y2 = 0 -> write(' ') ; true),
      write(Y),
      (Y3 = 0 -> write(' ') ; true),
      Y1 is Y+1, dimY(Y1, DY)
    ).

line(Y, DY) :-
  Y > DY ->
    nl
  ;
    (
      write(' '), write('-'), write('-'), write('-'),
      Y1 is Y+1, line(Y1, DY)
    ).

lines(Mode, X, Y, DX, DY, Puzzle, Path) :-
  Y > DY ->
    (
      write('|'),
      (Mode = 2 ->  ( write(' '), write(X) ) ; true),
      nl,
      (Mode = 3 ->
        (
          line(1, DY),
          X1 is X+1,
          (X1 > DX ->
            true
          ;
            lines(1, X1, 1, DX, DY, Puzzle, Path)
          )
        )
      ;
        (
          Mode1 is Mode+1,
          lines(Mode1, X, 1, DX, DY, Puzzle, Path)
        )
      )
    )
  ;
    (Mode = 1 ->
      (
        write('|'), write(' '),
        X1 is X-1,
        (remove(n(X,Y,X1,Y), Path, RestPath) ->
          write('^')
        ;
          ( write(' '), RestPath = Path )
        ),
        write(' '),
        Y1 is Y+1,
        lines(Mode, X, Y1, DX, DY, Puzzle, RestPath)
      )
    ;
      (Mode = 2 ->
        (
          write('|'),
          Y0 is Y-1,
          (remove(n(X,Y,X,Y0), Path, TempPath) ->
            write('<')
          ;
            ( write(' '), TempPath = Path )
          ),
          (remove(l(I,X,Y,FX,FY), Puzzle, TmpPuzzle) ->
            (
              write(I),
              ( ((FX*DY)+FY =< (X*DY)+Y) -> RestPuzzle = TmpPuzzle ; RestPuzzle = Puzzle )
            )
          ;
            (remove(l(I,FX,FY,X,Y), Puzzle, TmpPuzzle) ->
              (
                write(I),
                ( ((FX*DY)+FY =< (X*DY)+Y) -> RestPuzzle = TmpPuzzle ; RestPuzzle = Puzzle )
              )
	    ;
              ( write(' '), RestPuzzle = Puzzle )
            )
          ),
          Y1 is Y+1,
          (remove(n(X,Y,X,Y1), TempPath, RestPath) ->
            write('>')
          ;
            ( write(' '), RestPath = TempPath )
          ),
          lines(Mode, X, Y1, DX, DY, RestPuzzle, RestPath)
        )
      ;
        (
          write('|'), write(' '),
          X1 is X+1,
          (remove(n(X,Y,X1,Y), Path, RestPath) ->
            write('v')
          ;
            ( write(' '), RestPath = Path )
          ),
          write(' '),
          Y1 is Y+1,
          lines(Mode, X, Y1, DX, DY, Puzzle, RestPath)
        )
      )
    ).

remove(X, [X | L], L) :- !.
remove(X, [Y | L], [Y | R]) :- remove(X, L, R).

