casse-tete-prolog : calculer les methodes de poser des cercles avec les trous sur un disque

casse-tête.pl

/* disque(Nom, Motif) - Modélisation des disques */
disque(a, [-1,  0,  0,  0,  0,  0]).
disque(b, [-1, -1,  0,  0,  0,  0]).
disque(c, [-1,  0, -1,  0,  0,  0]).
disque(d, [-1,  0,  0, -1,  0,  0]).
disque(e, [-1, -1, -1,  0,  0,  0]).
disque(f, [-1, -1, 0,  -1,  0,  0]).
disque(g, [-1,  0, -1,  0, -1,  0]).
disque(h, [-1, -1, -1, -1,  0,  0]).
disque(i, [-1, -1, -1,  0, -1,  0]).
disque(j, [-1, -1,  0, -1, -1,  0]).
disque(k, [-1, -1, -1, -1, -1,  0]).
disque(l, [-1, -1, -1, -1, -1,  -1]).
/* liste_des_disques(L) - Renvoyer la liste des disques L */

liste_des_disques(L) :- findall(X, disque(X, _M), L).


/* orienter(M1, M2, N) - Donner le disque M2 rotation de M1 de N fois  
 * N : rotation de 60deg dans le sens de l'horloge
 */

% decalage_gauche([X|R], M1) :- append(R, [X], M1).
decalage_droite(L, [F|R]) :- append(R, [F], L). 

orienter_memo(M, M, 0, _Nmax, _Memo).
orienter_memo(M1, M2, N, Nmax,Memo) :-
    Nmax > 0,
 	decalage_droite(M1, X),
 	X \= Memo,
 	Nmax1 is Nmax-1,
 	orienter_memo(X, M2, N2, Nmax1, Memo),
 	N is N2+1.

orienter(M1, M2, N) :- 
 	orienter_memo(M1, M2, N, 5, M1).




empilement_secteur(0, 0, 0).
empilement_secteur(2, -1, 1).
empilement_secteur(0, -1, 2).
empilement_secteur(1, -1, 0).

% empilement(S_avant, Motif, S_après)
empilement([], [], []). 
empilement([X|PreS], [Y|Motif], [Z|PostS]) :- 
    empilement_secteur(X, Y, Z),
    empilement(PreS, Motif, PostS).

enlever(X,[X|R],R). 
enlever(X,[P|R],[P|Q]):- enlever(X,R,Q).


disquePlate([0,0,0,0,0,0]).

chemin(Final, Final, [], []):- disque_Plat(Final).
/*chemin(Init, Final,  [[Mid, 0]|Chemin], Disques) :-
	disquePlate(Init),
	member(Mid, Disques),
	disque(Mid, MidMotif),
	empilement(Init, MidMotif, Res),
	enlever(Mid, Disques, Disques2),
	chemin(Res, Final, Chemin, Disques2).


chemin(Init, Final, [[Mid, Y]|Chemin], Disques) :-
	not(disquePlate(Init)),
	member(Mid, Disques),
	disque(Mid, MidMotif),
	orienter(MidMotif, MidMotifTourne, Y),
	empilement(Init, MidMotifTourne, Res),
	enlever(Mid, Disques, Disques2),
	chemin(Res, Final, Chemin, Disques2).*/

chemin(Init, Final, [[Mid, Y]|Chemin], Disques) :-
	member(Mid, Disques),
	disque(Mid, MidMotif),
	orienter(MidMotif, MidMotifTourne, Y),
	empilement(Init, MidMotifTourne, Res),
	enlever(Mid, Disques, Disques2),
	chemin(Res, Final, Chemin, Disques2).

solution(S) :-
    liste_des_disques(Disques),
	chemin([0,0,0,0,0,0], [0,0,0,0,0,0], S, Disques).


nb_sol(N):- 
	findall(1,solution(_S),L),
	length(L,N).

	%9030 optimisé
	% 75132 non-optimisé