/* Ecrit par Nicolas Zinovieff (p6mip138) */

/* representation du taquin
etatcoutant(a,b,c,d,e,f,g,h,i) represente
_______
|a|b|c|
|d|e|f|
|g|h|i|
-------    */

/* Pour les permutations, on utilise
__________
|A1|A2|A3|
|B1|B2|B3|
|C1|C2|C3|
----------   */

/* permutations ligne a ligne */
etatsuivant(etatcourant(0,A2,A3,X,B2,B3,C1,C2,C3),
			etatcourant(X,A2,A3,0,B2,B3,C1,C2,C3)).
etatsuivant(etatcourant(X,A2,A3,0,B2,B3,C1,C2,C3),
			etatcourant(0,A2,A3,X,B2,B3,C1,C2,C3)).

etatsuivant(etatcourant(A1,A2,A3,X,B2,B3,0,C2,C3),
			etatcourant(A1,A2,A3,0,B2,B3,X,C2,C3)).
etatsuivant(etatcourant(A1,A2,A3,0,B2,B3,X,C2,C3),
			etatcourant(A1,A2,A3,X,B2,B3,0,C2,C3)).

etatsuivant(etatcourant(A1,0,A3,B1,X,B3,C1,C2,C3),
			etatcourant(A1,X,A3,B1,0,B3,C1,C2,C3)).
etatsuivant(etatcourant(A1,X,A3,B1,0,B3,C1,C2,C3),
			etatcourant(A1,0,A3,B1,X,B3,C1,C2,C3)).

etatsuivant(etatcourant(A1,A2,A3,B1,0,B3,C1,X,C3),
			etatcourant(A1,A2,A3,B1,X,B3,C1,0,C3)).
etatsuivant(etatcourant(A1,A2,A3,B1,X,B3,C1,0,C3),
			etatcourant(A1,A2,A3,B1,0,B3,C1,X,C3)).

etatsuivant(etatcourant(A1,A2,0,B1,B2,X,C1,C2,C3),
			etatcourant(A1,A2,X,B1,B2,0,C1,C2,C3)).
etatsuivant(etatcourant(A1,A2,X,B1,B2,0,C1,C2,C3),
			etatcourant(A1,A2,0,B1,B2,X,C1,C2,C3)).

etatsuivant(etatcourant(A1,A2,A3,B1,B2,0,C1,C2,X),
			etatcourant(A1,A2,A3,B1,B2,X,C1,C2,0)).
etatsuivant(etatcourant(A1,A2,A3,B1,B2,X,C1,C2,0),
			etatcourant(A1,A2,A3,B1,B2,0,C1,C2,X)).

/* permutations colonnes a colonnes */
etatsuivant(etatcourant(X,0,A3,B1,B2,B3,C1,C2,C3),
			etatcourant(0,X,A3,B1,B2,B3,C1,C2,C3)).
etatsuivant(etatcourant(0,X,A3,B1,B2,B3,C1,C2,C3),
			etatcourant(X,0,A3,B1,B2,B3,C1,C2,C3)).

etatsuivant(etatcourant(A1,X,0,B1,B2,B3,C1,C2,C3),
			etatcourant(A1,0,X,B1,B2,B3,C1,C2,C3)).
etatsuivant(etatcourant(A1,0,X,B1,B2,B3,C1,C2,C3),
			etatcourant(A1,X,0,B1,B2,B3,C1,C2,C3)).

etatsuivant(etatcourant(A1,A2,A3,X,0,B3,C1,C2,C3),
			etatcourant(A1,A2,A3,0,X,B3,C1,C2,C3)).
etatsuivant(etatcourant(A1,A2,A3,0,X,B3,C1,C2,C3),
			etatcourant(A1,A2,A3,X,0,B3,C1,C2,C3)).

etatsuivant(etatcourant(A1,A2,A3,B1,X,0,C1,C2,C3),
			etatcourant(A1,A2,A3,B1,0,X,C1,C2,C3)).
etatsuivant(etatcourant(A1,A2,A3,B1,0,X,C1,C2,C3),
			etatcourant(A1,A2,A3,B1,X,0,C1,C2,C3)).

etatsuivant(etatcourant(A1,A2,A3,B1,B2,B3,X,0,C3),
			etatcourant(A1,A2,A3,B1,B2,B3,0,X,C3)).
etatsuivant(etatcourant(A1,A2,A3,B1,B2,B3,0,X,C3),
			etatcourant(A1,A2,A3,B1,B2,B3,X,0,C3)).

etatsuivant(etatcourant(A1,A2,A3,B1,B2,B3,C1,X,0),
			etatcourant(A1,A2,A3,B1,B2,B3,C1,0,X)).
etatsuivant(etatcourant(A1,A2,A3,B1,B2,B3,C1,0,X),
			etatcourant(A1,A2,A3,B1,B2,B3,C1,X,0)).

/* recherche avec accumulateur */
possible_taquin(X, X, CList, CList).
possible_taquin(X, Y, CList, List) :-
	etatsuivant(X, Z),
	not(member(Z, CList)),
	possible_taquin(Z, Y, [Z | CList], List).

chemin_taquin(X, Y, FoundPath) :- possible_taquin(X, Y, [X], FoundPath).

/* recherche en largeur */
recherche_largeur(X,Y,C) :- cherche(Y,[[X]],C).

cherche(Y,[[Y|Chs]|_],[Y|Chs]) :- !. /* la solution est la bonne mais inversee */
cherche(Y,[[S|Chs]|AutresChemins],Sol) :- findall([Suc,S|Chs],etatsuivant(S,Suc),NewChemins),
											append(AutresChemins,NewChemins,Chemins),
											cherche(Y,Chemins,Sol).

but_taquin_prof(X) :- chemin_taquin(X, etatcourant(1,2,3,8,0,4,7,6,5), Liste),reverse(Liste,R),write(R).
but_taquin_larg(X) :- recherche_largeur(X, etatcourant(1,2,3,8,0,4,7,6,5), Liste),reverse(Liste,R),write(R).
but_test_taquin :- chemin_taquin(etatcourant(0,1,2,3,4,5,6,7,8), etatcourant(1,2,3,8,0,4,7,6,5), Liste),reverse(Liste,R),write(R).
but_test_taquin2 :- recherche_largeur(etatcourant(0,1,2,3,4,5,6,7,8), etatcourant(1,2,3,8,0,4,7,6,5), Liste),reverse(Liste,R),write(R).
