#### faire une fonction qui à partir de polyo1 et de deux points M_1 dans polyo1 et M_2, renvoie : ## le translaté de polyo1 envoyant M_1 en M_2 ## la rotation de polyo1 d'angle Pi/2, Pi et -Pi/2 envoyant M_1 en M_2 ## faire une fonction Frontière qui calcule la frontière de polyo1 : ensemble des points de distance égale à 1 de polyo1 : il suffit d'appliquer les 4 fonctions non pas à polyo1 mais à la frontière #### faire une fonction successeur qui # part de figure =points de polyo1 # points_frontière=frontière de polyo1 # pour tous les points M_2 de points_frontiere, on teste les quatre fonctions pour M_1 variant de polyo1, on regarde le polyo déplacé et on regarde le nombre maximal de points_frontière couverts parmi les polyo sans débordement : # on pose le polyo déplacé # figure augmente de polyo # points_frontière devient on augmente points_frontiere de la frontière de polyo et on enlève les points de figure # on recommence jusqu'à une mise_A_Jour fausse def Distance_Points(M,N) : """ calcule la distance L^1 entre les points M et N """ return abs(M[0]-N[0])+abs(M[1]-N[1]) ### Fonctions de rotation ### def Rot_0(polyo1,M_1,M_2) : """ translate polyo1 pour amener M_1 en M_2 """ return [[N[0]-M_1[0]+M_2[0],N[1]-M_1[1]+M_2[1]] for N in polyo1] def Rot_1(polyo1,M_1,M_2) : """ tourne polyo1 de Pi/2 pour amener M_1 en M_2 """ return [[-N[1]+M_1[1]+M_2[0],N[0]-M_1[0]+M_2[1]] for N in polyo1] def Rot_2(polyo1,M_1,M_2) : """ tourne polyo1 de Pi pour amener M_1 en M_2 """ return [[-N[0]+M_1[0]+M_2[0],-N[1]+M_1[1]+M_2[1]] for N in polyo1] def Rot_3(polyo1,M_1,M_2) : """ tourne polyo1 de Pi/2 pour amener M_1 en M_2 """ return [[N[1]-M_1[1]+M_2[0],-N[0]+M_1[0]+M_2[1]] for N in polyo1] ### Fonction de calcul de frontière ### def Frontiere(polyo1,figure) : """ calcule la frontière de polyo1 """ L=[] for N in polyo1 : for x in [-1,1] : M=[N[0]+x,N[1]] if not(M in L or M in polyo1 or M in figure) : L.append(M) for y in [-1,1] : M=[N[0],N[1]+y] if not(M in L or M in polyo1 or M in figure) : L.append(M) return L ### Fonction de test de débordement def Test_Debordement(polyo,figure, dx,dy) : """ teste si le polyo est dans [0,dx]*[0,dy] et n'empiète pas sur figure """ Test=True for M in polyo : if M[0]>dx or M[1]>dy or M[0]<0 or M[1]<0 or M in figure : Test=False break return Test def Nbre_Intersect(figure1,figure2) : """ renvoie le nombre d'éléments communs entre deux listes sans redondance """ return len([N for N in figure1 if N in figure2]) ### Fonctions d'optimisation de polyominos def Meilleur_Polyo(polyo1,figure,frontiere,dx,dy) : """ trouve un déplacement de polyo1 pour lequel il n'y a pas débordement et pour lequel le nombre de cases de frontiere recouvertes par ce polyo1 déplacé est maximal """ compteur=0 Memoire=[] for P in frontiere : for N in polyo1 : for k in range(4) : Rot=eval("Rot_"+str(k)) polyo_Test=Rot(polyo1,N,P) val_Temp=Nbre_Intersect(polyo_Test,frontiere) if Test_Debordement(polyo_Test,figure, dx,dy) and val_Temp>compteur : compteur=val_Temp Memoire=polyo_Test return Memoire def Trouve_Successeur(polyo1,figure,frontiere,dx,dy) : """ trouve le polyomino suivant à placer : modifie la figure et la frontière """ figure_Temp=figure.copy() frontiere_Temp=frontiere.copy() polyo_suivant=Meilleur_Polyo(polyo1,figure,frontiere,dx,dy) figure_Temp.extend(polyo_suivant) frontiere_ajout=Frontiere(polyo_suivant,figure_Temp) frontiere_Temp.extend(frontiere_ajout) return [polyo_suivant,figure_Temp,frontiere_Temp] ### Interface Graphique ### from tkinter import * from random import * c=20 largeur=30 hauteur=20 Taille_largeur=c*largeur Taille_hauteur=c*hauteur Polyomino=[] flag=1 def click_case(event) : global Polyomino,figure,frontiere,largeur,hauteur,b3,flag if flag : # pour l'afficher une seule fois b3=Button(fenetre,text='Calculer un pavage',command=dessiner_polyomino) b3.pack(side =RIGHT, padx =3, pady =3) flag=0 x=event.x y=event.y i=int(x/c) j=int(y/c) if Polyomino==[] : canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='blue') Polyomino.append([i,j]) elif not([i,j] in Polyomino) : for M in Polyomino : if Distance_Points(M,[i,j])==1 : canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='blue',width=0) Polyomino.append([i,j]) break figure=Polyomino frontiere=Frontiere(Polyomino,figure) def dessiner_grille(): """ dessine la grille """ for i in range(largeur+2) : canevas.create_line(i*c,0,i*c,Taille_hauteur+c,width=1,fill='black') for j in range(hauteur+2) : canevas.create_line(0,j*c,Taille_largeur+c,j*c,width=1,fill='black') fenetre.update() def Couleur_Hasard(): Hexa_chiffres=[str(k) for k in range(10)]+["A","B","C","D","E","F"] couleur="#" for k in range(6) : couleur+=Hexa_chiffres[randint(0,15)] return couleur def dessiner_polyomino(): global Polyomino,figure,frontiere,Liste_Polyominos,b5,fenetre_fin b3.destroy() Test_Mise_A_Jour=True compteur=0 Liste_Polyominos=[Polyomino] # on place le polyomino initial dans une liste pour ensuite traiter les quatre couleurs while Test_Mise_A_Jour : Test_Mise_A_Jour=False compteur+=1 Resultat=Trouve_Successeur(Polyomino,figure,frontiere,largeur,hauteur) if Resultat[0] !=[] : # sous-entendu on a trouvé un successeur Test_Mise_A_Jour=True polyo,figure,frontiere=Resultat[0],Resultat[1],Resultat[2] Liste_Polyominos.append(polyo) #incorporation du polyo dans une liste pour traiter les 4 couleurs ensuite frontiere= [x for x in frontiere if not(x in figure)] couleur=Couleur_Hasard() for M in polyo : canevas.create_rectangle(M[0]*c, M[1]*c, (M[0]+1)*c, (M[1]+1)*c, fill=couleur,width=0) # L=["carre"+str(k) for k in range(len(frontiere))] # for k in range(len(frontiere)) : # L[k]=canevas.create_rectangle(frontiere[k][0]*c, frontiere[k][1]*c, (frontiere[k][0]+1)*c, (frontiere[k][1]+1)*c, fill="green") #fenetre.after(100) fenetre.update() #fenetre.after(100) # for k in range(len(frontiere)) : # canevas.delete(L[k]) # fenetre.update() # une fenêtre s'affiche pour cloturer le processus fenetre_fin=Tk() for k in range(3) : texte=Label(fenetre_fin,text=" Fin du pavage !! Il y a "+str(compteur)+" polyominos posés. ",font='Arial 20',fg="red") texte.pack() fenetre_fin.after(300) fenetre_fin.update() texte.destroy() fenetre_fin.after(200) fenetre_fin.update() texte=Label(fenetre_fin,text=" Fin du pavage !! Il y a "+str(compteur)+" polyominos posés. ",font='Arial 20',fg="red") texte.pack() b5 = Button(fenetre_fin, text ='Algorithme de coloriage du pavage', command =Algorithme_Quatre_Couleurs) b5.pack(side =RIGHT, padx =3, pady =3) b = Button(fenetre_fin, text ='Fermer', command =fenetre_fin.quit) b.pack(side =BOTTOM) fenetre_fin.mainloop() fenetre_fin.destroy() ### Problème des quatre couleurs ### # principe de l'algorithme de Welsh et Powell """ 1) Repérer le degré de chaque sommet. 2) Ranger les sommets par ordre de degrés décroissants (dans certains cas plusieurs possibilités). 3) Attribuer au premier sommet (A) de la liste une couleur. 4) Suivre la liste en attribuant la même couleur au premier sommet (B) qui ne soit pas adjacent à (A). 5) Suivre (si possible) la liste jusqu'au prochain sommet (C) qui ne soit adjacent ni à A ni à B. 6) Continuer jusqu'à ce que la liste soit finie. 7) Prendre une deuxième couleur pour le premier sommet (D) non encore coloré de la liste. 8) Répéter les opérations 4 à 7. 9) Continuer jusqu'à avoir colorié tous les sommets. """ def Test_distance_polyo(polyo1,polyo2) : """ teste si deux polyominos sont adjacents """ return min([min([Distance_Points(M,N) for N in polyo2]) for M in polyo1])==1 def Degres(L_Polyo) : """ calcule le degré de chaque élément de L_Polyo : la liste renvoyée est [[polyo,degre],...] """ L_Degres=[] for M in L_Polyo : L_Degres.append([M,len([N for N in L_Polyo if Test_distance_polyo(M,N)])]) return L_Degres Liste_Couleurs=["red","blue","yellow","green","orange","magenta","black","white"] def Dessine_Polyo_Quatre_Couleurs(polyo,couleur) : """ dessine le polyo de la couleur Liste_Couleurs[k] """ for M in polyo : canevas.create_rectangle(M[0]*c, M[1]*c, (M[0]+1)*c, (M[1]+1)*c, fill=couleur,width=0) fenetre.update() def Algorithme_Quatre_Couleurs() : """ calcule et effectue le coloriage du graphe planaire """ global Liste_Couleurs,Liste_Polyominos,b5,fenetre_fin b5.destroy() L_Temp=Degres(Liste_Polyominos).copy() ### on trie les sommets (polyominos) par degrés décroissant L=[Res[1] for Res in L_Temp] # liste des degrés L.sort(reverse=True) # tri décroissant Sommets_Tries=[] while L!=[] : for Res in L_Temp : if Res[1]==L[0] : Sommets_Tries.append(Res[0]) # ajout du sommet break # sortie de boucle for L.remove(L[0]) # suppression du plus haut degré L_Temp.remove(Res) # suppression de sommet pondéré # Sommets_Tries est la liste des sommets par degrés décroissant ### on commence vraiment l'algorithme de coloriage while Sommets_Tries!=[] : Test=True # vérifie si on a pu colorier un sommet Racine=Sommets_Tries[0] L_Couleur=[Racine] couleur=Liste_Couleurs[0] Dessine_Polyo_Quatre_Couleurs(Racine,couleur) # on marque le sommet d'une couleur Sommets_Tries.remove(Racine) # on le retire while Test : Test=False for polyo_Test in Sommets_Tries : Marqueur=0 for polyo in L_Couleur : if Test_distance_polyo(polyo_Test,polyo) : Marqueur=1 break if Marqueur==0 : #polyo n'est pas encore colorié et n'est adjacent à aucun sommet colorié Dessine_Polyo_Quatre_Couleurs(polyo_Test,couleur) L_Couleur.append(polyo_Test) Sommets_Tries.remove(polyo_Test) Test=True # on a pu colorier un autre sommet de la même couleur que d'autres ; on ajoute à la liste des sommets coloriés en "couleur" et on le retire des sommets non coloriés break Liste_Couleurs.remove(couleur) # on passe à une autre couleur de sommets fenetre_fin.quit ########## interface graphique ########## fenetre = Tk() canevas = Canvas(fenetre, width =Taille_largeur+c, height =Taille_hauteur+c, bg ='white') canevas.bind("", click_case) canevas.pack(side =TOP, padx =5, pady =5) dessiner_grille() b4 = Button(fenetre, text ='Quitter', command =fenetre.quit) b4.pack(side =RIGHT, padx =3, pady =3) fenetre.mainloop() fenetre.destroy()