TryAlgo

Utiliser Paint pour les sudokus

Introduction

Vous vous souvenez du magnifique cliffhanger de l’article sur l’outil “Seau” de Paint ? (Bien évidemment. Sinon, vous êtes tout invités à le relire). On y avait découvert (un) algorithme de parcours des noeuds dans un graphe, et on l’avait utilisé pour implémenter l’outil “Seau” : en cliquant sur un pixel avec une certaine couleur, on colorie ce pixel, et tous ses pixels voisins de la même couleur initiale. En résumé :

(Tout un article pour décrire cela, hé oui. Mais au moins, il y avait des illustrations de petits coeurs)

Et à la fin, j’avais écrit que l’on pouvait utiliser cet algorithme pour résoudre des sudokus. C’est donc parti !

Problème

Le sudoku est un jeu de puzzle où l’on doit compléter par des chiffres de 1 à 9 les cases vides d’une grille de 9 cases par 9, selon les trois règles suivantes :

Par exemple, la grille de sudoku incomplète suivante :

Cases    A    B    C    D   E    F    G   H    I
a   8      4    9       3      7   1
b   6   3   5    8       7      2   4
c   7   1   9       2    4      5   
d       8    7       9    1    3       6
e    1         7   3    6          9
f    3       6   4   8       2    1   
g      6       5    4       7   3   8
h   4   7       3       2   1    9   5
i   9   5       1       8    4      2

peut être complétée en une grille complète et correcte de la façon suivante :

Cases    A    B    C    D    E    F   G   H   I
a   8   [2]   4    9    [5]    3   [6]   7   1
b   6   3   5    8    [1]    7   [9]   2   4
c   7   1   9    [6]    2    4   [8]   5   [3]
d   [5]    8    7   [2]   9   1   3    [4]   6
e   1    [4]    [2]   7   3   6   [5]    [8]    9
f    3   [9]    6   4   8   [5]    2   1    [7]
g   [2]   6   [1]    5    4    [9]    7   3   8
h   4   7   [8]    3    [6]    2   1   9   5
i   9   5   [3]    1    [7]    8   4   [6]   2

Les chiffres en gras permettent de faire ressortir les sous-grilles de 3 cases par 3 dont je parlais plus tôt.

Utiliser Paint ?

Sachant que l’on sait que l’on va utiliser la même méthode que l’outil “Seau”, comment fait-on pour ramener un problème de sudoku à un problème de coloriage de pixels ? Vous l’aurez deviné : on va convertir la grille de sudoku en graphe. Pour convertir ce problème en graphe, on doit donc déterminer :

Laissez-vous le temps de la réflexion avant de poursuivre. En particulier, prenez une feuille de papier, et écrivez une idée de réponse à ces deux questions. En particulier, repensez à ce qui a été fait pour l’outil Seau. Ce ne sera probablement pas l’exacte même formalisation qui sera utilisée, mais vous serez dans la bonne direction.

Faites-le.

Formalisation du problème

J’espère que vous avez noirci cette feuille de papier.

(a) Ils sont situés sur la même ligne.

(b) Ils sont dans la même colonne.

(c) Ils sont dans la même sous-grille 3 x 3.

Mais il manque une règle : celle de l’unique occurrence sur les lignes, colonnes et sous-grilles. Et c’est là où va intervenir la partie coloriage dans la résolution du problème : on attribue une couleur par valeur possible de case (autrement dit, 9). Le but sera alors de colorier le graphe de telle sorte à ce que, pour toute paire de noeuds voisins, ces deux noeuds aient des couleurs distinctes.

Par exemple, considérons une grille incomplète de sudoku 4 x 4 (pour plus de lisibilité…). En particulier, les sous-grilles seront de taille 2, et les lignes et les colonnes seront de longueur 2. On complétera la grille par les valeurs 1 (bleu), 2 (rouge), 3 (vert) ou 4 (orange) :

Cases    A    B    C    D
a         3   4
b      4   2   1
c            3
d    1   3   4   2

(Je ne vous ferai pas l’insulte de vous donner la solution).

Le graphe correspondant est le suivant :

