Python en mathématiques - Défis

Rallye 2010 - Exercice 1

Mosaïque

Énoncé original

exercice 1, 2010

Exercice

Résoudre ce problème avec un programme python.

  • Un code possible
  • Toutes les grilles
  • Petite amélioration
  • Plus concis

On teste ligne par ligne toutes les positions pour une cellule rouge :

  1. On place une cellule rouge en ligne 1, colonne 1
  2. On place une cellule rouge en ligne 2, colonne 1
  3. On place une cellule rouge en ligne 3, colonne 1
  4. On place une cellule rouge en ligne 4, colonne 1
  5. On place une cellule rouge en ligne 5, colonne 1

On teste alors si la grille est valide. Ce n'est pas le cas : on passe à la colonne suivante en ligne 5 :

  1. une cellule rouge en ligne 1, colonne 1
  2. une cellule rouge en ligne 2, colonne 1
  3. une cellule rouge en ligne 3, colonne 1
  4. une cellule rouge en ligne 4, colonne 1
  5. une cellule rouge en ligne 5, colonne 2

On teste si la grille est valide. Ce n'est pas le cas. On passe à la colonne suivante en ligne 5...

Quand on aura constaté l'échec dans les 5 colonnes de la ligne 5, on passera à la valeur de colonne suivante en ligne 4 en recommençant à 1 en ligne 5 :

  1. une cellule rouge en ligne 1, colonne 1
  2. une cellule rouge en ligne 2, colonne 1
  3. une cellule rouge en ligne 3, colonne 1
  4. une cellule rouge en ligne 4, colonne 2
  5. une cellule rouge en ligne 5, colonne 1

...

On teste ainsi, avec cinq boucles imbriquées, toutes les grilles ayant exactement une cellule rouge par ligne. Et on ne retient le résultat que si cette grille est compatible avec les contraintes de l'énoncé (c'est à dire une unique cellule rouge par colonne et une unique cellule rouge par région).

Les tests de validité de la grille peuvent être faits dans la boucle la plus imbriquée ou être faits à chaque niveau (ce qui est fait dans le code ci-dessous) afin de ne pas poursuivre une boucle vouée à l'échec (par exemple, si la boucle la plus externe vient de placer une cellule rouge en ligne 1, seconde cellule, il est inutile de tester une cellule rouge en seconde cellule de la ligne 2).


 
# dimension de la grille à paver :
dimension = 5


# le partage en zones :
partage = [ [(0,0), (0,1), (0,2), (0,3)],
			[(0,4), (1,4), (2,4), (3,4), (4,4), (3,3), (4,3)],
			[(1,2), (1,3), (2,3)],
			[(1,0), (1,1), (2,0), (3,0), (4,0), (4,1), (4,2)],
			[(2,1), (2,2), (3,1), (3,2)]
]



def voisinage( cellule):
	"""
	cellule est un couple (ligne, colonne).
	La fonction renvoie la liste des couples coordonnées (ligne, colonne)
	des cellules qui touchent la cellule argument.
	"""
	# coordonnées de la cellule :
	lig, col = cellule[0], cellule[1]
	# liste des voisins pour une cellule non bordante :
	voisinage_apriori = [(lig-1,col-1), (lig-1, col), (lig-1, col+1), 
						(lig, col-1), (lig, col+1),
						(lig+1, col-1), (lig+1, col), (lig+1, col +1)]
	# filtrage pour le cas d'une cellule en bordure :
	voisinage_reel = []
	for cel in voisinage_apriori :
		if (0 <= cel[0] <  dimension) and (0 <= cel[1] <  dimension) :
			voisinage_reel.append( cel )
	return voisinage_reel



def compatible(rouge1, rouge2) :
	"""
	rouge1 est un couple (ligne_1, colonne_1).
	rouge2 est un couple (ligne_2, colonne_2).
	La fonction renvoie True si les cellules (ligne_1, colonne_1)
	et (ligne_2, colonne_2) peuvent être toutes deux rouges sans violer les règles, 
	la fonction renvoie False sinon.
	"""
	# incompatibilité si même ligne :
	if rouge1[0] == rouge2[0] : return False
	# incompatibilité si même colonne :
	if rouge1[1] == rouge2[1] : return False
	# incompatibilité si même zone :
	for zone in partage :
		if rouge1 in zone and rouge2 in zone : return False
	# incompatibilité si cases voisines :
	if rouge2 in voisinage(rouge1): return False
	return True
	


