/* Tracassin */
tr(P) :-
	etat_i(E1),
	etat_f(E2),
	transfo(E1,E2,[E1],P).

transfo(Ef,Ef,_,[]).  
transfo(Ec,Ef,LE,[Op|A]):-
	ope(Ec,Es,Op),
	hors(Es,LE),
	transfo(Es,Ef,[Ec|LE],A).  

ope(E1,E2,r1) :- once(subst([x,b],[b,x],E1,E2)).
ope(E1,E2,r2) :- once(subst([b,o],[o,b],E1,E2)).
ope(E1,E2,r3) :- once(subst([x,o,b],[b,o,x],E1,E2)).
ope(E1,E2,r4) :- once(subst([b,x,o],[o,x,b],E1,E2)).

subst(C1,C2,L1,L2) :-
	conc(L0,R,L1),
	conc(X,C1,L0),
	conc(X,C2,Li),
	conc(Li,R,L2).

/* Utilitaires */

conc([],X,X).
conc([X|R],Y,[X|Z]):-conc(R,Y,Z).

once(P):- P,!.

hors(X,[]).
hors(X,[Y|Z]):- 
	X \== Y, 
	hors(X,Z).

/* Jeu d'essai */

etat_i([x,x,x,x,b,o,o,o,o]).
etat_f([o,o,o,o,b,x,x,x,x]).