Modélisation en Python du jeu du Sudoku

Nous allons utiliser une modélisation du jeu du Sudoku utilisant un graphe coloré.

Structure de données modélisant une grille de Sudoku

La grille du jeu peut être représentée par une matrice carrée en Python :

• Une matrice 9x9 pour le Sudoku classique ;

• Une matrice 4x4 pour le mini-Sudoku ;

• Une matrice 16x16 pour le méga-Sudoku;

Exemple :

La grille du mini-Sudoku présentée ci-dessus peut être représentée par la liste suivante :

Remarque :

Les cases vides sont "codées" par le chiffre 0.

Vérification d'une grille de Sudoku

Ecrire une fonction nommée verifie_grille_Sudoku(grille) qui retourne :

• Retourne 1 si la grille grille est complète (sans 0) et respecte les contraintes du jeu (unicité de chaque chiffre resource chaque ligne, sur chaque colonne sur chaque sous-grille)

• Retourne -1 si la grille grille est complète (sans 0) et ne respecte pas les contraintes du jeu (unicité de chaque chiffre sur chaque ligne, sur chaque colonne sur chaque sous-grille)

• Retourne 0 si la grille grille est incomplète (avec un ou plusieurs 0) et respecte les contraintes du jeu (unicité de chaque chiffre sur chaque ligne, sur chaque colonne sur chaque sous-grille)

grille est une matrice carrée de taille 4x4 ou 9x9 ou 16x16 qui représente la grille de Sudoku (éventuellement incomplète).

grille[i][j] contient la valeur de la case de la grille de Sudoku à l'intersection de la ligne i + 1 et de la colonne j + 1.

Modélisation d'une grille de Sudoku avec un graphe

On peut modéliser une grille de Sudoku avec un graphe défini comme suit :

• Les sommets du graphe sont les cases de la grille.

  Pour un Sudoku classique le nombre de sommets est $9 \times 9 = 81$.

  Pour un mini-Sudoku le nombre de sommets est $4 \times 4 = 16$.

  Pour un méga-Sudoku le nombre de sommets est $16 \times 16 = 256$.

