#|			BOURDON Morgane et TSARAFIDY Alain
			Binome n°2
			le 30 octobre 2000
			TP n°5 lisp
|#


(setf carte_1 '((pied jaune)(pied vert)(tete rose)(tete violet)))
(setf carte_2 '((pied rose)(pied violet)(tete jaune)(tete violet)))
(setf carte_3 '((pied jaune)(pied violet)(tete rose)(tete vert)))
(setf carte_4 '((pied jaune)(pied vert)(tete rose)(tete vert)))
(setf carte_5 '((pied violet)(pied rose)(tete vert)(tete violet)))
(setf carte_6 '((pied jaune)(pied rose)(tete jaune)(tete vert)))
(setf carte_7 '((pied rose)(pied vert)(tete jaune)(tete violet)))
(setf carte_8 '((pied violet)(pied rose)(tete violet)(tete vert)))
(setf carte_9 '((pied rose)(pied jaune)(tete violet)(tete vert)))
(setf cartes (list 'carte_1 'carte_2 'carte_3 'carte_4 'carte_5 'carte_6 'carte_7 'carte_8 'carte_9))
(setf sol_cour (list (list 'carte_1 0)))
(setf (symbol-plist 'cartes_associees) NIL)



;la fonction correspond-1() verifie la correspondance entre les cotes 0 et 2
;de deux cartes etant donnees leurs orientations respectives.


(defun correspond-1 (carte1 ori1 carte2 ori2)

	(let ((droit (nth (mod ori1 4) carte1))
	      (gauche (nth (mod (+ ori2 2) 4) carte2)))
	      
	      (and (equal (cadr droit) (cadr gauche))  ;on teste l'egalite des couleurs
		   (not (equal (car droit) (car gauche)))   ;on teste la difference pied-tete 
	       )
	)
)


;la fonction correspond-2() verifie la correspondance entre les cotes 3 et 1
;de deux cartes etant donnees leurs orientations respectives.
 

(defun correspond-2 (carte1 ori1 carte2 ori2)
	(let ((bas (nth (mod (+ ori1 3) 4) carte1))
	      (haut (nth (mod (+ ori2 1) 4) carte2)))
	      
	      (and (equal (cadr bas) (cadr haut)) 
	     	       (not (equal (car bas) (car haut)))
	       )
	)
)



;La fonction verifie() verifie par l'appel des 2 fonctions precedentes qu'on peut inserer une carte dans
;la solution courante.
 

(defun verifie (sol_courante carte ori position)
	(if (or (= (mod position 3) 2) (= (mod position 3) 0)) ; on teste si l'on est sur les colonnes 2 ou 3.
	    (if (> position 3)                                 ; on teste si l'on est sur les lignes 2 ou 3
		(and (correspond-1 (eval (car (nth (- position 2) sol_courante))) (cadr (nth (- position 2) sol_courante)) carte ori)
		     (correspond-2 (eval (car (nth (- position 4) sol_courante))) (cadr (nth (- position 4) sol_courante)) carte ori))
		;ici, on est sur la premiere ligne:
	        (correspond-1 (eval (car (nth (- position 2) sol_courante)))(cadr (nth (- position 2) sol_courante)) carte ori)
		)
	    ;ici, on est sur la premiere colonne:
	    ( correspond-2 (eval (car (nth (- position 4) sol_courante)))(cadr (nth (- position 4) sol_courante)) carte ori)
	)
) 




;la fonction recherche() a partir d'une carte fixee dans solution courante va chercher toutes les solutions possibles
;avec le reste des cartes, elle teste chacune des cartes restantes dans toutes ses orientations jusqu'a insertion eventuelle


(defun recherche (sol_courante carte_res position)
  (cond ((> position 9) (print sol_courante))
	(t (loop for carte in carte_res do
	     (loop for ori from 0 to 3 do
	       (if (verifie sol_courante (eval carte) ori position)       ;on teste l'insertion possible de la carte
		   (recherche (append sol_courante (list (list carte ori))) (remove carte carte_res) (1+ position))
		 )       ;ici,il y a eu insertion, on enleve la carte inseree des cartes restantes et on incremente
                         ; la position de 1 et on relance la recherche avec la nouvelle solution
	       )
	     )
	   )
	)
)



;la fonction prog_rech() initialise la premiere carte et lance la fonction recherche()


(defun prog_rech (cartes_tot)
  (loop for carte in cartes_tot do
    (loop for ori from 0 to 3 do
      (recherche (list (list carte ori)) (remove carte cartes_tot) 2)
      )
    )
)

;(prog_rech cartes)

; On trouvera ici la deuxieme methode de recherche;
;Les cartes seront orientees comme suit:
;  7 3 6
;  4 1 2
;  8 5 9

(defun genere_simple (carte_choisie cartes_res ori)
  (setf (symbol-plist 'liste_temp) NIL)
  (setf (symbol-plist 'liste_temp2) NIL)
    (loop for cote from 0 to 3 do
      (setf liste_generee NIL)
      (loop for carte in cartes_res do
	(loop for ori2 from 0 to 3 do
	  (cond ((equal ori 0) (cond ((equal cote 0) (if (correspond-1 (eval carte_choisie) 0 (eval carte) ori2)
							 (push (list carte ori2) liste_generee)
						       )
				      )
				     ((equal cote 1) (if (correspond-2 (eval carte) ori2 (eval carte_choisie) 0)
							 (push (list carte ori2) liste_generee)
						       )
				      )
				     ((equal cote 2) (if (correspond-1 (eval carte) ori2 (eval carte_choisie) 0)
							 (push (list carte ori2) liste_generee)
						       )
				      )
				     (t (if (correspond-2 (eval carte_choisie) 0 (eval carte) ori2)
					    (push (list carte ori2) liste_generee)
					  )
				      )
				     )
		 )
		((equal ori 1) (cond ((equal cote 0) (if (correspond-2 (eval carte_choisie) 1 (eval carte) ori2)
							 (push (list carte ori2) liste_generee)
						       )
				      )
				     ((equal cote 1) (if (correspond-1 (eval carte_choisie) 1 (eval carte) ori2)
							 (push (list carte ori2) liste_generee)
						       )
				      )
				     ((equal cote 2) (if (correspond-2 (eval carte) ori2 (eval carte_choisie) 1)
							 (push (list carte ori2) liste_generee)
						       )
				      )
				     (t (if (correspond-1 (eval carte) ori2 (eval carte_choisie) 1)
					    (push (list carte ori2) liste_generee)
					  )
				      )
				     )
		 )
		((equal ori 2) (cond ((equal cote 0) (if (correspond-1 (eval carte) ori2 (eval carte_choisie) 2)
							 (push (list carte ori2) liste_generee)
						       )
				      )
				     ((equal cote 1) (if (correspond-2 (eval carte_choisie) 2 (eval carte) ori2)
							 (push (list carte ori2) liste_generee)
						       )
				      )
				     ((equal cote 2) (if (correspond-1 (eval carte_choisie) 2 (eval carte) ori2)
							 (push (list carte ori2) liste_generee)
						       )
				      )
				     (t (if (correspond-2 (eval carte) ori2 (eval carte_choisie) 2)
					    (push (list carte ori2) liste_generee)
					  )
				      )
				     )
		 )
		(t (cond ((equal cote 0) (if (correspond-2 (eval carte) ori2 (eval carte_choisie) 3)
							 (push (list carte ori2) liste_generee)
						       )
				      )
				     ((equal cote 1) (if (correspond-1 (eval carte) ori2 (eval carte_choisie) 3)
							 (push (list carte ori2) liste_generee)
						       )
				      )
				     ((equal cote 2) (if (correspond-2 (eval carte_choisie) 3 (eval carte) ori2)
							 (push (list carte ori2) liste_generee)
						       )
				      )
				     (t (if (correspond-1 (eval carte_choisie) 3 (eval carte) ori2)
					    (push (list carte ori2) liste_generee)
					  )
				      )
				     )
		 )
		)
	  )
	)
      (setf (get 'liste_temp cote) liste_generee)
      ) 
    (setf (symbol-plist 'liste_temp2)  (symbol-plist 'liste_temp))
    (symbol-plist 'liste_temp2) 
)

(defun genere (liste_carte)
  (setf (symbol-plist 'liste_temp) NIL)
  (setf (symbol-plist 'liste_temp2) NIL)
  (loop for carte_choisie in liste_carte do
    (setf liste_generee NIL)
    (loop for ori from 0 to 3 do
      (push (genere_simple carte_choisie liste_carte ori) liste_generee)
      (setf (get 'liste_temp ori) liste_generee)
      )
;    (print (symbol-plist 'liste_temp))
    (setf (get 'liste_temp2 carte_choisie)  (symbol-plist 'liste_temp))
;    (print (symbol-plist 'liste_temp2))
    )
;    (setf (symbol-plist 'liste_temp2)  (symbol-plist 'liste_temp))
    (symbol-plist 'liste_temp2)
) 



(defun verifie2 (carte1 carte2 carte ori position)
  (cond ((equal position 6)(and (correspond-1 (car carte2) (cadr carte2) carte ori) (correspond-2 carte ori (car carte1) (cadr carte1))))
	((equal position 7)(and (correspond-1 carte ori (car carte1) (cadr carte1)) (correspond-2 carte ori (car carte2) (cadr carte2))))
	((equal position 8)(and (correspond-1 carte ori (car carte2) (cadr carte2)) (correspond-2 (car carte1) (cadr carte1) carte ori)))
	((equal position 9)(and (correspond-1 (car carte1) (cadr carte1) carte ori) (correspond-2 (car carte2) (cadr carte2) carte ori)))
	(t ())
	)
)


(defun recherche2 (sol_courante carte1_assoc carte2_assoc position  cartes_restantes)
  (cond ((> position 9) (print sol_courante))
	((< position 6)(print sol_courante) (loop for carte in (getf  carte1_assoc  (- position 2)) do
			   (recherche2 (append sol_courante (list carte)) (genere_simple (caar sol_courante) (remove (caar sol_courante) cartes_restantes) (cadar sol_courante)) carte2_assoc (+ 1 position) (remove (car carte) cartes_restantes)
				       )
			   )
	 )
	((equal position 6) (let ((carte1 (nth (- position 5) sol_courante))
				  (carte2 (nth (- position 4) sol_courante))
				  (carte1_assoc (getf (genere_simple (car carte1) cartes_restantes  (cadr carte1)) (mod (+ 1 (cadr carte1)) 4)))
				  (carte2_assoc (getf (genere_simple (car carte2) cartes_restantes  (cadr carte2)) (cadr carte2))))
			      (print carte1)
			      (loop for carte in carte1_assoc do
				(setf peut_inserer (member carte carte2_assoc))
				(if peut_inserer (recherche2 (append sol_courante (list peut_inserer)) (getf (genere_simple (car carte2) (remove (car peut_inserer) cartes_restantes) (cadr carte2)) (mod (+ 2 (cadr carte2)) 4))  (getf (genere_simple (car (nth (- position 3))) (remove (car peut_inserer) cartes_restantes) (cadr (nth (- position 3)))) (mod (+  (cadr (nth (- position 3))) 1) 4)) (+ 1 position ) (remove (car peut_inserer) cartes_restantes))
				  )
				)
			      )
	 )
	 
	(t (print sol_courante)
#|
(let ((carte1 (nth (- position 5) sol_courante))
		 (carte2 (nth (- position 4) sol_courante))
		 (carte3 (nth 1 sol_courante)))
	     (print carte1)
	     (print carte2)
	     (print carte3)
	     (print position)
;	     (print cartes_assoc)
	     (loop for carte in cartes_restantes do
;	       (setf (symbol-plist 'carte_a_verifier_assoc) (genere_simple carte  (list (car carte1) (car carte2))))
	       (cond ((equal position 9) (cond ((< (cadr carte1) 2)
						(if (verifie2 carte1 carte3 carte 0 position)
						    (recherche2 (append sol_courante (list (list carte 0))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes)))
						(if (verifie2 carte1 carte3 carte 1 position) 
						    (recherche2 (append sol_courante (list (list carte 1))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes))))
					       (t (if (verifie2 carte1 carte3 carte 2 position)
						      (recherche2 (append sol_courante (list (list carte 2))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes)))
						  (if (verifie2 carte1 carte3 carte 3 position) 
						      (recherche2 (append sol_courante (list (list carte 3))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes)))
						  )
					       ))
		     ((or (equal position 6) (equal position 8)) (cond ((>= (mod (cadr carte1) 3) 1)
									(if (verifie2 carte1 carte2 carte 1 position)
									    (recherche2 (append sol_courante (list (list carte 1))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes)))
									(if (verifie2 carte1 carte2 carte 2 position) 
									    (recherche2 (append sol_courante (list (list carte 2))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes))))
								       (t (if (verifie2 carte1 carte2 carte 0 position)
									      (recherche2 (append sol_courante (list (list carte 0))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes)))
									  (if (verifie2 carte1 carte2 carte 3 position) 
									      (recherche2 (append sol_courante (list (list carte 3))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes))))))
		     (t (cond ((< (cadr carte1) 2)
			       (if (verifie2 carte1 carte2 carte 0 position)
				   (recherche2 (append sol_courante (list (list carte 0))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes)))
			       (if (verifie2 carte1 carte2 carte 1 position) 
				   (recherche2 (append sol_courante (list (list carte 1))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes))))
			      (t (if (verifie2 carte1 carte2 carte 2 position)
				     (recherche2 (append sol_courante (list (list carte 2))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes)))
				 (if (verifie2 carte1 carte2 carte 3 position) 
				     (recherche2 (append sol_courante (list (list carte 3))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes)))
				 )
			      )
			)
		     )
	       )
	     )
|#
	   )
	)
  )
  
#|  
(defun recherche2 (sol_courante cartes_assoc toutes_cartes_assoc position  cartes_restantes)
  (cond ((> position 9) (print sol_courante))
	((< position 6) (loop for carte in (getf  cartes_assoc  (- position 2)) do
			   (recherche2 (append sol_courante (list carte)) (genere_simple (caar sol_courante) (remove (caar sol_courante) cartes_restantes) (cadar sol_courante)) toutes_cartes_assoc (+ 1 position) (remove (car carte) cartes_restantes)
				       )
			   )
	 )
	 
	(t (let ((carte1 (nth (- position 5) sol_courante))
		 (carte2 (nth (- position 4) sol_courante))
		 (carte3 (nth 1 sol_courante)))
	     (print carte1)
	     (print carte2)
	     (print carte3)
	     (print position)
;	     (print cartes_assoc)
	     (loop for carte in cartes_restantes do
;	       (setf (symbol-plist 'carte_a_verifier_assoc) (genere_simple carte  (list (car carte1) (car carte2))))
	       (cond ((equal position 9) (cond ((< (cadr carte1) 2)
						(if (verifie2 carte1 carte3 carte 0 position)
						    (recherche2 (append sol_courante (list (list carte 0))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes)))
						(if (verifie2 carte1 carte3 carte 1 position) 
						    (recherche2 (append sol_courante (list (list carte 1))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes))))
					       (t (if (verifie2 carte1 carte3 carte 2 position)
						      (recherche2 (append sol_courante (list (list carte 2))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes)))
						  (if (verifie2 carte1 carte3 carte 3 position) 
						      (recherche2 (append sol_courante (list (list carte 3))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes)))
						  )
					       ))
		     ((or (equal position 6) (equal position 8)) (cond ((>= (mod (cadr carte1) 3) 1)
									(if (verifie2 carte1 carte2 carte 1 position)
									    (recherche2 (append sol_courante (list (list carte 1))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes)))
									(if (verifie2 carte1 carte2 carte 2 position) 
									    (recherche2 (append sol_courante (list (list carte 2))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes))))
								       (t (if (verifie2 carte1 carte2 carte 0 position)
									      (recherche2 (append sol_courante (list (list carte 0))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes)))
									  (if (verifie2 carte1 carte2 carte 3 position) 
									      (recherche2 (append sol_courante (list (list carte 3))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes))))))
		     (t (cond ((< (cadr carte1) 2)
			       (if (verifie2 carte1 carte2 carte 0 position)
				   (recherche2 (append sol_courante (list (list carte 0))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes)))
			       (if (verifie2 carte1 carte2 carte 1 position) 
				   (recherche2 (append sol_courante (list (list carte 1))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes))))
			      (t (if (verifie2 carte1 carte2 carte 2 position)
				     (recherche2 (append sol_courante (list (list carte 2))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes)))
				 (if (verifie2 carte1 carte2 carte 3 position) 
				     (recherche2 (append sol_courante (list (list carte 3))) cartes_assoc toutes_cartes_assoc (+ 1 position) (remove carte cartes_restantes)))
				 )
			      )
			)
		     )
	       )
	     )
	   )
	)
  )
  
|#
(defun prog_rech2 (cartes_tot)
  (loop for carte in cartes_tot do
    (print (recherche2 (list (list carte 0)) (genere_simple carte (remove carte cartes_tot) 0) NIL 2 (remove carte cartes_tot)))
    )
)

(prog_rech2 cartes)
#|
(print (genere_simple 'carte_1 (remove 'carte_1 cartes) 1))
(print (genere_simple 'carte_1 (remove 'carte_1 cartes) 2))
(print (genere_simple 'carte_1 (remove 'carte_1 cartes) 3))
|#
(print (genere_simple 'carte_1 (remove 'carte_1 cartes) 0))

;(print (genere (list 'carte_1 'carte_2 'carte_3)))