/*****************************************************************************/
/*         Zweite Prolog Uebung in KI von Dannecker Andreas                  */
/*   starten mit:                                                            */
/*		start(N,Z,StarZ).					     */
/* N für Grösse des Feldes,  Z für Ausgabeformatierung Spalten pro Zeile     */
/*      StartZ für den Startzustand in Form von "[Zeile,Spalte]"             */
/*****************************************************************************/
start(N,Spalten,StartZ):-	
		((N>0,[R,S]=StartZ,R=<N,R>0,S=<N,S>0),
		 ((	save_move(N,StartZ,[StartZ],RL),
			L is N * N,
			listlen(RL,LL),
			L = LL,
			rev(RL,InverseL),
			zael(1,InverseL,Spalten,0)
		  );write('Keine Loesung mit diesem Programm moeglich'))
		);write('Unerlaubte Startposition oder Brettgroesse').

zael(N,[H|[]],_,_):- 	write(N),write(' '),write(H).
zael(N,[H|T],N2,N3):-  	write(N),write(' '),write(H),write('    '),
			NPL is N + 1,NW is N3 + 1,
			((NW=N2,nl,zael(NPL,T,N2,0));
			 (zael(NPL,T,N2,NW))).

rev(L,RL):- revzap(L,[],RL).
revzap([],List,List).
revzap([H|T],L2,L3):- revzap(T,[H|L2],L3).

listlen(L,N)	:-	lenacc(L,0,N).
lenacc([],N,N).
lenacc([_|T],X,N):-	X1 is X+1,
			lenacc(T,X1,N).

save_move(N,Start,Ergliste,RergListe):-
		(	all_possible_moves(N,Start,Ergliste,RListe),
			best_move(N,RListe,Ergliste,BMove),
			BMove\=[],
			save_move(N,BMove,[BMove|Ergliste],RergListe)
		);RergListe=Ergliste.

best_move(_,[],_,BZug)		:- 	BZug=[].
best_move(_,[X|[]],_,BZug)	:- 	BZug=X,!.
best_move(N,[Zug1|T],ErgListe,BZug):- 	best_move(N,T,ErgListe,Zug2),
				all_possible_moves(N,Zug1,ErgListe,Liste1),
				all_possible_moves(N,Zug2,ErgListe,Liste2),
				listlen(Liste1,N1),
				listlen(Liste2,N2),
				((N1=<N2,BZug=Zug1);(N1>=N2,BZug=Zug2)).

all_possible_moves(N,Feld,ErgL,RL):-
		(bagof(X,poss_move(N,Feld,ErgL,X),RL);RL=[]),!.

poss_move(N,Feld,ErgL,RL):-
	regel_move(Feld,Zug),
	(Zug\=[],[R,S]=Zug),
	R=<N,R>0,S=<N,S>0,
  	not(member([R,S],ErgL)),
	RL=Zug.

regel_move(VFeld,AFeld):-
	(VFeld\=[],[R,S]=VFeld),
	((R1 is R - 2, S1 is S + 1,AFeld=[R1,S1]);
	 (R2 is R - 1, S2 is S + 2,AFeld=[R2,S2]);
	 (R3 is R + 1, S3 is S + 2,AFeld=[R3,S3]);
	 (R4 is R + 2, S4 is S + 1,AFeld=[R4,S4]);
	 (R5 is R + 2, S5 is S - 1,AFeld=[R5,S5]);
	 (R6 is R + 1, S6 is S - 2,AFeld=[R6,S6]);
	 (R7 is R - 1, S7 is S - 2,AFeld=[R7,S7]);
	 (R8 is R - 2, S8 is S - 1,AFeld=[R8,S8])).