Navigation : << Human Stratégies | Index | OR-Tools >>
A la fin de ce notebook, vous saurez :
Duree estimee : ~15 min | Prerequis : Sudoku-00 Environment
Ce notebook implemente des solveurs de Sudoku utilisant la coloration de graphe, une approche classique de la théorie des graphes.
Le Sudoku peut etre modelise comme un problème de coloration de graphe :
# Configuration du chemin vers les puzzles
from pathlib import Path
NOTEBOOK_DIR = Path.cwd()
PUZZLES_DIR = NOTEBOOK_DIR / "Puzzles"
def load_puzzles(filepath: str, max_puzzles: int = None) -> List[str]:
puzzles = []
with open(filepath, "r") as f:
for line in f:
line = line.strip()
if len(line) >= 81:
puzzles.append(line[:81])
if max_puzzles and len(puzzles) >= max_puzzles:
break
return puzzles
easy_puzzles = load_puzzles(str(PUZZLES_DIR / "Sudoku_Easy51.txt"), max_puzzles=10)
print(f"Puzzles charges: {len(easy_puzzles)} faciles")Puzzles charges: 10 facilesNetworkX fournit nx.sudoku_graph() qui genere automatiquement le graphe de contraintes Sudoku !
# Créer le graphe Sudoku avec NetworkX
G = nx.sudoku_graph()
print("=== Statistiques du Graphe Sudoku ===")
print(f"Sommets: {G.number_of_nodes()}")
print(f"Aretes: {G.number_of_edges()}")
# Verifier que c'est un graphe regulier
degrees = [d for n, d in G.degree()]
print(f"Degré min: {min(degrees)}, max: {max(degrees)}")
print(f"Graphe regulier: {len(set(degrees)) == 1}")=== Statistiques du Graphe Sudoku ===
Sommets: 81
Aretes: 810
Degré min: 20, max: 20
Graphe regulier: TrueNetworkX a genere automatiquement :
Chaque sommet represente une cellule, et les aretes representent les contraintes d’exclusion.
Dans le graphe de contraintes du Sudoku, chaque arete represente une exclusion mutuelle entre deux cellules. Les cellules les plus contraintes (celles qui ont le plus de voisins non encore resolus) sont les plus difficiles a remplir.
Implementez count_unassigned_constraints(coloring, G) qui retourne un dictionnaire {vertex: count} indiquant, pour chaque cellule non coloriee, combien de ses voisins sont également non colories.
Indices :
coloring[v] == 0)# EXERCICE : Compter les contraintes par cellule
#
# Indications :
# - Identifiez les sommets non colories (coloring[v] == 0)
# - Pour chaque sommet non colorie, comptez ses voisins non colories
# - Retournez le dictionnaire trie par contraintes decroissantes
def count_unassigned_constraints(coloring: list, G) -> dict:
"""Compte les voisins non colories pour chaque cellule non coloriee.
Args:
coloring: liste de 81 entiers (0=non colorie)
G: graphe NetworkX des contraintes
Returns:
Dictionnaire {vertex: count} trie par count decroissant
"""
# TODO etudiant : implementez le comptage des contraintes
return {}
# Test rapide avec un coloring partiel (grille facile, quelques indices)
# 0 = case vide, 1-9 = chiffre attribue
test_coloring = [0]*81
# Quelques valeurs pre-remplies (ligne 0: 4,_,3,_,2,_,6,_,7)
for i, v in enumerate([4,0,3,0,2,0,6,0,7]):
test_coloring[i] = v
constraints = count_unassigned_constraints(test_coloring, G)
print(f"Nombre de cellules non colories : {len(constraints)}")
if constraints:
top = list(constraints.items())[:3]
print(f"Top 3 cellules les plus contraintes : {top}")Nombre de cellules non colories : 0class SudokuGrid:
"""Representation d'une grille de Sudoku 9x9."""
def __init__(self, grid: Optional[List[List[int]]] = None):
if grid is None:
self.cells = [[0] * 9 for _ in range(9)]
else:
self.cells = [row[:] for row in grid]
@classmethod
def from_string(cls, s: str) -> "SudokuGrid":
s = s.replace(".", "0").replace(" ", "").replace("\n", "")
if len(s) != 81:
raise ValueError("La chaîne doit avoir 81 caractères")
grid = cls()
for i in range(81):
grid.cells[i // 9][i % 9] = int(s[i])
return grid
def to_coloring(self) -> List[int]:
"""Convertit la grille en coloration de graphe."""
coloring = [0] * 81
for row in range(9):
for col in range(9):
coloring[row * 9 + col] = self.cells[row][col]
return coloring
def from_coloring(self, coloring: List[int]) -> "SudokuGrid":
"""Met a jour la grille depuis une coloration."""
for v in range(81):
row, col = v // 9, v % 9
self.cells[row][col] = coloring[v]
return self
def __str__(self) -> str:
lines = []
for r in range(9):
if r > 0 and r % 3 == 0:
lines.append("-" * 21)
row_str = ""
for c in range(9):
if c > 0 and c % 3 == 0:
row_str += "| "
val = self.cells[r][c]
row_str += (str(val) if val != 0 else ".") + " "
lines.append(row_str)
return "\n".join(lines)
# Test
test_grid = SudokuGrid.from_string(easy_puzzles[0])
print("Puzzle facile:")
print(test_grid)Puzzle facile:
9 . 2 | . . 5 | 4 . 3
1 . . | . 6 3 | . 2 5
5 . 8 | 4 . 7 | . 6 .
---------------------
. 2 6 | 3 . 9 | . . 1
. 5 7 | . 1 . | 2 9 .
. 9 . | 6 7 . | 5 3 .
---------------------
2 4 . | 5 3 . | 6 . .
7 . 5 | 2 . . | 3 . 4
. 8 . | . 4 1 | 9 5 . Nous utilisons le graphe NetworkX pour guider le backtracking avec l’heuristique MRV (Minimum Remaining Values).
def solve_with_mrv_backtracking(grid: SudokuGrid) -> Tuple[bool, int, int]:
"""
Resout le Sudoku avec backtracking + heuristique MRV.
Returns:
(success, nodes_explored, backtracks)
"""
G = nx.sudoku_graph()
coloring = grid.to_coloring()
nodes_explored = 0
backtracks = 0
def get_available_colors(vertex: int, coloring: List[int]) -> set:
used = set()
for neighbor in G.neighbors(vertex):
if coloring[neighbor] != 0:
used.add(coloring[neighbor])
return set(range(1, 10)) - used
def select_mrv_vertex(coloring: List[int]) -> Optional[int]:
best_vertex = None
min_colors = 10
for v in range(81):
if coloring[v] != 0:
continue
available = get_available_colors(v, coloring)
if len(available) < min_colors:
min_colors = len(available)
best_vertex = v
return best_vertex
def backtrack(coloring: List[int]) -> bool:
nonlocal nodes_explored, backtracks
nodes_explored += 1
vertex = select_mrv_vertex(coloring)
if vertex is None:
return True
for color in get_available_colors(vertex, coloring):
coloring[vertex] = color
if backtrack(coloring):
return True
coloring[vertex] = 0
backtracks += 1
return False
success = backtrack(coloring)
grid.from_coloring(coloring)
return success, nodes_explored, backtracks
# Test
test_grid = SudokuGrid.from_string(easy_puzzles[0])
print("Puzzle a resoudre:")
print(test_grid)
start = time.time()
success, nodes, bts = solve_with_mrv_backtracking(test_grid)
elapsed = (time.time() - start) * 1000
print(f"\nResolu: {success} en {elapsed:.2f} ms")
print(f"Noeuds explores: {nodes}")
print(f"Backtracks: {bts}")
print("\nSolution:")
print(test_grid)Puzzle a resoudre:
9 . 2 | . . 5 | 4 . 3
1 . . | . 6 3 | . 2 5
5 . 8 | 4 . 7 | . 6 .
---------------------
. 2 6 | 3 . 9 | . . 1
. 5 7 | . 1 . | 2 9 .
. 9 . | 6 7 . | 5 3 .
---------------------
2 4 . | 5 3 . | 6 . .
7 . 5 | 2 . . | 3 . 4
. 8 . | . 4 1 | 9 5 .
Resolu: True en 2.15 ms
Noeuds explores: 37
Backtracks: 0
Solution:
9 6 2 | 1 8 5 | 4 7 3
1 7 4 | 9 6 3 | 8 2 5
5 3 8 | 4 2 7 | 1 6 9
---------------------
8 2 6 | 3 5 9 | 7 4 1
3 5 7 | 8 1 4 | 2 9 6
4 9 1 | 6 7 2 | 5 3 8
---------------------
2 4 9 | 5 3 8 | 6 1 7
7 1 5 | 2 9 6 | 3 8 4
6 8 3 | 7 4 1 | 9 5 2 Le solveur a resolu un puzzle facile en 1.88 ms avec seulement 37 noeuds explores et 0 backtracks.
| Aspect | Valeur | Signification |
|---|---|---|
| Temps | 1.88 ms | Resolution très rapide |
| Noeuds explores | 37 | MRV reduit l’espace de recherche |
| Backtracks | 0 | Pas d’erreurs necessaires |
Points cles : 1. MRV fonctionne très bien : La heuristique choisit les cases les plus contraintes 2. NetworkX simplifie le code : Plus besoin de gerer manuellement les voisins 3. Graphe regulier : Tous les sommets ont degré 20, donc MRV se base sur les domaines
Note technique : L’heuristique MRV (Minimum Remaining Values) est particulierement efficace sur Sudoku car les contraintes locales (ligne, colonne, bloc) reduisent rapidement les domaines des cases voisines.
L’heuristique MRV choisit le sommet avec le moins de couleurs disponibles. Mais quand plusieurs sommets ont le même nombre de couleurs possibles (egalite MRV), l’heuristique de degré les departage en choisissant celui qui a le plus de voisins non colories. Ce sommet est le plus contraignant, donc le colorier en premier reduit l’arbre de recherche.
Implementez select_unassigned_vertex(coloring, G) qui combine MRV + degré.
Indices :
coloring[v] == 0)# EXERCICE : Heuristique de degré (MRV + Degree)
#
# Indications :
# - Collectez les sommets non colories (coloring[v] == 0)
# - Pour chacun, calculez les couleurs disponibles (couleurs des voisins déjà prises)
# - Trouvez le minimum de couleurs (MRV)
# - En cas d egalite, choisissez le sommet avec le plus de voisins non colories
def select_unassigned_vertex(coloring: list, G) -> int:
"""Selectionne le prochain sommet a colorier avec MRV + degré.
Args:
coloring: liste de 81 entiers (0=non colorie)
G: graphe NetworkX des contraintes
Returns:
Index du sommet a colorier, ou -1 si tous sont colories
"""
# TODO etudiant : implementez MRV + degree heuristic
return -1
# Test rapide avec une grille partiellement remplie
test_coloring_dh = [0]*81
for i, v in enumerate([4,0,3,0,2,0,6,0,7]):
test_coloring_dh[i] = v
vertex = select_unassigned_vertex(test_coloring_dh, G)
print(f"Prochain sommet a colorier : {vertex}")Prochain sommet a colorier : -1def benchmark(puzzles: List[str], name: str, limit: int = 5):
"""Benchmark de solveur MRV."""
print(f"\nBenchmark: {name} ({min(limit, len(puzzles))} puzzles)")
results = []
for puzzle_str in puzzles[:limit]:
grid = SudokuGrid.from_string(puzzle_str)
start = time.time()
success, nodes, bts = solve_with_mrv_backtracking(grid)
elapsed = (time.time() - start) * 1000
results.append({"success": success, "time_ms": elapsed, "nodes": nodes, "backtracks": bts})
solved = [r for r in results if r["success"]]
if solved:
avg_time = sum(r["time_ms"] for r in solved) / len(solved)
print(f"Succes: {len(solved)}/{len(results)}")
print(f"Temps moyen: {avg_time:.2f} ms")
else:
print("Aucun puzzle resolu !")
return results
benchmark(easy_puzzles, "Puzzles Faciles", limit=3)
hard_puzzles = load_puzzles(str(PUZZLES_DIR / "Sudoku_hardest.txt"))
benchmark(hard_puzzles, "Puzzles Difficiles", limit=2)
Benchmark: Puzzles Faciles (3 puzzles)
Succes: 3/3
Temps moyen: 3.68 ms
Benchmark: Puzzles Difficiles (2 puzzles)
Succes: 2/2
Temps moyen: 45.95 ms[{'success': True,
'time_ms': 9.479761123657227,
'nodes': 164,
'backtracks': 104},
{'success': True,
'time_ms': 82.42917060852051,
'nodes': 1496,
'backtracks': 1437}]Les résultats montrent que l’approche coloration de graphe est efficace mais moins optimale que les solveurs CSP dedies.
| Type | Temps moyen | Analyse |
|---|---|---|
| Puzzles faciles | ~2.5 ms | Performance correcte |
| Puzzles difficiles | ~47 ms | Beaucoup plus lent (notez les backtracks) |
Comparaison avec d’autres approches : - OR-Tools CP-SAT : nettement plus rapide pour les difficiles (voir Sudoku-10) - Backtracking simple : Plusieurs secondes pour les difficiles - NetworkX : Bon compromis simplicite/performance
Points cles : 1. NetworkX n’a pas de solveur integre : Nous devons implementer le backtracking 2. L’avantage est la flexibilite : Facile d’experimentation avec d’autres algorithmes de coloration 3. Graphe regulier : Le degré constant (20) aide a comprendre la structure
Note technique : La coloration de graphe est un problème NP-complet. Le Sudoku est un cas particulier avec une structure très reguliere, ce qui permet des optimisations spécifiques que NetworkX n’exploite pas.
Avant d’accepter une solution de Sudoku, il est essentiel de verifier que la coloration obtenue est une coloration propre du graphe de contraintes : deux sommets adjacents ne doivent pas partager la même couleur.
Implementez la fonction is_valid_coloring(coloring, G) qui verifie cette propriete sur l’ensemble du graphe.
Indices :
G.edges()(u, v), verifiez que coloring[u] != coloring[v]True si la coloration est propre et complete, False sinon# EXERCICE : Verification d'une coloration valide
#
# Indications :
# - Parcourez toutes les aretes avec G.edges()
# - Pour chaque arete (u, v), verifiez coloring[u] != coloring[v]
# - Verifiez qu aucun sommet n a la couleur 0
# - Retournez True si la coloration est propre et complete
def is_valid_coloring(coloring: list, G) -> bool:
"""Verifie qu une coloration est propre (pas de conflits) et complete.
Args:
coloring: liste de 81 entiers (0=non colorie, 1-9=couleur)
G: graphe NetworkX des contraintes Sudoku
Returns:
True si la coloration est propre et complete, False sinon
"""
# TODO etudiant : implementez la verification de coloration
return False
# Test rapide sur une grille resolue
test_gc = SudokuGrid.from_string('..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..')
success, _, _ = solve_with_mrv_backtracking(test_gc)
if success:
coloring = test_gc.to_coloring()
print(f"Coloration valide : {is_valid_coloring(coloring, nx.sudoku_graph())}")
else:
print("Pas de solution")Coloration valide : FalseL’heuristique LCV (Least Constraining Value) complete MRV en optimisant l’ordre des couleurs : a chaque étape, choisir la couleur qui reduit le moins les domaines des sommets voisins.
count_remaining_options(vertex, color, coloring, G) : calcule combien d’options restent pour les voisins non colories si on assigne color au sommet vertexsolve_with_lcv(grid) : solveur complet combinant MRV pour le choix du sommet et LCV pour l’ordre des couleursLCV peut ralentir la recherche (calcul couteux) mais reduit les backtracks sur les puzzles difficiles en maintenant les domaines des voisins plus ouverts.
def get_available_colors(vertex: int, coloring: List[int]) -> set:
used = set()
for neighbor in G.neighbors(vertex):
if coloring[neighbor] != 0:
used.add(coloring[neighbor])
return set(range(1, 10)) - used
def count_remaining_options(vertex: int, color: int, coloring: list, G) -> int:
"""
Compte le nombre total d'options restantes pour les voisins non colories
si on assigne `color` au sommet `vertex`.
Plus le nombre est eleve, moins la couleur est contraignante (LCV).
"""
# 1. Temporairement assigner `color` au sommet `vertex`
# 2. Pour chaque voisin non colorie du sommet `vertex` :
# - Calculer le nombre de couleurs disponibles pour ce voisin
# - Ajouter au total
# 3. Annuler l'assignation temporaire
# 4. Retourner le total
total = 0
# 1
coloring[vertex] = color
# 2
for neighbor in G.neighbors(vertex):
if coloring[neighbor] == 0:
total += len(get_available_colors(neighbor, coloring))
# 3
coloring[vertex] = 0
# 4
return total
def solve_with_lcv(grid: SudokuGrid) -> tuple:
"""
Resout le Sudoku avec backtracking + MRV pour le sommet + LCV pour l'ordre des couleurs.
Retourne (success, nodes_explored, backtracks).
"""
# Reprendre solve_with_mrv_backtracking et modifier l'ordre des couleurs :
# - Pour chaque sommet selectionne par MRV,
# - Trier les couleurs disponibles par count_remaining_options decroissant (LCV)
# - Essayer les couleurs dans cet ordre
G = nx.sudoku_graph()
coloring = grid.to_coloring()
nodes_explored = 0
backtracks = 0
def select_mrv_vertex(coloring: List[int]) -> Optional[int]:
best_vertex = None
min_colors = 10
for v in range(81):
if coloring[v] != 0:
continue
available = get_available_colors(v, coloring)
if len(available) < min_colors:
min_colors = len(available)
best_vertex = v
return best_vertex
def backtrack(coloring: List[int]) -> bool:
nonlocal nodes_explored, backtracks
nodes_explored += 1
vertex = select_mrv_vertex(coloring)
if vertex is None:
return True
available_colors = get_available_colors(vertex, coloring)
remaining_options = [count_remaining_options(vertex, color, coloring, G) for color in available_colors]
sorted_pairs = sorted(zip(remaining_options, available_colors), reverse=True)
sorted_colors = [pair[1] for pair in sorted_pairs]
for color in sorted_colors:
coloring[vertex] = color
if backtrack(coloring):
return True
coloring[vertex] = 0
backtracks += 1
return False
success = backtrack(coloring)
grid.from_coloring(coloring)
return success, nodes_explored, backtracks
# Test comparatif LCV vs MRV pur
grid_test = SudokuGrid.from_string(hard_puzzles[0])
success, nodes, bts = solve_with_lcv(grid_test)
print(f"LCV - Noeuds: {nodes}, Backtracks: {bts}")
grid_test2 = SudokuGrid.from_string(hard_puzzles[0])
success2, nodes2, bts2 = solve_with_mrv_backtracking(grid_test2)
print(f"MRV pur - Noeuds: {nodes2}, Backtracks: {bts2}")
#print("Exercice LCV a implementer !")LCV - Noeuds: 182, Backtracks: 122
MRV pur - Noeuds: 164, Backtracks: 104Les résultats montrent un comportement contre-intuitif de LCV sur ce puzzle difficile.
| Méthode | Noeuds explores | Backtracks | Analyse |
|---|---|---|---|
| LCV | 182 | 122 | Plus de backtracks |
| MRV pur | 164 | 104 | Plus efficace |
Points cles :
count_remaining_options pour chaque couleur peut ralentir la recherche plus qu’il n’aide a reduire les backtracksNote technique : LCV est plus utile sur des graphes avec des degrés heterogenes (certains sommets beaucoup plus contraints que d’autres). Sur le graphe Sudoku regulier (deg. 20 partout), le gain est limite par le cout de calcul.
Implementez un solveur de Sudoku par coloration de graphe avec l’heuristique Welsh-Powell, une approche gloutonne qui ordonne les sommets par degré decroissant avant coloration.
L’heuristique Welsh-Powell est une approche gloutonne classique pour la coloration de graphes :
sort_vertices_by_degree(coloring) : retourne la liste des sommets non colories tries par degré decroissant (en ne comptant que les aretes vers les sommets non colories)
solve_with_welsh_powell(grid) : solveur complet utilisant Welsh-Powell pour le choix du sommet. Le solveur doit :
Comparer les performances de Welsh-Powell vs MRV sur les puzzles difficiles
Indice :
Le degré actuel d’un sommet non colorie est le nombre de ses voisins qui sont également non colories. Plus ce degré est eleve, plus le sommet est contraint et doit etre colorie prioritairement.
Welsh-Powell est une heuristique gloutonne classique qui performe bien sur les graphes de coloration généraux, mais peut etre moins efficace que MRV sur Sudoku ou la structure est très reguliere.
def sort_vertices_by_degree(coloring: List[int], G) -> List[int]:
"""
Retourne la liste des sommets non colories tries par degré decroissant.
Le degré compte les voisins non colories seulement.
"""
uncolored = [v for v in range(81) if coloring[v] == 0]
def get_degree(v):
return sum(1 for neighbor in G.neighbors(v) if coloring[neighbor] == 0)
return sorted(uncolored, key=get_degree, reverse=True)
def solve_with_welsh_powell(grid: SudokuGrid) -> tuple:
"""
Resout le Sudoku avec backtracking + heuristique Welsh-Powell.
Welsh-Powell: choisir le sommet non colorie avec le plus grand degré actuel.
Retourne (success, nodes_explored, backtracks).
"""
G = nx.sudoku_graph()
coloring = grid.to_coloring()
nodes_explored = 0
backtracks = 0
def get_available_colors(vertex: int, coloring: List[int]) -> set:
used = set()
for neighbor in G.neighbors(vertex):
if coloring[neighbor] != 0:
used.add(coloring[neighbor])
return set(range(1, 10)) - used
def backtrack(coloring: List[int]) -> bool:
nonlocal nodes_explored, backtracks
nodes_explored += 1
sorted_vertices = sort_vertices_by_degree(coloring, G)
if not sorted_vertices:
return True
vertex = sorted_vertices[0]
for color in sorted(list(get_available_colors(vertex, coloring))):
coloring[vertex] = color
if backtrack(coloring):
return True
coloring[vertex] = 0
backtracks += 1
return False
success = backtrack(coloring)
grid.from_coloring(coloring)
return success, nodes_explored, backtracks
# Test comparatif Welsh-Powell vs MRV sur un puzzle facile.
# Note: Welsh-Powell selectionne le sommet de plus haut degré non colorie. Sur un graphe
# Sudoku regulier (tous degré 20), cette heuristique n'apporte pas de guide efficace
# et tombe vite dans de longues branches de backtracking sur les puzzles difficiles.
# Les puzzles difficiles peuvent necessiter sys.setrecursionlimit() eleve et un stack Python
# agrandi pour terminer ; on utilise ici un puzzle easy pour un benchmark reproductible.
grid_test = SudokuGrid.from_string(easy_puzzles[0])
success, nodes, bts = solve_with_welsh_powell(grid_test)
print(f"Welsh-Powell (easy[0]) - Succes: {success}, Noeuds: {nodes}, Backtracks: {bts}")
grid_test2 = SudokuGrid.from_string(easy_puzzles[0])
success2, nodes2, bts2 = solve_with_mrv_backtracking(grid_test2)
print(f"MRV (easy[0]) - Succes: {success2}, Noeuds: {nodes2}, Backtracks: {bts2}")Welsh-Powell (easy[0]) - Succes: True, Noeuds: 992, Backtracks: 955
MRV (easy[0]) - Succes: True, Noeuds: 37, Backtracks: 0Les résultats sur le même puzzle easy_puzzles[0] illustrent clairement les limites de Welsh-Powell dans ce contexte.
| Méthode | Noeuds explores | Backtracks | Analyse |
|---|---|---|---|
| Welsh-Powell | 992 | 955 | Beaucoup de retours en arriere |
| MRV pur | 37 | 0 | Resolution sans erreur |
Points cles :
Note technique : Sur les puzzles plus difficiles (
Sudoku_hardest.txt,Sudoku_top95.txt), Welsh-Powell peut partir en branches de recherche très profondes. Unsys.setrecursionlimit(50000)est alors necessaire pour eviter unRecursionError, et sur Windows la taille de stack Python par defaut (1 MB) peut encore limiter ; les benchmarks sur puzzles difficiles sont donc laisses de cote dans ce notebook pour rester reproductible.
Ce notebook a montre comment modeliser le Sudoku comme un problème de coloration de graphe en utilisant NetworkX et sa fonction nx.sudoku_graph(), qui genere automatiquement un graphe regulier de 81 sommets et 810 aretes (degré 20 par sommet). L’implementation a couvert trois stratégies de coloration : le backtracking avec heuristique MRV (Minimum Remaining Values), qui s’est revelee la plus efficace avec 0 backtrack sur les puzzles faciles ; l’heuristique LCV (Least Constraining Value), qui ordonne les couleurs candidates par impact minimal sur les voisins mais s’est revelee contre-productive sur le graphe regulier du Sudoku ; et l’heuristique Welsh-Powell (tri par degré decroissant), inadaptee a la structure reguliere du graphe Sudoku puisque tous les sommets ont un degré identique.
Les benchmarks comparatifs ont permis de quantifier ces différences : MRV resout un puzzle facile en 37 noeuds et 0 backtrack, tandis que Welsh-Powell necessite 992 noeuds et 955 backtracks sur la même instance. Cette expérience illustre un principe fondamental de la resolution de problemes combinatoires : l’efficacite d’une heuristique depend fortement de la structure du graphe sous-jacent. Les heuristiques conques pour des graphes heterogenes (cartes geographiques, allocation de registres) perdent leur avantage sur les graphes reguliers comme celui du Sudoku.
Le prochain notebook, Sudoku-10-ORTools-Python, passe a une approche industrielle de la programmation par contraintes avec OR-Tools CP-SAT, un solveur qui combine propagation de contraintes, recherche locale et programmation lineaire pour atteindre des performances nettement superieures sur les instances difficiles.
| Avantages | Inconvenients |
|---|---|
nx.sudoku_graph() pret a l’emploi |
Pas de solveur complet integre |
| Algorithmes de coloration varies | Moins performant que CP-SAT |
| Facile d’experimentation | Necessite backtracking manuel |
NetworkX peut resoudre de nombreux problemes de coloration :
Navigation : << Human Stratégies | Index | OR-Tools >>