def grille_ok(  cellule) :
	"""
	grille contient des cellules jaunes et des cellules rouges.
	cellule est un couple (ligne, colonne).
	On vérifie si la cellule (ligne, colonne) peut être mise en rouge
	compte tenu des cellules déjà rouges.
	"""
	for lig in range(dimension):
		for col in range(dimension):
			if (lig, col) != cellule and grille[lig][col] == 'R' :
				if not(compatible((lig, col), cellule)) : return False
	return True
	
	
	
def nb_rouges(grille):
	"""
	compte le nombre de rouges dans grille.
	"""
	compteur = 0
	for lig in range(dimension):
		for col in range(dimension) :
			if grille[lig][col] == 'R':
				compteur += 1
	return compteur
	
	
def raz_ligne(grille, ligne):
	"""
	Remet toute la ligne numéro ligne de grille à jaune.
	"""
	for col in range(dimension):
		grille[ligne][col] = 'J'
		
def raz_sousligne(grille, ligne) :
	"""
	Remet à jaune toutes les cellules de ligne et des lignes suivantes.
	"""
	for lig in range(ligne, dimension):
		raz_ligne(grille, lig)
	
	
def afficher( grille ):
	""" 
	Affiche la grille !
	"""
	for lig in range(dimension):
		for col in range(dimension):
			print(grille[lig][col], end = " ")
		print()
	print()
		

# la grille, remplie de cases jaunes :
grille = [ ['J' for x in range(dimension)] for y in range(dimension)]



# on place en ligne 1 une cellule rouge
# puis on place une cellule rouge en ligne 2, compatible avec celle de la ligne 1
# puis on place une cellule rouge en ligne 3, compatible avec celles des lignes 1 et 2
# ...
# on affiche si on a placé une cellule rouge dans chaque ligne
# A chaque nouvelle case essayée dans une ligne, on met toute la ligne à jaune ainsi
# que les lignes qui sont en dessous avant les nouveaux essais.
for col_lig0 in range(dimension) :
	
	raz_sousligne(grille, 0)
	grille[0][col_lig0] = 'R'
	 
	
	for col_lig1 in range(dimension) :
		raz_sousligne(grille, 1)  
		if  grille_ok(  (1,col_lig1) ) :
			grille[1][col_lig1] = 'R'
			
			for col_lig2 in range(dimension) : 
				raz_sousligne(grille, 2) 
				if  col_lig2 != 1 and grille_ok(  (2,col_lig2) )   :
					grille[2][col_lig2] = 'R'
				
					for col_lig3 in range(dimension) : 
						raz_sousligne(grille, 3)
						if col_lig3 != 1 and  grille_ok(  (3,col_lig3) )   :
							grille[3][col_lig3] = 'R'
							
							
							for col_lig4 in range(dimension) :
								raz_sousligne(grille, 4)  
								if  grille_ok(  (4,col_lig4) ) :
									grille[4][col_lig4] = 'R'
									if nb_rouges(grille) == 5 :
										afficher( grille )
			


On obtient :

J R J J J 
J J J R J 
R J J J J 
J J R J J 
J J J J R

Dans le code précédent, on s'assure que les deux cellules jaunes imposées par l'énoncé restent jaunes en leur interdisant de prendre la couleur rouge : if col_lig2 != 1 and ..., if col_lig3 != 1 and .... Si l'on supprime ces deux tests, on obtiendra toutes les grilles possibles respectant les contraintes. Il n'y en a en fait que trois.

Le code :


# dimension de la grille à paver :
dimension = 5


# le partage en zones :
partage = [ [(0,0), (0,1), (0,2), (0,3)],
			[(0,4), (1,4), (2,4), (3,4), (4,4), (3,3), (4,3)],
			[(1,2), (1,3), (2,3)],
			[(1,0), (1,1), (2,0), (3,0), (4,0), (4,1), (4,2)],
			[(2,1), (2,2), (3,1), (3,2)]
]



