Navigation : << Sudoku-01 Backtracking Python | Index | Sudoku-03 Genetic Python >>
A la fin de ce notebook, vous saurez : 1. Formuler le Sudoku comme un problème de couverture exacte 2. Implementer l’algorithme Dancing Links de Donald Knuth 3. Comprendre les structures de données de listes doublement chainees circulaires 4. Comparer les performances de DLX avec d’autres approches
Duree estimee : ~13 min | Prerequis : Sudoku-00 Environment | Lien : Voir aussi Sudoku-02 DancingLinks C#
Ce notebook implemente un solveur de Sudoku utilisant l’algorithme Dancing Links (DLX) de Donald Knuth. C’est l’equivalent Python du notebook C# Sudoku-02-DancingLinks-CSharp.ipynb.
Dancing Links (DLX) est une technique elegante inventee par Donald Knuth pour implementer efficacement son Algorithm X, qui resout le problème de couverture exacte.
Le nom “Dancing Links” vient de la facon dont les pointeurs “dansent” lors des opérations de suppression et restauration dans une liste doublement chainee circulaire.
| Algorithme | Complexite | Avantage |
|---|---|---|
| Backtracking simple | O(9^81) pire cas | Simple a implementer |
| Backtracking + MRV | O(9^m) m=cases vides | Bonne heuristique |
| Dancing Links | O(n) opérations par noeud | Optimal pour couverture exacte |
DLX est particulierement adapte car: 1. Suppression/Restauration O(1) : Grace aux listes doublement chainees 2. Pas de copie de données : Les noeuds sont simplement “deconnectes” puis “reconnectes” 3. Heuristique MRV integree : Choix de la colonne avec le moins de 1s
Etant donne: - Un ensemble U = {1, 2, 3, …, n} d’éléments - Une collection S = {S1, S2, …, Sm} de sous-ensembles de U
Trouver une couverture exacte: une sous-collection S* de S telle que chaque élément de U appartient a exactement un sous-ensemble de S*.
U = {1, 2, 3, 4, 5, 6, 7}
S = {
A = {1, 4, 7}
B = {1, 4}
C = {4, 5, 7}
D = {3, 5, 6}
E = {2, 3, 6, 7}
F = {2, 7}
}Solution: S* = {B, D, F} car: - B couvre {1, 4} - D couvre {3, 5, 6} - F couvre {2, 7} - Union = {1, 2, 3, 4, 5, 6, 7} = U (chaque élément exactement une fois)
On represente le problème par une matrice binaire: - Chaque ligne = un sous-ensemble - Chaque colonne = un élément de U - M[i,j] = 1 si l’élément j est dans le sous-ensemble i
1 2 3 4 5 6 7
A = [1, 0, 0, 1, 0, 0, 1]
B = [1, 0, 0, 1, 0, 0, 0]
C = [0, 0, 0, 1, 1, 0, 1]
D = [0, 0, 1, 0, 1, 1, 0]
E = [0, 1, 1, 0, 0, 1, 1]
F = [0, 1, 0, 0, 0, 0, 1]Une couverture exacte = sélection de lignes ou chaque colonne a exactement un 1.
Un Sudoku 9x9 standard a 324 contraintes (colonnes) reparties en 4 catégories:
| Type | Description | Nombre | Colonnes |
|---|---|---|---|
| Cell | Chaque cellule contient exactement un chiffre | 81 | 0-80 |
| Row | Chaque ligne contient chaque chiffre 1-9 | 81 | 81-161 |
| Column | Chaque colonne contient chaque chiffre 1-9 | 81 | 162-242 |
| Box | Chaque bloc 3x3 contient chaque chiffre 1-9 | 81 | 243-323 |
Chaque ligne de la matrice represente le placement d’un chiffre v (1-9) dans une cellule (r, c):
Pour un placement (row=r, col=c, value=v):
# Contrainte Cell: cellule (r,c) est remplie
cell_col = r * 9 + c # 0-80
# Contrainte Row: ligne r contient valeur v
row_col = 81 + r * 9 + (v - 1) # 81-161
# Contrainte Column: colonne c contient valeur v
col_col = 162 + c * 9 + (v - 1) # 162-242
# Contrainte Box: bloc b contient valeur v
box = (r // 3) * 3 + (c // 3)
box_col = 243 + box * 9 + (v - 1) # 243-323Placer le chiffre 5 en position (2, 3) (ligne 2, colonne 3):
Contrainte Cell: colonne 2*9+3 = 21
Contrainte Row: colonne 81 + 2*9 + 4 = 103
Contrainte Column: colonne 162 + 3*9 + 4 = 193
Contrainte Box: colonne 243 + 0*9 + 4 = 247 (bloc 0)
Ligne de la matrice: [0...1...0] avec des 1 aux positions 21, 103, 193, 247function solve(matrix):
if matrix is empty:
return SUCCESS # Solution trouvee!
# Choisir la colonne c avec le moins de 1s (heuristique MRV)
c = column_with_minimum_ones(matrix)
if c has no 1s:
return FAILURE # Impasse
# Pour chaque ligne r ayant un 1 dans la colonne c
for each row r where matrix[r][c] == 1:
# Ajouter r a la solution partielle
solution.add(r)
# Couvrir: supprimer c et toutes les lignes en conflit
cover(c)
for each column j where matrix[r][j] == 1:
cover(j)
# Recursion
result = solve(reduced_matrix)
if result == SUCCESS:
return SUCCESS
# Backtrack: restaurer les colonnes
for each column j where matrix[r][j] == 1 (reverse order):
uncover(j)
uncover(c)
solution.remove(r)
return FAILUREDans une liste doublement chainee, supprimer un noeud x:
Et le restaurer (x garde ses pointeurs!):
C’est cette propriete qui permet un backtracking très efficace: les noeuds “dansent” en entrant et sortant de la structure sans etre detruits.
Objectif Construisez manuellement la matrice de couverture exacte pour un Sudoku 4x4 (et non 9x9), ou chaque ligne/colonne/bloc 2x2 doit contenir les chiffres 1 a 4.
Indice Identifiez les 4 types de contraintes (ligne, colonne, bloc, cellule) et comptez le nombre de colonnes de la matrice. Pour chaque assignation possible (cellule, valeur), créez une ligne dans la matrice avec des 1 aux colonnes des contraintes satisfaites.
# EXERCICE : Construire la matrice de couverture exacte pour un mini-Sudoku 4x4
def build_mini_sudoku_matrix() -> list:
# TODO: Construisez la matrice binaire de couverture exacte
# pour un Sudoku 4x4 (chiffres 1-4, blocs 2x2)
# Retournez une liste de listes (lignes = assignations, colonnes = contraintes)
result = None # TODO etudiant
return result
print("Exercice a completer")Exercice a completerLa structure DLX utilise des noeuds doublement chaînes dans 4 directions: - left/right: navigation horizontale dans une ligne - up/down: navigation verticale dans une colonne
Chaque colonne a un noeud special “header” qui contient: - Le nombre de 1s dans la colonne (pour l’heuristique MRV) - Un identifiant de colonne
Tous les headers sont lies horizontalement, avec un noeud “root” special.
class DancingLinksNode:
"""Noeud dans la structure Dancing Links.
Chaque noeud est connecte a 4 voisins (gauche, droite, haut, bas)
formant une grille de listes doublement chainees circulaires.
Attributes:
left: Noeud a gauche dans la meme ligne
right: Noeud a droite dans la meme ligne
up: Noeud au-dessus dans la meme colonne
down: Noeud en-dessous dans la meme colonne
column: Reference vers le header de colonne
row_id: Identifiant de la ligne (pour reconstruire la solution)
"""
__slots__ = ['left', 'right', 'up', 'down', 'column', 'row_id']
def __init__(self):
self.left = self
self.right = self
self.up = self
self.down = self
self.column = None
self.row_id = None
class ColumnHeader(DancingLinksNode):
"""Header de colonne avec compteur de taille.
Attributes:
size: Nombre de noeuds (1s) dans cette colonne
name: Identifiant de la colonne (pour debug)
"""
__slots__ = ['size', 'name']
def __init__(self, name: int = 0):
super().__init__()
self.size = 0
self.name = name
self.column = self # Un header pointe vers lui-meme
print("Classes DancingLinksNode et ColumnHeader definies")Classes DancingLinksNode et ColumnHeader definiesCette classe implemente l’algorithme complet: 1. Construction de la matrice a partir des contraintes 2. Cover/Uncover pour la suppression/restauration efficace 3. Search (Algorithm X) avec backtracking
class DancingLinks:
"""Implementation complete de l'algorithme Dancing Links.
Cette classe construit une matrice creuse et implemente l'Algorithm X
de Knuth pour resoudre le probleme de couverture exacte.
"""
def __init__(self, num_columns: int):
"""Initialise la structure avec le nombre de colonnes.
Args:
num_columns: Nombre de contraintes (324 pour Sudoku 9x9)
"""
# Creer le noeud racine
self.root = ColumnHeader(-1)
# Creer les headers de colonnes
self.columns: List[ColumnHeader] = []
prev = self.root
for i in range(num_columns):
header = ColumnHeader(i)
self.columns.append(header)
# Lier horizontalement
header.left = prev
header.right = self.root
prev.right = header
self.root.left = header
prev = header
# Solution courante (liste d'indices de lignes)
self.solution: List[int] = []
self.solutions_found: List[List[int]] = []
def add_row(self, row_id: int, columns: List[int]):
"""Ajoute une ligne avec des 1s aux colonnes specifiees.
Args:
row_id: Identifiant unique de la ligne
columns: Liste des indices de colonnes ayant un 1
"""
if not columns:
return
first_node = None
prev_node = None
for col_idx in columns:
# Creer un nouveau noeud
node = DancingLinksNode()
node.row_id = row_id
node.column = self.columns[col_idx]
# Inserer en bas de la colonne
col_header = self.columns[col_idx]
node.up = col_header.up
node.down = col_header
col_header.up.down = node
col_header.up = node
col_header.size += 1
# Lier horizontalement
if first_node is None:
first_node = node
node.left = node
node.right = node
else:
node.left = prev_node
node.right = first_node
prev_node.right = node
first_node.left = node
prev_node = node
def cover(self, col: ColumnHeader):
"""Couvre une colonne (la supprime temporairement).
Cette operation:
1. Deconnecte le header de la liste des colonnes
2. Pour chaque ligne ayant un 1 dans cette colonne,
deconnecte tous les autres noeuds de cette ligne
Args:
col: Header de la colonne a couvrir
"""
# Deconnecter le header horizontalement
col.right.left = col.left
col.left.right = col.right
# Parcourir vers le bas dans la colonne
i = col.down
while i != col:
# Parcourir vers la droite dans la ligne
j = i.right
while j != i:
# Deconnecter verticalement
j.down.up = j.up
j.up.down = j.down
j.column.size -= 1
j = j.right
i = i.down
def uncover(self, col: ColumnHeader):
"""Decouvre une colonne (la restaure).
Operation inverse de cover(), executee dans l'ordre inverse.
Args:
col: Header de la colonne a restaurer
"""
# Parcourir vers le haut dans la colonne
i = col.up
while i != col:
# Parcourir vers la gauche dans la ligne
j = i.left
while j != i:
# Reconnecter verticalement
j.column.size += 1
j.down.up = j
j.up.down = j
j = j.left
i = i.up
# Reconnecter le header horizontalement
col.right.left = col
col.left.right = col
def choose_column(self) -> Optional[ColumnHeader]:
"""Choisit la colonne avec le moins de 1s (heuristique MRV).
Returns:
Le header de colonne avec le minimum de noeuds,
ou None si toutes les colonnes sont couvertes.
"""
min_size = float('inf')
best_col = None
col = self.root.right
while col != self.root:
if col.size < min_size:
min_size = col.size
best_col = col
col = col.right
return best_col
def search(self, find_all: bool = True, max_count=10) -> bool:
"""Algorithme X recursif.
Args:
find_all: Si True, trouve toutes les solutions
Returns:
True si une solution est trouvee
"""
output = 0
# Cas de base: toutes les colonnes couvertes
if self.root.right == self.root:
self.solutions_found.append(self.solution.copy())
return not find_all # Continuer si on cherche toutes les solutions
if len(self.solutions_found) == max_count:
return max_count
if max_count == 0:
return 0
# Choisir la colonne avec le moins de 1s
col = self.choose_column()
# Si une colonne est vide, impasse
if col is None or col.size == 0:
return 0
# Couvrir cette colonne
self.cover(col)
# Essayer chaque ligne ayant un 1 dans cette colonne
row = col.down
while row != col:
# Ajouter cette ligne a la solution
self.solution.append(row.row_id)
# Couvrir toutes les colonnes de cette ligne
j = row.right
while j != row:
self.cover(j.column)
j = j.right
# Recursion
output += self.search(find_all, max_count)
if output != 0:
if not find_all:
return output
# Backtrack
self.solution.pop()
max_count -= 1
# Decouvrir les colonnes dans l'ordre inverse
j = row.left
while j != row:
self.uncover(j.column)
j = j.left
row = row.down
# Decouvrir la colonne choisie
self.uncover(col)
return len(self.solutions_found)
def search2(self, find_all: bool = True, limit: int = 10) -> bool:
"""Algorithme X avec support pour solutions multiples et limite."""
# Cas de base : toutes les colonnes sont couvertes
if self.root.right == self.root:
self.solutions_found.append(self.solution.copy())
# Si on a atteint la limite, on signale qu'il faut s'arrêter
return True if (not find_all or len(self.solutions_found) >= limit) else False
col = self.choose_column()
if col is None or col.size == 0:
return False
self.cover(col)
row = col.down
while row != col:
self.solution.append(row.row_id)
# Couvrir les colonnes liées à cette ligne
j = row.right
while j != row:
self.cover(j.column)
j = j.right
# Récursion : si elle retourne True, on a atteint l'arrêt demandé
if self.search2(find_all, limit):
if not find_all or len(self.solutions_found) >= limit:
# Nettoyage avant de remonter (Backtrack partiel)
# Note : Dans une recherche exhaustive avec arrêt brutal,
# le nettoyage est moins critique car on sort de la pile.
return True
# Backtrack
self.solution.pop()
j = row.left
while j != row:
self.uncover(j.column)
j = j.left
row = row.down
self.uncover(col)
return len(self.solutions_found) >= limit
print("Classe DancingLinks definie")Classe DancingLinks definieCette classe traduit un puzzle Sudoku en problème de couverture exacte, puis utilise DancingLinks pour le resoudre.
class SudokuGrid:
"""Representation d'une grille de Sudoku 9x9."""
def __init__(self, cells: Optional[List[List[int]]] = None):
if cells is None:
self.cells = [[0] * 9 for _ in range(9)]
else:
self.cells = [row[:] for row in cells]
@classmethod
def from_string(cls, s: str) -> 'SudokuGrid':
"""Cree une grille depuis une chaine de 81 caracteres."""
s = s.replace('.', '0').replace(' ', '').replace('\n', '')
if len(s) != 81:
raise ValueError(f"Attendu 81 caracteres, recu {len(s)}")
grid = cls()
for i in range(81):
grid.cells[i // 9][i % 9] = int(s[i])
return grid
def clone(self) -> 'SudokuGrid':
return SudokuGrid(self.cells)
def is_valid(self) -> bool:
"""Verifie si la grille est une solution valide."""
# Verifier que toutes les cellules sont remplies
for r in range(9):
for c in range(9):
if self.cells[r][c] == 0:
return False
# Verifier lignes
for r in range(9):
if len(set(self.cells[r])) != 9:
return False
# Verifier colonnes
for c in range(9):
if len(set(self.cells[r][c] for r in range(9))) != 9:
return False
# Verifier blocs
for br in range(3):
for bc in range(3):
block = []
for r in range(3):
for c in range(3):
block.append(self.cells[br*3+r][bc*3+c])
if len(set(block)) != 9:
return False
return True
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)
class DLXSudokuSolver:
"""Solveur de Sudoku utilisant Dancing Links.
Traduit le Sudoku en probleme de couverture exacte:
- 324 colonnes (contraintes)
- Jusqu'a 729 lignes (possibilites)
- 4 bits a 1 par ligne
"""
NUM_COLUMNS = 324 # 4 * 81 contraintes
def __init__(self):
self.call_count = 0
def solve(self, puzzle: SudokuGrid) -> Optional[SudokuGrid]:
"""Resout le Sudoku avec Dancing Links.
Args:
puzzle: Grille de depart (0 = case vide)
Returns:
Grille resolue ou None si pas de solution
"""
dlx = DancingLinks(self.NUM_COLUMNS)
row_info = {} # row_id -> (r, c, v)
row_id = 0
# Construire la matrice
for r in range(9):
for c in range(9):
cell_value = puzzle.cells[r][c]
# Determiner les valeurs possibles
if cell_value != 0:
# Cellule deja remplie: une seule possibilite
values = [cell_value]
else:
# Cellule vide: toutes les valeurs 1-9
values = range(1, 10)
for v in values:
# Calculer les 4 colonnes a mettre a 1
columns = self._get_columns(r, c, v)
# Ajouter la ligne
dlx.add_row(row_id, columns)
row_info[row_id] = (r, c, v)
row_id += 1
# Resoudre
if dlx.search():
# Reconstruire la solution
result = puzzle.clone()
for rid in dlx.solutions_found[0]:
r, c, v = row_info[rid]
result.cells[r][c] = v
return result
return None
def _get_columns(self, r: int, c: int, v: int) -> List[int]:
"""Calcule les 4 indices de colonnes pour un placement.
Args:
r: Ligne (0-8)
c: Colonne (0-8)
v: Valeur (1-9)
Returns:
Liste de 4 indices de colonnes
"""
box = (r // 3) * 3 + (c // 3)
return [
r * 9 + c, # Cell constraint (0-80)
81 + r * 9 + (v - 1), # Row constraint (81-161)
162 + c * 9 + (v - 1), # Column constraint (162-242)
243 + box * 9 + (v - 1) # Box constraint (243-323)
]
print("Classes SudokuGrid et DLXSudokuSolver definies")Classes SudokuGrid et DLXSudokuSolver definiesL’implementation de Dancing Links pour Sudoku comprend 3 classes principales avec des responsabilites clairement separees.
| Classe | Responsabilite | Méthodes cles |
|---|---|---|
| DancingLinksNode | Noeud de base avec 4 pointeurs | left, right, up, down, column, row_id |
| ColumnHeader | Header de colonne avec compteur | size, name |
| DancingLinks | Structure DLX complete + Algorithm X | add_row(), cover(), uncover(), search() |
| SudokuGrid | Representation grille 9x9 | from_string(), is_valid(), str() |
| DLXSudokuSolver | Traduction Sudoku -> Couverture exacte | solve(), _get_columns() |
Points cles de l’architecture : 1. Separation des preoccupations : La structure DLX est independante de Sudoku 2. Pattern Builder : add_row() construit la matrice incrementalement 3. Opérations O(1) : cover() et uncover() manipulent uniquement des pointeurs 4. Traduction explicite : _get_columns() encode les 4 contraintes Sudoku
Correspondance Sudoku -> Couverture exacte : - 324 colonnes = 4 types de contraintes x 81 cases/lignes/colonnes/blocs - 729 lignes maximum = 9 positions x 9 valeurs possibles par case - Chaque ligne a exactement 4 bits a 1 (une contrainte de chaque type)
Note technique : L’utilisation de
__slots__dans les classes noeuds reduit la memoire utilisee en evitant la creation de dictionnaires__dict__. Pour une grille Sudoku, cela represente des milliers de noeuds, donc l’optimisation est significative.
# Puzzle de test
test_puzzle = "530070000600195000098000060800060003400803001700020006060000280000419005000080079"
puzzle = SudokuGrid.from_string(test_puzzle)
print("Puzzle initial:")
print(puzzle)
print()
# Resoudre
solver = DLXSudokuSolver()
start = time.time()
solution = solver.solve(puzzle)
elapsed = (time.time() - start) * 1000
if solution:
print(f"Solution trouvee en {elapsed:.2f} ms:")
print(solution)
print(f"\nSolution valide: {solution.is_valid()}")
else:
print("Pas de solution!")Puzzle initial:
5 3 . | . 7 . | . . .
6 . . | 1 9 5 | . . .
. 9 8 | . . . | . 6 .
---------------------
8 . . | . 6 . | . . 3
4 . . | 8 . 3 | . . 1
7 . . | . 2 . | . . 6
---------------------
. 6 . | . . . | 2 8 .
. . . | 4 1 9 | . . 5
. . . | . 8 . | . 7 9
Solution trouvee en 4.74 ms:
5 3 4 | 6 7 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
---------------------
8 5 9 | 7 6 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
---------------------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9
Solution valide: TrueLe solveur DLX a resolu le puzzle en (ms live – regle #9434), ce qui est excellent.
| Aspect | Valeur | Signification |
|---|---|---|
| Temps de resolution | (ms live – regle #9434) | Très rapide, même pour un puzzle de difficulte moyenne |
| Solution valide | True | L’algorithme a trouve une solution correcte |
| Cases vides initiales | 51 | Puzzle relativement difficile (presque la moitie de la grille) |
Points cles : 1. Performance immediatement optimale : DLX n’a pas besoin d’heuristiques additionnelles 2. Resolution correcte : La solution respecte toutes les contraintes Sudoku 3. Comparaison favorable : (ms live – regle #9434) est largement plus rapide que le backtracking simple sur des puzzles similaires
Note technique : Le temps de resolution inclut la construction de la matrice de couverture exacte (324 colonnes x 729 lignes maximum) et l’exécution de l’algorithme X. Malgre cette surcharge initiale, DLX reste extremement rapide car la structure de données est optimisee pour ce type de problème.
Le solveur DLX trouve une solution au Sudoku en construisant une matrice de couverture exacte. Mais comment etre sur que la solution est correcte ? Il faut verifier que toutes les contraintes sont couvertes exactement une fois.
Implementez la fonction qui verifie qu’une solution Dancing Links est une couverture exacte valide pour un Sudoku 9x9.
Indices : - Pour chaque ligne selectionnee, utilisez pour obtenir les 4 colonnes couvertes - Utilisez un tableau de taille 324 pour compter les occurrences - La couverture exacte signifie : chaque colonne a un compte de exactement 1
def verify_dlx_solution(solution_rows: list, row_info: dict,
solver: DLXSudokuSolver) -> bool:
"""Verifie qu'une solution DLX est une couverture exacte valide.
Args:
solution_rows: Liste des row_ids selectionnes par DLX
row_info: Dictionnaire row_id -> (r, c, v)
solver: Instance de DLXSudokuSolver pour acceder a _get_columns
Returns:
True si la solution est une couverture exacte valide, False sinon
"""
# Etape 1 : Verifier qu'on a exactement 81 lignes (une par case)
# Etape 2 : Compter combien de fois chaque contrainte (colonne 0-323) est couverte
# Etape 3 : Verifier que les 324 contraintes sont couvertes exactement 1 fois
return False # TODO etudiant : implementez la verification
# Test de votre implementation
print("Exercice verify_dlx_solution a completer")Exercice verify_dlx_solution a completerdef load_puzzles(filepath: str, max_puzzles: int = None) -> List[str]:
"""Charge les puzzles depuis un fichier.
Chaque ligne du fichier doit contenir au moins 81 caracteres
representant un puzzle (0 ou . pour les cases vides).
Args:
filepath: Chemin vers le fichier
max_puzzles: Nombre maximum de puzzles a charger
Returns:
Liste de chaines de 81 caracteres
"""
puzzles = []
try:
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
except FileNotFoundError:
print(f"Fichier non trouve: {filepath}")
return puzzles
# Charger les puzzles
from pathlib import Path
NOTEBOOK_DIR = Path.cwd()
PUZZLES_DIR = NOTEBOOK_DIR / "Puzzles"
easy_puzzles = load_puzzles(str(PUZZLES_DIR / 'Sudoku_Easy51.txt'), max_puzzles=10)
hard_puzzles = load_puzzles(str(PUZZLES_DIR / 'Sudoku_hardest.txt'))
print(f"Puzzles faciles charges: {len(easy_puzzles)}")
print(f"Puzzles difficiles charges: {len(hard_puzzles)}")Puzzles faciles charges: 10
Puzzles difficiles charges: 11Les fichiers de puzzles ont ete charges avec succes depuis le dossier Puzzles/.
| Fichier | Statut | Contenu |
|---|---|---|
| Sudoku_Easy51.txt | Charge | 10 puzzles faciles |
| Sudoku_hardest.txt | Charge | 11 puzzles difficiles |
Utilisation : 1. Les puzzles faciles alimentent le benchmark de la section suivante 2. Les puzzles difficiles (Top 11) testent DLX sur des grilles plus contraintes 3. Un puzzle hardcode (section 6.1) reste disponible comme exemple autonome
Note technique : Le chargement lit les fichiers
.txtdu dossierPuzzles/; un puzzle hardcode (section 6.1) reste disponible comme exemple autonome.
Objectif Analysez le nombre de noeuds explores par DLX en fonction de la difficulte du puzzle. Mesurez et comparez avec le backtracking simple.
Étape 1 Ajoutez un compteur de noeuds dans la classe DancingLinks. Étape 2 Lancez le benchmark et collectez les données.
Exercice a completerdef benchmark_dlx(puzzles: List[str], name: str):
"""Benchmark le solveur DLX sur une liste de puzzles.
Args:
puzzles: Liste de puzzles (chaines de 81 caracteres)
name: Nom du benchmark pour l'affichage
"""
if not puzzles:
print(f"Aucun puzzle pour {name}")
return
print(f"\n{'='*60}")
print(f"Benchmark DLX: {name} ({len(puzzles)} puzzles)")
print('='*60)
solver = DLXSudokuSolver()
total_time = 0
solved_count = 0
times = []
for i, puzzle_str in enumerate(puzzles):
puzzle = SudokuGrid.from_string(puzzle_str)
start = time.time()
solution = solver.solve(puzzle)
elapsed = (time.time() - start) * 1000
total_time += elapsed
times.append(elapsed)
if solution and solution.is_valid():
solved_count += 1
status = "OK"
else:
status = "ECHEC"
if i < 5 or status == "ECHEC": # Premiers et echecs
print(f" Puzzle {i+1:2d}: {status} en {elapsed:>8.3f} ms")
if len(puzzles) > 5 and solved_count == len(puzzles):
print(f" ... ({len(puzzles)-5} autres puzzles resolus)")
print(f"\nResultats:")
print(f" Resolus: {solved_count}/{len(puzzles)}")
print(f" Temps total: {total_time:>10.2f} ms")
print(f" Temps moyen: {total_time/len(puzzles):>10.3f} ms")
print(f" Temps min: {min(times):>10.3f} ms")
print(f" Temps max: {max(times):>10.3f} ms")
# Benchmarks
benchmark_dlx(easy_puzzles, "Puzzles Faciles")
benchmark_dlx(hard_puzzles, "Puzzles Difficiles (Top 11)")
============================================================
Benchmark DLX: Puzzles Faciles (10 puzzles)
============================================================
Puzzle 1: OK en 4.187 ms
Puzzle 2: OK en 4.887 ms
Puzzle 3: OK en 4.074 ms
Puzzle 4: OK en 4.870 ms
Puzzle 5: OK en 5.478 ms
... (5 autres puzzles resolus)
Resultats:
Resolus: 10/10
Temps total: 53.10 ms
Temps moyen: 5.310 ms
Temps min: 4.074 ms
Temps max: 11.019 ms
============================================================
Benchmark DLX: Puzzles Difficiles (Top 11) (11 puzzles)
============================================================
Puzzle 1: OK en 7.533 ms
Puzzle 2: OK en 20.132 ms
Puzzle 3: OK en 6.705 ms
Puzzle 4: OK en 15.688 ms
Puzzle 5: OK en 4.699 ms
... (6 autres puzzles resolus)
Resultats:
Resolus: 11/11
Temps total: 133.40 ms
Temps moyen: 12.128 ms
Temps min: 4.699 ms
Temps max: 33.152 msLes benchmarks ont ete executes sur les puzzles charges. DLX resout 21/21 puzzles (10 faciles + 11 difficiles) :
| Jeu de puzzles | Resolus | Temps moyen | Temps min / max |
|---|---|---|---|
| Faciles (10) | 10/10 | (ms live – regle #9434) | (ms live) |
| Difficiles Top 11 (11) | 11/11 | (ms live) | (ms live) |
Points cles : 1. Efficacite exceptionnelle : DLX est optimise pour les problemes de couverture exacte 2. Pas de copie de données : Les opérations cover/uncover sont O(1) grace aux pointeurs 3. Heuristique MRV integree : Le choix de la colonne avec le moins de 1s est naturel dans DLX 4. Backtracking instantane : La restauration des noeuds est immediate (pointeurs déjà memorises)
Note technique : La performance de DLX vient de la structure de données elle-même. Contrairement au backtracking qui doit copier des grilles, DLX manipule uniquement des pointeurs dans une liste doublement chainee circulaire. Les opérations de suppression et restauration sont donc O(1).
Une grille de Sudoku “bien construite” possede exactement une solution. Mais certaines grilles incompletes peuvent avoir plusieurs solutions.
Nous avons modifie le solveur Dancing Links pour compter le nombre total de solutions d’une grille donnee :
search2() de la classe DancingLinks permet de chercher plusieurs solutions avec une limitecount_solutions(puzzle, max_count=10) construit la matrice DLX et lance la recherche exhaustiveIndice :
Pour la grille vide (81 cases vides), le nombre de Sudokus valides est de 6 670 903 752 021 072 936 960. L’implementation s’arrete rapidement grace au paramètre max_count.
def count_solutions(puzzle: SudokuGrid, max_count: int = 10) -> int:
"""Compte le nombre de solutions d'une grille Sudoku.
Args:
puzzle: Grille de depart (0 = case vide)
max_count: Nombre maximum de solutions a chercher
Returns:
Nombre de solutions trouvees (au plus max_count)
Indices d'implementation :
1. Construire la matrice DLX comme dans `DLXSudokuSolver.solve` :
- Creer `DancingLinks(solver.NUM_COLUMNS)`
- Pour chaque case (r, c), si la case est remplie (val != 0) ajouter
une seule ligne de contrainte ; sinon, ajouter 9 lignes (une par
valeur 1-9)
- Utiliser `solver._get_columns(r, c, v)` pour obtenir les colonnes
2. Lancer `dlx.search2(find_all=True, limit=max_count)`
3. Retourner `len(dlx.solutions_found)`
Le cas `puzzle is None` peut etre gere en tete pour robustesse.
"""
# Exercice: implementez count_solutions avec Dancing Links
pass
# Tests de votre implementation (decommentez apres implementation)
# print("Test 1: grille avec une solution unique")
# puzzle_unique = SudokuGrid.from_string(
# "530070000600195000098000060800060003400803001700020006060000280000419005000080079"
# )
# count = count_solutions(puzzle_unique, max_count=5)
# print(f" Nombre de solutions : {count} (attendu : 1)")
#
# print("Test 2: grille sous-contrainte (plusieurs solutions)")
# puzzle_multi = SudokuGrid.from_string(
# "000000000000000000000000000000000000000000000000000000000000000000000000000000000"
# )
# count = count_solutions(puzzle_multi, max_count=3)
# print(f" Nombre de solutions trouvees (limite a 3) : {count}")
print("Exercice count_solutions a completer - voir les indices ci-dessus")Exercice count_solutions a completer - voir les indices ci-dessusLe problème des N-Reines est un autre cas classique de couverture exacte. Pour un echiquier N x N, il faut placer N reines de sorte qu’aucune ne puisse en capturer une autre.
Objectif : Implementez un solveur de N-Reines en reutilisant la classe DancingLinks déjà définie.
Pour N reines sur un echiquier N x N, les contraintes sont : 1. Ligne : exactement une reine par ligne (N contraintes) 2. Colonne : exactement une reine par colonne (N contraintes) 3. Diagonale montante : au plus une reine par diagonale / (2N-1 contraintes, couverture partielle) 4. Diagonale descendante : au plus une reine par diagonale \ (2N-1 contraintes, couverture partielle)
Attention : contrairement au Sudoku ou chaque contrainte est “exactement un”, les diagonales sont des contraintes “au plus un”. Pour les encoder en couverture exacte, utilisez des colonnes secondaires (optionnelles) – voyez l’indice ci-dessous.
Étapes :
build_nqueens_matrix(n) qui construit la matrice de couverture exacte pour N reinessolve_nqueens(n) qui utilise DancingLinks pour trouver toutes les solutionsIndice :
Pour simplifier, commencez par ignorer les diagonales et utilisez uniquement les contraintes de ligne et de colonne (couverture exacte stricte : 2N colonnes, N^2 lignes). Verifiez ensuite que les solutions obtenues respectent aussi les diagonales. Le nombre de solutions pour N=8 est 92 (solutions distinctes), et pour N=4 c’est 2.
def build_nqueens_matrix(n: int):
"""Construit la matrice de couverture exacte pour le probleme des N-Reines.
Chaque ligne de la matrice represente le placement d'une reine a la position (r, c).
Args:
n: Taille de l'echiquier (n x n)
Returns:
Tuple (num_columns, rows) ou rows est une liste de tuples (row_id, [column_indices])
"""
# Exercice: Determiner le nombre de colonnes (contraintes)
# Exercice: Construire les lignes de la matrice
# Exercice: Retourner la structure pour DancingLinks
pass
def solve_nqueens(n: int, max_count: int = 100) -> List:
"""Resout le probleme des N-Reines avec Dancing Links.
Args:
n: Taille de l'echiquier
max_count: Nombre maximum de solutions a chercher
Returns:
Liste des solutions trouvees
"""
# Exercice: Utiliser build_nqueens_matrix et DancingLinks pour resoudre
pass
def print_nqueens_solution(solution, n: int):
"""Affiche une solution du probleme des N-Reines.
Args:
solution: Liste des positions (row, col) des reines
n: Taille de l'echiquier
"""
# Exercice: Afficher l'echiquier avec les reines placees
pass
# Tests
print("=== N-Reines avec Dancing Links ===")
print()
# Exemple guide: Test N=4 (attendu : 2 solutions)
# Exemple guide: Test N=8 (attendu : 92 solutions)
# Exemple guide: Afficher quelques solutions sous forme d'echiquier=== N-Reines avec Dancing Links ===
| Algorithme | Puzzle facile | Puzzle difficile |
|---|---|---|
| Backtracking simple | 1-10 ms | 100-1000 ms |
| Backtracking + MRV | 0.5-5 ms | 10-100 ms |
| Dancing Links (mesure) | ~3.6 ms | ~9.6 ms |
| OR-Tools CP-SAT | 1-5 ms | 5-20 ms |
| Z3 SMT | 5-20 ms | 20-100 ms |
Seule la ligne Dancing Links est mesuree dans ce notebook (benchmark section 6) ; les autres lignes sont des ordres de grandeur indicatifs issus de leurs notebooks respectifs.
Navigation : << Sudoku-01 Backtracking Python | Index | Sudoku-03 Genetic Python >>