Maintenant que l’on a le graphe, comment procéder pour résoudre le problème de coloriage associé ?

Résolution du problème de coloriage

En quoi l’algorithme utilisé pour l’outil Seau va-t-il nous être utile ? En fait, les noeuds déjà coloriés nous donnent un ensemble de contraintes pour le choix de la couleur de leurs voisins. Essentiellement, l’algorithme consiste à rassembler toutes ces contraintes, à les propager aux voisins des noeuds déjà coloriés (comme la couleur pour l’outil Seau), et, à partir de ce moment-là, chercher les couleurs restantes qui peuvent être utilisées. A chaque nouveau noeud colorié, on réitère le processus de propagation de contraintes aux voisins, jusqu’à ce que tous les noeuds sont coloriés (et on trouve une solution), ou qu’un noeud ne puisse être colorié (car toutes les couleurs sont interdites pour ce noeud). Dans ce cas, on effectue un backtracking (voir cet article), et on revient à l’étape précédente, marque la couleur que l’on avait choisie à cette étape comme “interdite”, et on poursuit l’algorithme.

On associe donc à chaque noeud une propriété “couleurs interdites”, qui nous donne la liste des couleurs des voisins du noeud considéré.

A chaque étape de l’algorithme :

En Python, on peut implémenter cette procédure de la manière suivante :

couleurs = ["white",
	"blue", "red", "green", 
	"orange", "yellow", "pink",
	"cyan", "purple", "grey"]

def colorier_graphe(graphe):
	# noeuds est une liste d'éléments (nom du noeud, couleur du noeud)
	# aretes est une matrice d'adjacence
	noeuds, aretes = graphe
	nn = len(noeuds)
	# Propriété "couleurs interdites" pour les noeuds
	# vide pour le moment (qui contiendra des couples (couleur, noeud voisin);
	# garder le noeud d'où provient la contrainte nous permettra de backtracker)
	# On convertit les couleurs en nombres pour faciliter les comparaisons
	sommets = [[x[0], couleurs.index(x[1]), []] for x in noeuds]
	# Garder une trace des noeuds déjà coloriés
	est_colorie = [False for i in range(nn)]
	noeud_colorie_indices = []
	for i in range(nn):
		# 0 est non colorié
		if (not(sommets[i][1] == 0)):
			noeud_colorie_indices.append(i)
			est_colorie[i] = True
	sommets = backtracking_colorier(est_colorie, sommets, aretes, noeud_colorie_indices)
	if (sommets == "BACKTRACKING"):
		return("Insoluble")
	noeuds = [[x[0], couleurs[x[1]]] for x in sommets]
	return([noeuds, aretes])

def backtracking_colorier(est_colorie, sommets, aretes, noeud_colorie_indices):
	nn = len(sommets)
	from math import sqrt
	nb_couleurs = int(sqrt(nn))
	# S'il existe des noeuds dont la couleur doit être propagée
	while (len(noeud_colorie_indices) > 0):
		noeud_indice = noeud_colorie_indices.pop()
		couleur = sommets[noeud_indice][1]
		# Propagation de la contrainte sur 
		# la couleur aux voisins du noeud
		for i in range(nn):
			if (aretes[i][noeud_indice]):
				# Alors le noeud d'indice i est un voisin du 
				# noeud d'indice noeud_indice
				# On met à jour sa propriété "couleurs interdites"
				sommets[i][2] += [[couleur, noeud_indice]]
	# Si tous les noeuds sont coloriés
	# retourner l'ensemble des sommets et leurs couleurs
	if (all(est_colorie)):
		return(sommets)
	# Sinon, on considère un noeud non colorié
	# (on recherche le premier indice tel que l'élément
	# correspondant ne soit pas colorié
	# Tous les noeuds ont au moins une couleur disponible
	# sinon, on aura retourné une exception avant
	noeud_non_colorie_indice = est_colorie.index(False)
	couleurs_interdites = [paire[0] for paire in sommets[noeud_non_colorie_indice][2]]
	couleurs_disponibles = filter(lambda x: not(x in couleurs_interdites), range(1, nb_couleurs+1))
	# Si le noeud ne peut être colorié
	if (len(couleurs_disponibles) == 0):
		return("BACKTRACKING")
	# Sinon on le colorie par une couleur disponible
	couleur_choisie = min(couleurs_disponibles)
	est_colorie[noeud_non_colorie_indice] = True
	sommets[noeud_non_colorie_indice][1] = couleur_choisie
	noeud_colorie_indices = [noeud_non_colorie_indice]
	res = backtracking_colorier(est_colorie, sommets, aretes, noeud_colorie_indices)
	# Backtracking
	if (res == "BACKTRACKING"):
		# On ajoute la couleur actuelle du noeud à la liste des couleurs interdites
		couleurs_interdites = sommets[noeud_non_colorie_indice][2]
		sommets[noeud_non_colorie_indice][2] += [[sommets[noeud_non_colorie_indice][1], "backtracking"]]
		# On "décolorie" le noeud
		sommets[noeud_non_colorie_indice][1] = 0
		est_colorie[noeud_non_colorie_indice] = False
		# On annule les contraintes sur ses voisins
		# (d'où l'intérêt de conserver le noeud voisin qui donne la contrainte)
		for i in range(nn):
			if (aretes[i][noeud_non_colorie_indice]):
				sommets[i][2] = filter(lambda paire:not(paire[1]==noeud_non_colorie_indice), sommets[i][2])
		# Et on recommence !
		return(backtracking_colorier(est_colorie, sommets, aretes, noeud_colorie_indices))
	else:
		return(res)

