%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % 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).