def voisinage( cellule):
	"""
	cellule est un couple (ligne, colonne).
	La fonction renvoie la liste des couples coordonnées (ligne, colonne)
	des cellules qui touchent la cellule argument.
	"""
	# coordonnées de la cellule :
	lig, col = cellule[0], cellule[1]
	# liste des voisins pour une cellule non bordante :
	voisinage_apriori = [(lig-1,col-1), (lig-1, col), (lig-1, col+1),
						(lig, col-1), (lig, col+1),
						(lig+1, col-1), (lig+1, col), (lig+1, col +1)]
	# filtrage pour le cas d'une cellule en bordure :
	voisinage_reel = []
	for cel in voisinage_apriori :
		if (0 <= cel[0] <  dimension) and (0 <= cel[1] <  dimension) :
			voisinage_reel.append( cel )
	return voisinage_reel



def compatible(rouge1, rouge2) :
	"""
	rouge1 est un couple (ligne_1, colonne_1).
	rouge2 est un couple (ligne_2, colonne_2).
	La fonction renvoie True si les cellules (ligne_1, colonne_1)
	et (ligne_2, colonne_2) peuvent être toutes deux rouges sans violer les règles,
	la fonction renvoie False sinon.
	"""
	# incompatibilité si même ligne :
	if rouge1[0] == rouge2[0] : return False
	# incompatibilité si même colonne :
	if rouge1[1] == rouge2[1] : return False
	# incompatibilité si même zone :
	for zone in partage :
		if rouge1 in zone and rouge2 in zone : return False
	# incompatibilité si cases voisines :
	if rouge2 in voisinage(rouge1): return False
	return True



def grille_ok(  cellule) :
	"""
	grille contient des cellules jaunes et des cellules rouges.
	cellule est un couple (ligne, colonne).
	On vérifie si la cellule (ligne, colonne) peut être mise en rouge
	compte tenu des cellules déjà rouges.
	"""
	for lig in range(dimension):
		for col in range(dimension):
			if (lig, col) != cellule and grille[lig][col] == 'R' :
				if not(compatible((lig, col), cellule)) : return False
	return True



def nb_rouges(grille):
	"""
	compte le nombre de rouges dans grille.
	"""
	compteur = 0
	for lig in range(dimension):
		for col in range(dimension) :
			if grille[lig][col] == 'R':
				compteur += 1
	return compteur


def raz_ligne(grille, ligne):
	"""
	Remet toute la ligne numéro ligne de grille à jaune.
	"""
	for col in range(dimension):
		grille[ligne][col] = 'J'

def raz_sousligne(grille, ligne) :
	"""
	Remet à jaune toutes les cellules de ligne et des lignes suivantes.
	"""
	for lig in range(ligne, dimension):
		raz_ligne(grille, lig)


def afficher( grille ):
	"""
	Affiche la grille !
	"""
	for lig in range(dimension):
		for col in range(dimension):
			print(grille[lig][col], end = " ")
		print()
	print()


# la grille, remplie de cases jaunes :
grille = [ ['J' for x in range(dimension)] for y in range(dimension)]



# on place en ligne 1 une cellule rouge
# puis on place une cellule rouge en ligne 2, compatible avec celle de la ligne 1
# puis on place une cellule rouge en ligne 3, compatible avec celles des lignes 1 et 2
# ...
# on affiche si on a placé une cellule rouge dans chaque ligne
# A chaque nouvelle case essayée dans une ligne, on met toute la ligne à jaune ainsi
# que les lignes qui sont en dessous avant les nouveaux essais.
for col_lig0 in range(dimension) :

	raz_sousligne(grille, 0)
	grille[0][col_lig0] = 'R'


	for col_lig1 in range(dimension) :
		raz_sousligne(grille, 1)
		if  grille_ok(  (1,col_lig1) ) :
			grille[1][col_lig1] = 'R'

			for col_lig2 in range(dimension) :
				raz_sousligne(grille, 2)
				if    grille_ok(  (2,col_lig2) )   :
					grille[2][col_lig2] = 'R'

					for col_lig3 in range(dimension) :
						raz_sousligne(grille, 3)
						if    grille_ok(  (3,col_lig3) )   :
							grille[3][col_lig3] = 'R'


							for col_lig4 in range(dimension) :
								raz_sousligne(grille, 4)
								if  grille_ok(  (4,col_lig4) ) :
									grille[4][col_lig4] = 'R'
									if nb_rouges(grille) == 5 :
										afficher( grille )

Les grilles :

R J J J J 
J J J R J 
J R J J J 
J J J J R 
J J R J J 

J R J J J 
J J J R J 
R J J J J 
J J R J J 
J J J J R 