Exemples

Appliquons ce programme au problème 4 x 4 de la section précédente (les zéros dénotent les cases à compléter) :

sudoku44 = [
	[0, 0, 3, 4],
	[0, 4, 2, 1],
	[0, 0, 0, 3],
	[1, 3, 4, 2]
]

La solution (que vous auriez facilement trouvée par vous-même) est :

solution44 = [
	[2, 1, 3, 4],
	[3, 4, 2, 1],
	[4, 2, 1, 3],
	[1, 3, 4, 2]
]

En appliquant l’algorithme précédent, on obtient le graphe colorié suivant :

graphe = construire_graphe(sudoku44)
graphe = colorier_graphe(graphe)
grille = reconstruire_grille(graphe)
construire_graphe(grille)

En convertissant cette solution en grille complète de sudoku, on obtient :

[
	[2, 1, 3, 4],
	[3, 4, 2, 1],
	[4, 2, 1, 3],
	[1, 3, 4, 2]
]

Qui est la même que la solution que nous avons trouvée manuellement.

Appliquons le programme maintenant au problème 9 x 9 :

exemple = [
	[8, 0, 4, 9, 0, 3, 0, 7, 1],
	[6, 3, 5, 8, 0, 7, 0, 2, 4],
	[7, 1, 9, 0, 2, 4, 0, 5, 0],
	[0, 8, 7, 0, 9, 1, 3, 0, 6],
	[1, 0, 0, 7, 3, 6, 0, 0, 9],
	[3, 0, 6, 4, 8, 0, 2, 1, 0],
	[0, 6, 0, 5, 4, 0, 7, 3, 8],
	[4, 7, 0, 3, 0, 2, 1, 9, 5],
	[9, 5, 0, 1, 0, 8, 4, 0, 2]
]
graphe = construire_graphe(exemple)
graphe = colorier_graphe(graphe)
grille = reconstruire_grille(graphe)
construire_graphe(grille)

Le graphe obtenu est horrible. Vous pouvez vous faire “”"”plaisir”””” à le visualiser avec les fonctions décrites à la fin de cet article.

En convertissant cette solution en grille complète de sudoku, on obtient :

[
	[8, 2, 4, 9, 5, 3, 6, 7, 1], 
	[6, 3, 5, 8, 1, 7, 9, 2, 4], 
	[7, 1, 9, 6, 2, 4, 8, 5, 3], 
	[5, 8, 7, 2, 9, 1, 3, 4, 6], 
	[1, 4, 2, 7, 3, 6, 5, 8, 9], 
	[3, 9, 6, 4, 8, 5, 2, 1, 7], 
	[2, 6, 1, 5, 4, 9, 7, 3, 8], 
	[4, 7, 8, 3, 6, 2, 1, 9, 5], 
	[9, 5, 3, 1, 7, 8, 4, 6, 2]
]