• Les arêtes représentent les contraintes d'une grille de Sudoku.

  Exemple : Pour une grille de mini-Sudoku, le sommet repésenté en rouge (à l'intersection de la ligne 3 et de la colonne 2) est lié à tous les sommets en bleus.

  

  C'est à dire à tous les sommets sur la même ligne que lui, sur la même colonne que lui et dans la même sous-grille que lui.

  Le graphe avec tous les sommets et toutes les arêtes pour une grille de Mini-Sudoku est le suivant :

  

Structure de données pour représenter le graphe associé à une grille de Sudoku

Il est possible d'utiliser un dictionnaire représentant la liste d'adjacence associée au graphe.

Les clefs du dictionnaire sont les sommets du graphe.

On peut réprésenter chaque sommet par un tuple du type (ligne,colonne) déterminant la ligne et la colonne de la case de la grille du associé au sommet.

Les valeurs du dictionnaire sont la liste des voisins d'un sommet donné.

Exemple :

Le dictionnaire ainsi défini pour une grille de Mini-Sudoku est le suivant :

{
	(1, 1): [(1, 2), (1, 3), (1, 4), (2, 1), (3, 1), (4, 1), (2, 2)],
	(1, 2): [(1, 1), (1, 3), (1, 4), (2, 2), (3, 2), (4, 2), (2, 1)],
	(1, 3): [(1, 1), (1, 2), (1, 4), (2, 3), (3, 3), (4, 3), (2, 4)],
	(2, 1): [(2, 2), (2, 3), (2, 4), (1, 1), (3, 1), (4, 1), (1, 2)],
	(2, 2): [(2, 1), (2, 3), (2, 4), (1, 2), (3, 2), (4, 2), (1, 1)],
	(2, 3): [(2, 1), (2, 2), (2, 4), (1, 3), (3, 3), (4, 3), (1, 4)],
	(2, 4): [(2, 1), (2, 2), (2, 3), (1, 4), (3, 4), (4, 4), (1, 3)],
	(3, 1): [(3, 2), (3, 3), (3, 4), (1, 1), (2, 1), (4, 1), (4, 2)],
	(3, 2): [(3, 1), (3, 3), (3, 4), (1, 2), (2, 2), (4, 2), (4, 1)],
	(3, 3): [(3, 1), (3, 2), (3, 4), (1, 3), (2, 3), (4, 3), (4, 4)],
	(3, 4): [(3, 1), (3, 2), (3, 3), (1, 4), (2, 4), (4, 4), (4, 3)],
	(4, 1): [(4, 2), (4, 3), (4, 4), (1, 1), (2, 1), (3, 1), (3, 2)],
	(4, 2): [(4, 1), (4, 3), (4, 4), (1, 2), (2, 2), (3, 2), (3, 1)],
	(4, 4): [(4, 1), (4, 2), (4, 3), (1, 4), (2, 4), (3, 4), (3, 3)]
}
		

Ecrire une fonction nommée construit_graphe_Sudoku(taille) qui construit et retourne le dictionnaire représentant le graphe d'une grille de Sudoku de taille taille.

• taille = 2 correspond au mini-Sudoku (grille carrée de dimension $2 \ times 2 = 4$).

• taille = 3 correspond au Sudoku classique (grille carrée de dimension $3 \ times 3 = 9$).

• taille = 4 correspond au méga-Sudoku (grille carrée de dimension $4 \ times 4 = 16$).

Donner pour chaque dictionnaire associé au mini-Sudoku, au Sudoku classique et au méga-Sudoku l'ordre et le nombre d'arêtes du graphe associé.

Résolution d'une grille de Sudoku incomplète avec un algorithme de coloration de graphe

La coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente.

On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique.

Exemple : une coloration du graphe de Petersen avec 3 couleurs.

Application de la coloration d'un graphe à la résolution d'une grille de Sudoku

La couleur ici sera le nombre contenu dans la case relative au sommet du graphe.

Il existe plusieurs algorithmes gloutons de coloration de graphes (qui ne fournissent pas nécessairement une coloration avec un nombre minimale de couleurs).

On peut citer les algorithmes Welsh & Powell et DSATUR qui sont sont basés sur une coloration séquentielle du graphe en visitant les sommets par ordre de degré décroissant.

Présentation des principales étapes d'un algorithme possible de coloration du graphe lié à une grille de Sudoku

Voici les étapes principales de cet algorithme récursif :

1. S'il ne reste pas de cases vides dans la grille, retourner le graphe coloré complet.

2. Sinon, déterminer le sommet qui a un maximum de nombres impossibles (ou un minimum de nombres possibles) noté sommet_maxparmi les sommets corrrespondants à une case vide.

3. A partir de la liste des voisins de sommet_max, construire la liste des couleurs possibles que l'on peut attribuer à ce sommet.

4. Attribuer successivement chacune des couleurs possibles à sommet_max.

5. Par un appel récursif retourner à l'étape 1.

Ecrire une fonction nommée colorie_graphe(graphe_colore) qui applique l'algorithme décrit ci-dessus.

Remarque :

Le paramètre graphe_colore est un dictionnaire représentant un graphe lié à une grille de Sudoku partiellement coloré (la couleur d'un sommet est le nombre d'une case remplie de la grille ou 0 si la case est vide).

Les clefs de ce dictionnaire sont les sommets représentés par un tuple (ligne,colonne)

Les valeurs sont aussi un tuple du type couleur,liste_voisins.

Exemple : le dictionnaire ainsi défini du graphe coloré correspondant à cette grille :

est :

{
	(1, 1): [0, [(1, 2), (1, 3), (1, 4), (2, 1), (3, 1), (4, 1), (2, 2)]],
	(1, 2): [0, [(1, 1), (1, 3), (1, 4), (2, 2), (3, 2), (4, 2), (2, 1)]],
	(1, 3): [0, [(1, 1), (1, 2), (1, 4), (2, 3), (3, 3), (4, 3), (2, 4)]],
	(1, 4): [0, [(1, 1), (1, 2), (1, 3), (2, 4), (3, 4), (4, 4), (2, 3)]],
	(2, 1): [1, [(2, 2), (2, 3), (2, 4), (1, 1), (3, 1), (4, 1), (1, 2)]],
	(2, 2): [0, [(2, 1), (2, 3), (2, 4), (1, 2), (3, 2), (4, 2), (1, 1)]],
	(2, 3): [3, [(2, 1), (2, 2), (2, 4), (1, 3), (3, 3), (4, 3), (1, 4)]],
	(2, 4): [0, [(2, 1), (2, 2), (2, 3), (1, 4), (3, 4), (4, 4), (1, 3)]],
	(3, 1): [4, [(3, 2), (3, 3), (3, 4), (1, 1), (2, 1), (4, 1), (4, 2)]],
	(3, 2): [3, [(3, 1), (3, 3), (3, 4), (1, 2), (2, 2), (4, 2), (4, 1)]],
	(3, 3): [1, [(3, 1), (3, 2), (3, 4), (1, 3), (2, 3), (4, 3), (4, 4)]],
	(3, 4): [0, [(3, 1), (3, 2), (3, 3), (1, 4), (2, 4), (4, 4), (4, 3)]],
	(4, 1): [2, [(4, 2), (4, 3), (4, 4), (1, 1), (2, 1), (3, 1), (3, 2)]],
	(4, 2): [0, [(4, 1), (4, 3), (4, 4), (1, 2), (2, 2), (3, 2), (3, 1)]],
	(4, 3): [0, [(4, 1), (4, 2), (4, 4), (1, 3), (2, 3), (3, 3), (3, 4)]],
	(4, 4): [0, [(4, 1), (4, 2), (4, 3), (1, 4), (2, 4), (3, 4), (3, 3)]]
}
		

Résolution de grilles de Sudoku

Voici un scénario d'utilisation des fonctions python développées dans ce projet pour résoudre une grille de Sudoku.

1. Choisir une grille de Sudoku incomplète (de type mini , classique ou méga) ;

   Vous pouvez utiliser ce fichier pour des exemples de grilles à tester (avec des niveaux différents : Facile, moyen, difficile ou diabolique).

2. Vérifier si cette grille est valide (à l'aide de la fonction verifie_grille_Sudoku(grille)) ;

3. Si la grille est valide, générer le graphe (non coloré) associé à la grille de Sudoku traitée selon sa taille (construit_graphe_Sudoku(taille));

4. Appliquer l'algorithme de coloration du graphe pour résoudre la grille de Sudoku (colorie_graphe(graphe_colore));

Mettre en place ce scénario de résolution de grilles de Sudoku.

Quelles remarques peut-on faire sur la complexité algorithmique de la fonction colorie_graphe(graphe_colore) selon la taille de la grille (4x4, 9x9 ou 16x16) et le niveau de difficulté ?

Pour aller plus loin

Affichage d'une grille de Sudoku avec une interface graphique

En utilisant un gestionnaire d'interface graphique (TKinter, Processing Python ou Pygame), écrire une fonction nommée dessine_grille(grille) qui permet d'afficher une grille de Sudoku dans une fenêtre.

Exemple de grille affichée (avec Pygame)

Affichage des graphes (non coloré et coloré) associés à la grille de Sudoku à l'aide de la bibliothèque GraphViz

Cette bibliothèque permet de génerer des fichiers textes au format dot.

Il est possible de visualiser un fichier dot en ligne via ce site viz-js.com.

Visualisation des graphes non colorés (associés à une grille de Sudoku vierge)

Ecrire une fonction nommée genere_fichier_dot(graphe, nom_fichier, engine='dot') qui génère un fichier texte au format dotnommé nom_fichier représentant le graphe graphe à l'aide de la bibliothèque Python Graphviz.

Exemples de rendus possible pour une grille de mini-Sudoku :

fichier dot

Exemple de rendu possible pour une grille de Sudoku classique :

fichier dot

Visualisation des graphes colorés (associés à une grille de Sudoku résolue)

Ecrire une fonction nommée genere_fichier_dot_graphe_colore_clusters(grille, graphe, nom_fichier) qui génère un fichier au format dot nommé nom_fichier représentant le graphe coloré graphe à l'aide de la bibliothèque Python Graphviz.

En utilisant le rendu engine = "osage", sans générer les arêtes du graphe et en utilisant des clusters / sous-graphes, il est possible d'obtenir un rendu respectant une présentation similaire à la grille du Sudoku.

Exemple d'une grille de mini-Sudoku résolue :

Fichier dot associé

Exemple d'une grille de Sudoku classique résolue :

Exemple d'une grille de méga-Sudoku classique résolue :

Auteur : Hugues Malherbe