J J R J J 
R J J J J 
J J J R J 
J R J J J 
J J J J R 

Principe

Comme on ajoute une case rouge ligne par ligne, lorsqu'on vérifie la compatibilité de la nouvelle cellule avec les rouges déjà présents, il n'est pas utile de vérifier les lignes sous cette cellule (puisqu'elles n'ont pas encore de cases rouges). On diminue donc un peu le nombre de tests en réécrivant la fonction grille_ok. De cette façon, on peut également remplacer les appels raz_sousligne effectués dans les boucles imbriquées par des simples raz_ligne.

Le code


# dimension de la grille à paver :
dimension = 5


# le partage en zones :
partage = [ [(0,0), (0,1), (0,2), (0,3)],
			[(0,4), (1,4), (2,4), (3,4), (4,4), (3,3), (4,3)],
			[(1,2), (1,3), (2,3)],
			[(1,0), (1,1), (2,0), (3,0), (4,0), (4,1), (4,2)],
			[(2,1), (2,2), (3,1), (3,2)]
]



def voisinage( cellule):
	"""
	cellule est un couple (ligne, colonne).
	La fonction renvoie la liste des couples coordonnées (ligne, colonne)
	des cellules qui touchent la cellule argument.
	"""
	# coordonnées de la cellule :
	lig, col = cellule[0], cellule[1]
	# liste des voisins pour une cellule non bordante :
	voisinage_apriori = [(lig-1,col-1), (lig-1, col), (lig-1, col+1),
						(lig, col-1), (lig, col+1),
						(lig+1, col-1), (lig+1, col), (lig+1, col +1)]
	# filtrage pour le cas d'une cellule en bordure :
	voisinage_reel = []
	for cel in voisinage_apriori :
		if (0 <= cel[0] <  dimension) and (0 <= cel[1] < dimension) :
			voisinage_reel.append( cel )
	return voisinage_reel



def compatible(rouge1, rouge2) :
	"""
	rouge1 est un couple (ligne_1, colonne_1).
	rouge2 est un couple (ligne_2, colonne_2).
	La fonction renvoie True si les cellules (ligne_1, colonne_1)
	et (ligne_2, colonne_2) peuvent être toutes deux rouges sans violer les règles,
	la fonction renvoie False sinon.
	"""
	# incompatibilité si même ligne :
	if rouge1[0] == rouge2[0] : return False
	# incompatibilité si même colonne :
	if rouge1[1] == rouge2[1] : return False
	# incompatibilité si même zone :
	for zone in partage :
		if rouge1 in zone and rouge2 in zone : return False
	# incompatibilité si cases voisines :
	if rouge2 in voisinage(rouge1): return False
	return True



def grille_ok(  cellule) :
	"""
	grille contient des cellules jaunes et des cellules rouges.
	cellule est un couple (ligne, colonne).
	On vérifie si la cellule (ligne, colonne) peut être mise en rouge
	compte tenu des cellules déjà rouges.
	On ne contrôle ici que la compatibilité avec les lignes au-dessus
	de la cellule testée.
	"""
	for lig in range(cellule[0]):
		for col in range(dimension):
			if grille[lig][col] == 'R' :
				if not(compatible((lig, col), cellule)) : return False
	return True



def nb_rouges(grille):
	"""
	compte le nombre de rouges dans grille.
	"""
	compteur = 0
	for lig in range(dimension):
		for col in range(dimension) :
			if grille[lig][col] == 'R':
				compteur += 1
	return compteur


def raz_ligne(grille, ligne):
	"""
	Remet toute la ligne numéro ligne de grille à jaune.
	"""
	for col in range(dimension):
		grille[ligne][col] = 'J'

 

def afficher( grille ):
	"""
	Affiche la grille !
	"""
	for lig in range(dimension):
		for col in range(dimension):
			print(grille[lig][col], end = " ")
		print()
	print()


# la grille, remplie de cases jaunes :
grille = [ ['J' for x in range(dimension)] for y in range(dimension)]