La fonction suivante en Python peut tester si cette solution respecte les règles du sudoku à notre place :

# On teste si une liste a des répétitions
# en testant si la longueur de la liste
# en entrée est égale à la longueur de la
# la liste dans laquelle on a supprimé 
# toutes les répétitions
def est_unique(liste):
	sans_repetitions = list(set(liste))
	return(len(liste) == len(sans_repetitions))

# On teste si la solution respecte les 
# règles du grille
# On suppose que toutes les valeurs de la grille
# sont comprises entre 1 et 9
def tester_solution(grille):
	nb_lignes = len(grille)
	# Toutes les lignes ont la même longueur
	nb_colonnes = len(grille[0])
	nb_sous_grilles = len(grille)
	# ex. 9 pour une grille de taille 9 x 9
	colonnes = []
	for j in range(nb_colonnes):
		colonne = []
		# On met dans la même colonne 
		# tous les éléments à la position j
		# dans chaque ligne
		for i in range(nb_lignes):
			colonne.append(grille[i][j])
		# On ajoute la colonne à la liste des colonnes
		colonnes += [colonne]
	# Construire les sous-grilles de taille (racine carré de la 
	# taille de la grille initiale), qu'on note r
	# La sous-grille qui commence à la ligne i 
	# et la colonne j (le coefficient en haut à gauche est
	# la position (i,j)) comporte les coefficients
	# aux positions (i, j), (i, j+1), (i, j+2), ..., (i, j+r-1)
	# (i+1, j), (i+1, j+1), (i+1, j+2), ..., (i+1, j+r-1)
	# (i+2, j), (i+2, j+1), (i+2, j+2), ..., (i+2, j+r-1)
	# ...
	# (i+r-1, j), ..., (i+r-1, j+r-1)
	# Attention à l'indexage en Python qui commence à zéro !
	sous_grilles = []
	from math import sqrt
	r = int(sqrt(len(grille)))
	indices_depart = [r*i for i in range(r)]
	for i in indices_depart:
		for j in indices_depart:
			# Le coefficient de départ est (i, j)
			sous_grille = []
			for k in [i+ui for ui in range(r)]:
				for l in [j+uj for uj in range(r)]:
					sous_grille.append(grille[k][l])
			sous_grilles += [sous_grille]
	# pour chaque ligne, on teste
	# s'il y a des répétitions
	for i in range(nb_lignes):
		if (not est_unique(grille[i])):
			return(False)
	# pour chaque colonne
	for i in range(nb_colonnes):
		if (not est_unique(colonnes[i])):
			return(False)
	# pour chaque sous-grille
	for i in range(nb_sous_grilles):
		if (not est_unique(sous_grilles[i])):
			return(False)
	# Sinon, toutes les conditions ont été remplies
	return(True)
tester_solution(grille)
> True

Pour aller plus loin

Comment est-on sûrs que l’algorithme (celui avec le backtracking) termine ? En fait, on énumère des “chemins”, où l’étape n est la couleur sélectionnée pour le nième noeud observé (dans cet algorithme, on inspecte les noeuds de gauche à droite, de haut en bas dans la grille). Le tableau “couleurs_disponibles” calculé pour chaque noeud observé donne les possibilités à explorer pour l’étape associée (comme un embranchement pour un véritable chemin). A chaque backtracking, on élimine une possibilité (on a exploré cette direction dans l’embranchement, et elle nous a mené à une impasse). Au final, on énumère les chemins possibles, jusqu’à trouver celui qui nous permet de trouver une solution pour chaque étape -ou alors, on a fini par explorer tous les chemins possibles, et aucun n’a abouti (le cas “Insoluble” dans l’algorithme).

Bon, je vous ai donné la solution sans trop me justifier. Ce serait bien de vérifier qu’effectivement, il est utile de chercher à résoudre le problème de coloriage de graphe pour faire des sudokus. En fait, le problème de sudoku, et ce problème de coloriage de graphe sont équivalents; autrement dit, si on trouve la solution pour une instance concrète de l’un de ces deux problèmes, on peut la convertir en solution de l’autre problème, après transformation de l’instance du premier problème en instance du second problème (par exemple, en convertissant la grille de sudoku en graphe) :