# on place en ligne 1 une cellule rouge
# puis on place une cellule rouge en ligne 2, compatible avec celle de la ligne 1
# puis on place une cellule rouge en ligne 3, compatible avec celles des lignes 1 et 2
# ...
# on affiche si on a placé une cellule rouge dans chaque ligne
# A chaque nouvelle case essayée dans une ligne, on met toute la ligne à jaune ainsi
# que les lignes qui sont en dessous avant les nouveaux essais.
for col_lig0 in range(dimension) :

	raz_ligne(grille, 0)
	grille[0][col_lig0] = 'R'


	for col_lig1 in range(dimension) :
		raz_ligne(grille, 1)
		if  grille_ok(  (1,col_lig1) ) :
			grille[1][col_lig1] = 'R'

			for col_lig2 in range(dimension) :
				raz_ligne(grille, 2)
				if    grille_ok(  (2,col_lig2) )   :
					grille[2][col_lig2] = 'R'

					for col_lig3 in range(dimension) :
						raz_ligne(grille, 3)
						if    grille_ok(  (3,col_lig3) )   :
							grille[3][col_lig3] = 'R'


							for col_lig4 in range(dimension) :
								raz_ligne(grille, 4)
								if  grille_ok(  (4,col_lig4) ) :
									grille[4][col_lig4] = 'R'
									if nb_rouges(grille) == 5 :
										afficher( grille )

Dans la recherche de toutes les solutions, on peut rendre plus concis (et plus facilement généralisable) l'imbrication de boucles à l'aide d'une fonction récursive :


from copy import deepcopy

# dimension de la grille à paver :
dimension = 5


# le partage en zones :
partage = [ [(0,0), (0,1), (0,2), (0,3)],
			[(0,4), (1,4), (2,4), (3,4), (4,4), (3,3), (4,3)],
			[(1,2), (1,3), (2,3)],
			[(1,0), (1,1), (2,0), (3,0), (4,0), (4,1), (4,2)],
			[(2,1), (2,2), (3,1), (3,2)]
]



def voisinage( cellule):
	"""
	cellule est un couple (ligne, colonne).
	La fonction renvoie la liste des couples coordonnées (ligne, colonne)
	des cellules qui touchent la cellule argument.
	"""
	# coordonnées de la cellule :
	lig, col = cellule[0], cellule[1]
	# liste des voisins pour une cellule non bordante :
	voisinage_apriori = [(lig-1,col-1), (lig-1, col), (lig-1, col+1),
						(lig, col-1), (lig, col+1),
						(lig+1, col-1), (lig+1, col), (lig+1, col +1)]
	# filtrage pour le cas d'une cellule en bordure :
	voisinage_reel = []
	for cel in voisinage_apriori :
		if (0 <= cel[0] <  dimension) and (0 <= cel[1] <  dimension) :
			voisinage_reel.append( cel )
	return voisinage_reel



def compatible(rouge1, rouge2) :
	"""
	rouge1 est un couple (ligne_1, colonne_1).
	rouge2 est un couple (ligne_2, colonne_2).
	La fonction renvoie True si les cellules (ligne_1, colonne_1)
	et (ligne_2, colonne_2) peuvent être toutes deux rouges sans violer les règles,
	la fonction renvoie False sinon.
	"""
	# incompatibilité si même ligne :
	if rouge1[0] == rouge2[0] : return False
	# incompatibilité si même colonne :
	if rouge1[1] == rouge2[1] : return False
	# incompatibilité si même zone :
	for zone in partage :
		if rouge1 in zone and rouge2 in zone : return False
	# incompatibilité si cases voisines :
	if rouge2 in voisinage(rouge1): return False
	return True



def grille_ok( grille, cellule) :
	"""
	grille contient des cellules jaunes et des cellules rouges.
	cellule est un couple (ligne, colonne).
	On vérifie si la cellule (ligne, colonne) peut être mise en rouge
	compte tenu des cellules déjà rouges.
	"""
	for lig in range(dimension):
		for col in range(dimension):
			if (lig, col) != cellule and grille[lig][col] == 'R' :
				if not(compatible((lig, col), cellule)) : return False
	return True



def nb_rouges(grille):
	"""
	compte le nombre de rouges dans grille.
	"""
	compteur = 0
	for lig in range(dimension):
		for col in range(dimension) :
			if grille[lig][col] == 'R':
				compteur += 1
	return compteur


def raz_ligne(grille, ligne):
	"""
	Remet toute la ligne numéro ligne de grille à jaune.
	"""
	for col in range(dimension):
		grille[ligne][col] = 'J'

def raz_sousligne(grille, ligne) :
	"""
	Remet à jaune toutes les cellules de ligne et des lignes suivantes.
	"""
	for lig in range(ligne, dimension):
		raz_ligne(grille, lig)


def afficher( grille ):
	"""
	Affiche la grille !
	"""
	for lig in range(dimension):
		for col in range(dimension):
			print(grille[lig][col], end = " ")
		print()
	print()


# la grille, remplie de cases jaunes :
grille = [ ['J' for x in range(dimension)] for y in range(dimension)]

Solutions = []


def resoudre(grille, ligne = 0) :
	G = deepcopy(grille)
	
	if ligne == dimension :
		Solutions.append(G)
	else :
		for col in range(dimension):
			raz_ligne(G, ligne)
			if grille_ok(G, (ligne,col) ) :
				G[ligne][col] = 'R'
				
				resoudre(G, ligne+1)
	
resoudre(grille)
for g in Solutions :
	afficher(g)
R J J J J 
J J J R J 
J R J J J 
J J J J R 
J J R J J 

J R J J J 
J J J R J 
R J J J J 
J J R J J 
J J J J R 

J J R J J 
R J J J J 
J J J R J 
J R J J J 
J J J J R 

Représenter la solution

Avec la tortue python, représenter la solution du problème.

  • Un code possible

On reprend le code précédent dans un fichier que l'on nomme solu.py :


from copy import deepcopy
# dimension de la grille à paver :
dimension = 5


# le partage en zones :
partage = [ [(0,0), (0,1), (0,2), (0,3)],
			[(0,4), (1,4), (2,4), (3,4), (4,4), (3,3), (4,3)],
			[(1,2), (1,3), (2,3)],
			[(1,0), (1,1), (2,0), (3,0), (4,0), (4,1), (4,2)],
			[(2,1), (2,2), (3,1), (3,2)]
]



def voisinage( cellule):
	"""
	cellule est un couple (ligne, colonne).
	La fonction renvoie la liste des couples coordonnées (ligne, colonne)
	des cellules qui touchent la cellule argument.
	"""
	# coordonnées de la cellule :
	lig, col = cellule[0], cellule[1]
	# liste des voisins pour une cellule non bordante :
	voisinage_apriori = [(lig-1,col-1), (lig-1, col), (lig-1, col+1),
						(lig, col-1), (lig, col+1),
						(lig+1, col-1), (lig+1, col), (lig+1, col +1)]
	# filtrage pour le cas d'une cellule en bordure :
	voisinage_reel = []
	for cel in voisinage_apriori :
		if (0 <= cel[0] < dimension) and (0 <= cel[1] <  dimension) :
			voisinage_reel.append( cel )
	return voisinage_reel



def compatible(rouge1, rouge2) :
	"""
	rouge1 est un couple (ligne_1, colonne_1).
	rouge2 est un couple (ligne_2, colonne_2).
	La fonction renvoie True si les cellules (ligne_1, colonne_1)
	et (ligne_2, colonne_2) peuvent être toutes deux rouges sans violer les règles,
	la fonction renvoie False sinon.
	"""
	# incompatibilité si même ligne :
	if rouge1[0] == rouge2[0] : return False
	# incompatibilité si même colonne :
	if rouge1[1] == rouge2[1] : return False
	# incompatibilité si même zone :
	for zone in partage :
		if rouge1 in zone and rouge2 in zone : return False
	# incompatibilité si cases voisines :
	if rouge2 in voisinage(rouge1): return False
	return True



def grille_ok(  cellule) :
	"""
	grille contient des cellules jaunes et des cellules rouges.
	cellule est un couple (ligne, colonne).
	On vérifie si la cellule (ligne, colonne) peut être mise en rouge
	compte tenu des cellules déjà rouges.
	"""
	for lig in range(dimension):
		for col in range(dimension):
			if (lig, col) != cellule and grille[lig][col] == 'R' :
				if not(compatible((lig, col), cellule)) : return False
	return True



def nb_rouges(grille):
	"""
	compte le nombre de rouges dans grille.
	"""
	compteur = 0
	for lig in range(dimension):
		for col in range(dimension) :
			if grille[lig][col] == 'R':
				compteur += 1
	return compteur


def raz_ligne(grille, ligne):
	"""
	Remet toute la ligne numéro ligne de grille à jaune.
	"""
	for col in range(dimension):
		grille[ligne][col] = 'J'

def raz_sousligne(grille, ligne) :
	"""
	Remet à jaune toutes les cellules de ligne et des lignes suivantes.
	"""
	for lig in range(ligne, dimension):
		raz_ligne(grille, lig)