En gage de bonne foi, voilà le code Python correspondant à ces transformations :

# Créer le graphe et produire une image PNG
# en utilisant GraphViz, que vous pouvez aussi voir
# dans la boîte à outils de Tryalgo
# (http://tryalgo.org/toolbox/)
def construire_graphe(grille):
	from subprocess import call
	couleurs_cases = couleurs[:len(grille)+1] 
	filename="sudoku" + str(len(grille))*2
	sudoku = "graph {\n"
	# Dimension de la grille
	n = len(grille)
	# Liste de noms et couleurs de noeuds
	noeuds = []
	# Le coefficient d'indice (i, j) est à la position n*i+j
	# dans la liste noeuds
	for i in range(n):
		for j in range(n):
			nom = "\"(" + str(i+1) + ", " + str(j+1) + ")\""
			couleur = couleurs_cases[grille[i][j]]
			noeuds.append([nom, couleur])
			# Ajouter le noeud au fichier DOT
			sudoku += "node [style=filled fillcolor=" + couleur
			sudoku += " shape=circle]\n"
			sudoku += nom + ";\n"
	# Matrice d'adjacence pour le graphe
	# aretes[i][j] = True si et seulement si le noeud i
	# et le noeud j sont voisins
	aretes = [[False]*(n*n) for j in range(n*n)]
	for i in range(n):
		for j in range(n):
			for k in range(n):
				# Voisinage par ligne
				aretes[n*i+j][n*i+k] = True
				# Voisinage par colonne
				aretes[n*i+j][n*k+j] = True
			# Voisinage par sous-grille
			# Remarquer que toutes les positions de 
			# coefficients d'une même sous-grille 
			# (numéros de ligne et de colonne)
			# ont le même quotient q pour la division 
			# euclidienne par r, où r est 
			# la racine carré de la taille de la
			# grille initiale
			# (voir le commentaire de la fonction
			# est_unique)
			from math import sqrt
			r = int(sqrt(n))
			# Valeurs de quotient
			q_i, q_j = int(i/r), int(j/r)
			# On énumère les valeurs possibles de reste
			# 0, 1, 2, ..., r-1
			for reste_i in range(r):
				for reste_j in range(r):
					# Enumérer les coordonnées de noeuds (ii, jj)
					ii = r*q_i+reste_i
					jj = r*q_j+reste_j
					aretes[n*i+j][n*ii+jj] = True
	# On ne met pas de boucle élémentaire
	# autrement dit, d'arête d'un noeud vers lui-même
	for i in range(n*n):
		# Pour éviter de mettre une boucle élémentaire
		# et parce que la matrice d'adjacence est ici symétrique
		# (le graphe est non orienté)
		for j in range(i+1, n*n):
			if (aretes[i][j]):
				sudoku += noeuds[i][0] + " -- " + noeuds[j][0] + ";\n"
		aretes[i][i] = False
	graphe = [noeuds, aretes]
	sudoku += "}"
	# On crée le fichier DOT associé au graphe
	with open(filename+".dot", "w") as f:
		f.write(sudoku)
	# Conversion du fichier DOT en image PNG
	call("dot -Tpng " + filename + ".dot > " + filename + ".png", shell=True)
	return(graphe)

def reconstruire_grille(graphe):
	noeuds, aretes = graphe
	from math import sqrt
	# On a n^2 cases, où n est la taille de la grille
	n = int(sqrt(len(noeuds)))
	grille = []
	for i in range(n):
		ligne = []
		for j in range(n):
			couleur = noeuds[n*i+j][1]
			# Retrouve l'indice de l'élément couleur
			# dans le tableau couleurs
			valeur = couleurs.index(couleur)
			ligne.append(valeur)
		# On met la ième ligne dans la grille
		grille += [ligne]
	return(grille)

Référence (en anglais)

“Sudoku Game Solution Using Graph Coloring” de Bharathi Dharavath

Commentaires