def afficher( grille ):
	"""
	Affiche la grille !
	"""
	for lig in range(dimension):
		for col in range(dimension):
			print(grille[lig][col], end = " ")
		print()
	print()


# la grille, remplie de cases jaunes :
grille = [ ['J' for x in range(dimension)] for y in range(dimension)]



# on place en ligne 1 une cellule rouge
# puis on place une cellule rouge en ligne 2, compatible avec celle de la ligne 1
# puis on place une cellule rouge en ligne 3, compatible avec celles des lignes 1 et 2
# ...
# on affiche si on a placé une cellule rouge dans chaque ligne
# A chaque nouvelle case essayée dans une ligne, on met toute la ligne à jaune ainsi
# que les lignes qui sont en dessous avant les nouveaux essais.
for col_lig0 in range(dimension) :

	raz_sousligne(grille, 0)
	grille[0][col_lig0] = 'R'


	for col_lig1 in range(dimension) :
		raz_sousligne(grille, 1)
		if  grille_ok(  (1,col_lig1) ) :
			grille[1][col_lig1] = 'R'

			for col_lig2 in range(dimension) :
				raz_sousligne(grille, 2)
				if  col_lig2 != 1 and grille_ok(  (2,col_lig2) )   :
					grille[2][col_lig2] = 'R'

					for col_lig3 in range(dimension) :
						raz_sousligne(grille, 3)
						if col_lig3 != 1 and  grille_ok(  (3,col_lig3) )   :
							grille[3][col_lig3] = 'R'


							for col_lig4 in range(dimension) :
								raz_sousligne(grille, 4)
								if  grille_ok(  (4,col_lig4) ) :
									grille[4][col_lig4] = 'R'
									if nb_rouges(grille) == 5 :
										solution = deepcopy(grille)
afficher(solution)  

Dans le script suivant, on commence par charger le résultat du script précédent.



from solu import solution

from turtle import *

## Constantes ##
unite = 10						# unité : longueur du côté d'une case du damier
nb_lignes = 5					# nombre de lignes du damier
nb_colonnes = 5					# nombre de colonnes du damier
 

##----- Modification du repère d'origine -----##
largeur = (max(nb_lignes, nb_colonnes)+1)*unite
setworldcoordinates( -unite, -unite, largeur, largeur)

delay(0) #   tortue rapide 


##----- Définition des fonctions -----##
def aller_a_sans_tracer(x, y) :
    """ On place la tortue en (x,y) sans tracer."""
    penup()
    goto(x, y)
    pendown()


def carre(x, y, couleur) :
	"""
	Dessine un carré de sommet inférieur gauche (x,y),
	de côté de longueur unite,
	côtés parallèles aux bords de l'écran.
	Couleur de remplissage : couleur.
	"""
	aller_a_sans_tracer(x*unite, y*unite)
	fillcolor(couleur)
	begin_fill()
	for i in range(4):
		forward(unite)
		left(90)
	end_fill()


def ligne(y):
	"""
	Dessine une ligne du damier, alternance des couleurs
	"""
	 
	for x in range(nb_colonnes):
		carre(x, y, 'red' if solution[4-y][x] == 'R' else 'yellow')
		 


def damier():
	"""
	Dessine le damier.
	"""
	for l in range(0, nb_lignes) :
		ligne(l)

        
def partage():
	"""
	Délimite les régions.
	"""
	aller_a_sans_tracer(0, 0)
	setheading(0)
	pensize(6)
	forward(5*unite)
	left(90)
	forward(5*unite)
	left(90)
	forward(5*unite)
	left(90)
	forward(5*unite)
	aller_a_sans_tracer(3*unite, 0)
	setheading(90)
	forward(3*unite)
	left(90)
	forward(2*unite)
	left(90)
	forward(2*unite)
	left(90)
	forward(2*unite)
	aller_a_sans_tracer(3*unite, 2*unite)
	setheading(0)
	forward(unite)
	left(90)
	forward(3*unite)
	aller_a_sans_tracer(4*unite, 4*unite)
	setheading(180)
	forward(4*unite)
	aller_a_sans_tracer(2*unite, 4*unite)
	setheading(-90)
	forward(unite)


##----- Tracé du damier -----##
damier()
partage()
hideturtle()
exitonclick() 

On obtient :
solution pavage