Search-08-DancingLinks : L’algorithme X et Dancing Links de Knuth

Navigation : << MCTS | Index | Programmation lineaire >>

References

  • Original paper : Knuth, D. E. (2000). Dancing Links. arXiv:cs/0011047
  • Applications : Sudoku, N-Queens, Pentominoes, Exact Cover
  • Notebook connexe : Sudoku-02-DancingLinks-Python
# Imports
import sys
import time
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as patches
from typing import List, Optional, Set, Tuple
from dataclasses import dataclass
from collections import defaultdict

%matplotlib inline

print("Environnement pret pour Dancing Links.")
print(f"Python {sys.version}")
Environnement pret pour Dancing Links.
Python 3.13.7 (tags/v3.13.7:bcee1c3, Aug 14 2025, 14:15:11) [MSC v.1944 64 bit (AMD64)]

1. Le problème de Couverture Exacte (~15 min)

Definition formelle

Le problème de couverture exacte (Exact Cover) est un problème de decision classique en théorie de la complexite.

Entree : - Un univers \(U\) d’éléments \(\{u_1, u_2, ..., u_n\}\) - Une collection \(S\) de sous-ensembles de \(U\), \(S = \{S_1, S_2, ..., S_m\}\)

Question : Existe-t-il une sous-collection \(S^* \subseteq S\) telle que : 1. Chaque élément de \(U\) est contenu dans exactement un sous-ensemble de \(S^*\) 2. Les sous-ensembles de \(S^*\) sont disjoints deux a deux

Representation matricielle

Le problème peut etre represente par une matrice binaire : - Les colonnes representent les éléments de l’univers - Les lignes representent les sous-ensembles - Une case a 1 si l’élément appartient au sous-ensemble, 0 sinon

Objectif : sélectionner un ensemble de lignes tel que chaque colonne ait exactement un 1 selectionne.

# Exemple simple de couverture exacte

# Univers : U = {1, 2, 3, 4, 5, 6, 7}
# Sous-ensembles : S1={1,4,7}, S2={1,4}, S3={4,5,7}, S4={3,5,6}, S5={2,3,6,7}, S6={2,7}
# Matrice de representation
#    1 2 3 4 5 6 7
# S1 1 0 0 1 0 0 1
# S2 1 0 0 1 0 0 0
# S3 0 0 0 1 1 0 1
# S4 0 0 1 0 1 1 0
# S5 0 1 1 0 0 1 1
# S6 0 1 0 0 0 0 1

# Solution: {S2, S4, S6}
# Verification: S2 U S4 U S6 = {1,4} U {3,5,6} U {2,7} = {1,2,3,4,5,6,7}

# Representation en Python
matrix = np.array([
    [1, 0, 0, 1, 0, 0, 1],  # S1
    [1, 0, 0, 1, 0, 0, 0],  # S2
    [0, 0, 0, 1, 1, 0, 1],  # S3
    [0, 0, 1, 0, 1, 1, 0],  # S4
    [0, 1, 1, 0, 0, 1, 1],  # S5
    [0, 1, 0, 0, 0, 0, 1],  # S6
])

solution_indices = [1, 3, 5]  # S2, S4, S6

print("Exemple de couverture exacte")
print("=" * 50)
print("Univers U = {1, 2, 3, 4, 5, 6, 7}")
print("\nMatrice binaire (lignes = sous-ensembles):")
print("    1 2 3 4 5 6 7")
row_names = ["S1", "S2", "S3", "S4", "S5", "S6"]
for i, row in enumerate(matrix):
    print(f"{row_names[i]}: {row}")

print("\nSolution proposee: {S2, S4, S6}")
solution_rows = matrix[solution_indices]
covered = np.sum(solution_rows, axis=0)
print(f"Elements couverts par ligne:")
print(f"  S2: {matrix[1]}")
print(f"  S4: {matrix[3]}")
print(f"  S6: {matrix[5]}")
print(f"Total: {covered}")
print(f"Verification: tous les elements couverts exactement une fois? {np.all(covered == 1)}")
Exemple de couverture exacte
==================================================
Univers U = {1, 2, 3, 4, 5, 6, 7}

Matrice binaire (lignes = sous-ensembles):
    1 2 3 4 5 6 7
S1: [1 0 0 1 0 0 1]
S2: [1 0 0 1 0 0 0]
S3: [0 0 0 1 1 0 1]
S4: [0 0 1 0 1 1 0]
S5: [0 1 1 0 0 1 1]
S6: [0 1 0 0 0 0 1]

Solution proposee: {S2, S4, S6}
Elements couverts par ligne:
  S2: [1 0 0 1 0 0 0]
  S4: [0 0 1 0 1 1 0]
  S6: [0 1 0 0 0 0 1]
Total: [1 1 1 1 1 1 1]
Verification: tous les elements couverts exactement une fois? True

Visualisation de la couverture exacte

Visualisons comment les sous-ensembles S2, S4 et S6 couvrent exactement tous les éléments de l’univers.

# Visualisation de la couverture exacte
fig, ax = plt.subplots(figsize=(10, 4))

# Dessiner l'univers comme des cercles
elements = ['1', '2', '3', '4', '5', '6', '7']
colors = ['#FF6B6B', '#4ECDC4', '#45B7D1', '#FFA07A', '#98D8C8', '#F7DC6F', '#BB8FCE']
x_positions = np.linspace(0, 10, len(elements))

# Dessiner les elements
for i, (elem, x, color) in enumerate(zip(elements, x_positions, colors)):
    circle = plt.Circle((x, 2), 0.4, color=color, alpha=0.7)
    ax.add_patch(circle)
    ax.text(x, 2, elem, ha='center', va='center', fontweight='bold', fontsize=12)
    
# Dessiner les sous-ensembles solution
solution_sets = [
    ([0, 3], 'S2 = {1, 4}', '#FF6B6B'),    # Elements 0 et 3
    ([2, 4, 5], 'S4 = {3, 5, 6}', '#4ECDC4'),  # Elements 2, 4, 5
    ([1, 6], 'S6 = {2, 7}', '#45B7D1')     # Elements 1 et 6
]

y_offset = 0
for indices, label, color in solution_sets:
    # Dessiner la ligne reliant les elements
    x_coords = [x_positions[i] for i in indices]
    y = y_offset
    
    # Ligne horizontale
    ax.plot([min(x_coords), max(x_coords)], [y, y], color=color, linewidth=3, alpha=0.6)
    
    # Lignes verticales vers chaque element
    for x in x_coords:
        ax.plot([x, x], [y, 1.6], color=color, linewidth=2, linestyle='--', alpha=0.5)
        ax.plot(x, 1.6, 'o', color=color, markersize=8)
    
    # Label
    ax.text(5, y + 0.15, label, ha='center', fontsize=11, fontweight='bold', color=color)
    y_offset -= 0.8

ax.set_xlim(-0.5, 10.5)
ax.set_ylim(-2, 2.5)
ax.set_aspect('equal')
ax.axis('off')
ax.set_title('Couverture Exacte : {S2, S4, S6} couvrent U = {1,2,3,4,5,6,7}', 
             fontsize=14, fontweight='bold', pad=20)

plt.tight_layout()
plt.show()

print("\nProprietes de cette solution:")
print("  - Chaque element de U est couvert exactement une fois")
print("  - Les sous-ensembles sont disjoints (S2 ∩ S4 = ∅, S2 ∩ S6 = ∅, S4 ∩ S6 = ∅)")
print("  - C'est une solution valide au probleme de couverture exacte")


Proprietes de cette solution:
  - Chaque element de U est couvert exactement une fois
  - Les sous-ensembles sont disjoints (S2 ∩ S4 = ∅, S2 ∩ S6 = ∅, S4 ∩ S6 = ∅)
  - C'est une solution valide au probleme de couverture exacte

Interpretation : Visualisation de la couverture exacte

La visualisation illustre parfaitement le concept de couverture exacte.

Aspect Observation
Univers U 7 éléments representes par des cercles colores
Sous-ensembles 3 lignes colorees reliant les éléments
Disjonction Les 3 lignes ne se croisent pas (pas d’élément partage)
Couverture Tous les 7 éléments sont connectes a une ligne

Points cles : - Chaque élément de l’univers est couvert exactement une fois - Les sous-ensembles S2, S4, S6 sont disjoints (S2 ∩ S4 = ∅, S2 ∩ S6 = ∅, S4 ∩ S6 = ∅) - C’est une solution valide au problème de couverture exacte

Note technique : Cette visualisation met en evidence la propriete fondamentale de la couverture exacte : la disjonction des sous-ensembles selectionnes.

Applications de la couverture exacte

Le problème de couverture exacte est NP-complet, mais DLX permet de le resoudre efficacement pour de nombreuses instances pratiques.

Application Univers Sous-ensembles Explication
Sudoku Cellules x contraintes Placements de chiffres Chaque cellule doit avoir exactement un chiffre
Pavage (Polyominos) Cases de la grille Positions de pieces Chaque case doit etre couverte exactement une fois
Pentominoes Cases de la grille Positions de pieces Chaque case doit etre couverte exactement une fois
Exact Cover éléments donnes Sous-ensembles donnes problème general
Set packing éléments Sous-ensembles Variante avec objectifs différents

WARNING : N-Queens n’est PAS une couverture exacte ! Les diagonales ont des contraintes d’inegalite (au plus une reine), pas d’egalite. Le pavage est un exemple correct de couverture exacte.

Note : La capacite de modeliser de nombreux problemes comme couverture exacte fait de DLX un outil très polyvalent pour les problemes ou toutes les contraintes sont des egalites.

2. L’Algorithme X de Knuth (~15 min)

Principe de l’algorithme X

L’algorithme X, propose par Donald Knuth en 1979, est une approche récursive force brute pour resoudre le problème de couverture exacte. C’est essentiellement un backtracking optimise pour les matrices creuses.

Idee principale

  1. Si la matrice est vide (toutes les colonnes couvertes), succes
  2. Sinon, choisir une colonne \(c\) (heuristique: colonne avec le moins de 1)
  3. Choisir une ligne \(r\) avec un 1 dans la colonne \(c\)
  4. Ajouter \(r\) a la solution partielle
  5. Couvrir la colonne \(c\) et toutes les lignes conflictuelles
  6. Recursivement resoudre le problème reduit
  7. Si echec, decouvrir et essayer une autre ligne

Pseudo-code

Algorithm X(A):
    if A is empty:
        return success  # Solution trouvee
    
    # Choisir la colonne avec le minimum de 1 (heuristique)
    c = column with fewest 1s in A
    
    # Pour chaque ligne avec un 1 dans la colonne c
    for each row r with A[r][c] = 1:
        # Inclure r dans la solution partielle
        add r to partial_solution
        
        # Couvrir la colonne c et les lignes conflictuelles
        cover column c and related rows
        
        # Recursion
        if X(A_reduced) is success:
            return success
        
        # Backtrack
        uncover column c and related rows
        remove r from partial_solution
    
    return failure  # Aucune solution

opération de couverture (cover)

L’opération cover(c) elimine la colonne \(c\) et toutes les lignes qui ont un 1 dans cette colonne :

  1. Supprimer la colonne \(c\) de la matrice
  2. Pour chaque ligne \(r\) avec un 1 dans la colonne \(c\) :
    • Supprimer toutes les colonnes \(j\) ou \(A[r][j] = 1\)
    • Cela elimine toutes les lignes conflictuelles

Cela créé un sous-problème plus petit qui peut etre resolu recursivement.

Heuristique de choix de colonne

Knuth suggere de choisir la colonne avec le minimum de 1 car : - Moins de choix = moins de branches a explorer - Reduit la taille de l’arbre de recherche - Equivalent a l’heuristique MRV (Minimum Remaining Values) dans les CSP

# Implementation simple de l'algorithme X (sans Dancing Links)
def algorithm_x_simple(matrix: np.ndarray) -> List[int]:
    """
    Implementation simple de l'algorithme X pour la couverture exacte.
    
    Args:
        matrix: Matrice binaire (lignes = sous-ensembles, colonnes = elements)
    
    Returns:
        Liste des indices de lignes formant une solution, ou liste vide si pas de solution
    """
    def solve(matrix: np.ndarray, solution: List[int], row_idx: List[int]) -> Optional[List[int]]:
        # Cas de base : matrice vide = toutes les colonnes couvertes
        if matrix.shape[1] == 0:
            return solution.copy()
        
        # Choisir la colonne avec le minimum de 1 (heuristique)
        col_sums = np.sum(matrix, axis=0)
        if np.any(col_sums == 0):
            return None  # Colonne sans 1 = impossible
        
        c = np.argmin(col_sums + (col_sums == 0) * 9999)
        
        # Essayer chaque ligne avec un 1 dans la colonne c
        for r in np.where(matrix[:, c] == 1)[0]:
            # Ajouter la ligne a la solution
            new_solution = solution + [row_idx[r]]
            
            # Trouver les colonnes a couvrir (toutes avec un 1 dans la ligne r)
            cols_to_cover = np.where(matrix[r] == 1)[0]
            
            # Creer la matrice reduite
            rows_to_keep = np.ones(matrix.shape[0], dtype=bool)
            for col in cols_to_cover:
                rows_to_keep &= (matrix[:, col] == 0)
            
            cols_to_keep = np.ones(matrix.shape[1], dtype=bool)
            cols_to_keep[cols_to_cover] = False

            new_row_indices = [row_idx[i] for i in np.where(rows_to_keep)[0]]
            
            reduced_matrix = matrix[np.ix_(rows_to_keep, cols_to_keep)]
            
            # Recursion
            result = solve(reduced_matrix, new_solution, new_row_indices)
            if result is not None:
                return result
        
        return None
    
    return solve(matrix, [], list(range(matrix.shape[0])))

# Tester sur notre exemple
matrix_test = np.array([
    [1, 0, 0, 1, 0, 0, 1],  # S1
    [1, 0, 0, 1, 0, 0, 0],  # S2
    [0, 0, 0, 1, 1, 0, 1],  # S3
    [0, 0, 1, 0, 1, 1, 0],  # S4
    [0, 1, 1, 0, 0, 1, 1],  # S5
    [0, 1, 0, 0, 0, 0, 1],  # S6
])

print("Algorithme X simple (implementation naive)")
print("=" * 50)

start_time = time.perf_counter()
solution = algorithm_x_simple(matrix_test)
elapsed = (time.perf_counter() - start_time) * 1000

if solution:
    print(f"Solution trouvee: {[f'S{i+1}' for i in solution]}")
    print(f"Solution attendue: ['S2', 'S4', 'S6']")
    print(f"Temps de recherche: {elapsed:.3f} ms")
else:
    print("Aucune solution trouvee")
Algorithme X simple (implementation naive)
==================================================
Solution trouvee: ['S2', 'S4', 'S6']
Solution attendue: ['S2', 'S4', 'S6']
Temps de recherche: 0.806 ms

Interpretation : Algorithme X simple

L’algorithme X trouve correctement la solution {S2, S4, S6}.

Aspect Observation
Solution {S2, S4, S6} comme attendu
Complexite Fonctionne mais creation de nouvelles matrices a chaque recursion
Efficacite Peu efficace pour les grandes matrices

Limitations de cette implementation : - Creation de nouvelles matrices a chaque recursion (couteux) - Recopie de données inutile - Pas de structure de données optimisee pour les matrices creuses

C’est précisément pour resoudre ces problemes que Knuth a invente Dancing Links.

Exercice 1 : Implementer l’heuristique MRV pour le choix de colonne

L’heuristique MRV (Minimum Remaining Values) consiste a choisir la colonne avec le moins de 1 restants, car elle offre le moins de choix possibles et donc reduit l’arbre de recherche.

La fonction algorithm_x_simple utilise déjà cette heuristique via np.argmin(col_sums). Implementez votre propre fonction choose_column_mrv qui :

  1. Parcourt toutes les colonnes de la matrice
  2. Pour chaque colonne, compte le nombre de 1
  3. Retourne l’index de la colonne avec le minimum de 1 (strictement positif)
  4. Si une colonne a 0 choix, retourne -1 (impossible)

Indices : - Utilisez np.sum(matrix, axis=0) pour obtenir le nombre de 1 par colonne - Eliminez les colonnes avec 0 choix (erreur) avec un masque booléen - Testez votre fonction sur matrix_test définie precedemment — la colonne avec le moins de 1 est la colonne 1 (index 1, deux 1)

Pourquoi c’est important : Sans MRV, l’algorithme explore beaucoup plus de branches inutiles. C’est l’equivalent du “fail-first” dans les CSP.

def choose_column_mrv(matrix: np.ndarray) -> int:
    """Choisit la colonne avec le moins de 1 (heuristique MRV).

    Args:
        matrix: Matrice binaire de shape (n_rows, n_cols)

    Returns:
        Index de la colonne avec le minimum de 1 (strictement positif),
        ou -1 si une colonne a 0 choix (impossible)
    """
    # TODO etudiant : implementer l'heuristique MRV
    # Etape 1 : compter les 1 par colonne
    # Etape 2 : si une colonne a 0 choix, retourner -1
    # Etape 3 : trouver la colonne avec le minimum positif
    return -1  # TODO etudiant : remplacer par l'implementation

print("Exercice a completer : heuristique MRV pour le choix de colonne")
Exercice a completer : heuristique MRV pour le choix de colonne

Exercice 2 : Verifier une solution de couverture exacte

Etant donnee une matrice binaire et un ensemble de lignes suppose etre une solution, implementez une fonction is_exact_cover qui verifie que : 1. Chaque colonne est couverte exactement une fois (somme = 1) 2. Aucune colonne n’est decouverte (somme = 0) 3. Aucune colonne n’est sur-couverte (somme > 1)

Indices : - Selectionnez les lignes de la solution dans la matrice avec matrix[solution_rows] - Utilisez np.sum(axis=0) pour obtenir le nombre de 1 par colonne - Verifiez que le résultat est un vecteur de 1 partout avec np.all(result == 1)

def is_exact_cover(matrix: np.ndarray, solution_rows: List[int]) -> bool:
    """Verifie qu'un ensemble de lignes forme une couverture exacte de la matrice.

    Args:
        matrix: Matrice binaire (numpy array) de shape (n_rows, n_cols)
        solution_rows: Liste des indices de lignes selectionnees

    Returns:
        True si les lignes forment une couverture exacte, False sinon
    """
    # TODO etudiant : implementer la verification
    # Etape 1 : extraire les lignes de la solution
    # Etape 2 : sommer les colonnes
    # Etape 3 : verifier que chaque colonne a exactement un 1
    return False  # TODO etudiant : remplacer par la verification

print("Exercice a completer : verification d'une couverture exacte")
Exercice a completer : verification d'une couverture exacte

3. Dancing Links - La Structure de données (~20 min)

L’idee geniale de Knuth

Donald Knuth a propose d’utiliser des listes doublement liees circulaires pour representer la matrice creuse. Cette structure permet d’effectuer les opérations cover/uncover en temps constant O(1).

Structure de données

Chaque noeud dans la matrice a 4 pointeurs : - L (Left) : noeud a gauche - R (Right) : noeud a droite - U (Up) : noeud au-dessus - D (Down) : noeud en-dessous

Les noeuds sont organises en : - Listes horizontales : les 1 dans une ligne - Listes verticales : les 1 dans une colonne - Circulaires : le dernier pointe vers le premier

Types de noeuds

Type rôle Champs supplementaires
ColumnNode Tete de colonne name, size (nombre de 1 dans la colonne)
DataNode 1 dans la matrice C (pointeur vers sa colonne)
Header Racine de la structure Pointeur vers la première colonne 
# Visualisation de la structure Dancing Links
fig, ax = plt.subplots(figsize=(12, 8))

# Matrice exemple pour la visualisation
#    A  B  C  D
# S1 1  0  0  1
# S2 0  1  1  0
# S3 1  0  1  0

# Positions des colonnes
col_x = [2, 4, 6, 8]
col_names = ['A', 'B', 'C', 'D']

# Dessiner les tetes de colonne (ColumnNode)
for x, name in zip(col_x, col_names):
    rect = plt.Rectangle((x-0.3, 6), 0.6, 0.8, 
                          facecolor='#FF6B6B', edgecolor='black', linewidth=2)
    ax.add_patch(rect)
    ax.text(x, 6.4, name, ha='center', va='center', fontsize=12, fontweight='bold')
    ax.text(x, 7, f'ColumnNode\n{name}', ha='center', va='bottom', fontsize=9)

# Dessiner les noeuds de donnees (DataNode)
# S1: positions aux colonnes A et D
nodes_s1 = [(0, 4.5), (3, 4.5)]
# S2: positions aux colonnes B et C
nodes_s2 = [(1, 2.5), (2, 2.5)]
# S3: positions aux colonnes A et C
nodes_s3 = [(0, 0.5), (2, 0.5)]

# Dessiner les noeuds de donnees
all_rows = [(nodes_s1, 'S1', 4.5), (nodes_s2, 'S2', 2.5), (nodes_s3, 'S3', 0.5)]

for nodes, label, y in all_rows:
    # Label de ligne
    ax.text(0.5, y, label, ha='center', va='center', fontsize=12, 
            fontweight='bold', bbox=dict(boxstyle='round', facecolor='wheat'))
    
    # Dessiner les noeuds
    for col_idx, y_node in nodes:
        x = col_x[col_idx]
        circle = plt.Circle((x, y), 0.35, facecolor='#4ECDC4', 
                           edgecolor='black', linewidth=2, zorder=3)
        ax.add_patch(circle)
        ax.text(x, y, '1', ha='center', va='center', fontsize=10, fontweight='bold')

# Dessiner les liens verticaux (colonnes)
link_color = '#45B7D1'
# Colonne A: header -> S1 -> S3 -> header
ax.plot([2, 2], [6, 4.5], color=link_color, linewidth=2, linestyle='-', alpha=0.7)
ax.plot([2, 2], [4.5, 0.5], color=link_color, linewidth=2, linestyle='-', alpha=0.7)
ax.plot([2, 2], [0.5, 6], color=link_color, linewidth=2, linestyle='--', alpha=0.3)

# Colonne B: header -> S2 -> header
ax.plot([4, 4], [6, 2.5], color=link_color, linewidth=2, linestyle='-', alpha=0.7)
ax.plot([4, 4], [2.5, 6], color=link_color, linewidth=2, linestyle='--', alpha=0.3)

# Colonne C: header -> S2 -> S3 -> header
ax.plot([6, 6], [6, 2.5], color=link_color, linewidth=2, linestyle='-', alpha=0.7)
ax.plot([6, 6], [2.5, 0.5], color=link_color, linewidth=2, linestyle='-', alpha=0.7)
ax.plot([6, 6], [0.5, 6], color=link_color, linewidth=2, linestyle='--', alpha=0.3)

# Colonne D: header -> S1 -> header
ax.plot([8, 8], [6, 4.5], color=link_color, linewidth=2, linestyle='-', alpha=0.7)
ax.plot([8, 8], [4.5, 6], color=link_color, linewidth=2, linestyle='--', alpha=0.3)

# Dessiner les liens horizontaux (lignes)
row_link_color = '#FFA07A'
# S1: A -> D -> A
ax.plot([2, 8], [4.5, 4.5], color=row_link_color, linewidth=2, linestyle='-', alpha=0.7)
ax.plot([8, 2], [4.5, 4.5], color=row_link_color, linewidth=2, linestyle='--', alpha=0.3)

# S2: B -> C -> B
ax.plot([4, 6], [2.5, 2.5], color=row_link_color, linewidth=2, linestyle='-', alpha=0.7)
ax.plot([6, 4], [2.5, 2.5], color=row_link_color, linewidth=2, linestyle='--', alpha=0.3)

# S3: A -> C -> A
ax.plot([2, 6], [0.5, 0.5], color=row_link_color, linewidth=2, linestyle='-', alpha=0.7)
ax.plot([6, 2], [0.5, 0.5], color=row_link_color, linewidth=2, linestyle='--', alpha=0.3)

# Legendes
ax.text(5, 5.2, 'Liens verticaux (colonnes)\nU/D', ha='center', fontsize=9, 
        color=link_color, fontweight='bold')
ax.text(5, 3.2, 'Liens horizontaux (lignes)\nL/R', ha='center', fontsize=9, 
        color=row_link_color, fontweight='bold')

# Annotations
ax.annotate('', xy=(2.5, 6.8), xytext=(3.5, 6.8),
            arrowprops=dict(arrowstyle='<->', color='black', lw=1.5))
ax.text(3, 7.2, 'L/R', ha='center', fontsize=8)

ax.annotate('', xy=(2.3, 5.5), xytext=(2.3, 5),
            arrowprops=dict(arrowstyle='<->', color='black', lw=1.5))
ax.text(1.7, 5.2, 'U/D', ha='center', fontsize=8)

ax.set_xlim(0, 10)
ax.set_ylim(-0.5, 7.5)
ax.set_aspect('equal')
ax.axis('off')
ax.set_title('Structure Dancing Links : Listes doublement liees circulaires', 
             fontsize=14, fontweight='bold')

plt.tight_layout()
plt.show()

print("Structure Dancing Links:")
print("  - Chaque noeud a 4 pointeurs: L (left), R (right), U (up), D (down)")
print("  - Les listes sont circulaires (le dernier pointe vers le premier)")
print("  - Les ColumnNode (rouge) sont les tetes de colonne")
print("  - Les DataNode (turquoise) representent les 1 dans la matrice")
print("  - Liens bleus: colonnes (verticaux)")
print("  - Liens oranges: lignes (horizontaux)")

Structure Dancing Links:
  - Chaque noeud a 4 pointeurs: L (left), R (right), U (up), D (down)
  - Les listes sont circulaires (le dernier pointe vers le premier)
  - Les ColumnNode (rouge) sont les tetes de colonne
  - Les DataNode (turquoise) representent les 1 dans la matrice
  - Liens bleus: colonnes (verticaux)
  - Liens oranges: lignes (horizontaux)

Cette section presente la structure de données ingenieuse inventee par Donald Knuth. Nous allons comprendre comment les listes doublement liees circulaires permettent d’effectuer les opérations de couverture et decouverte en temps constant O(1).

Points cles : - Chaque noeud a 4 pointeurs (L, R, U, D) - Les listes sont circulaires (le dernier pointe vers le premier) - Les opérations cover/uncover sont inverses exactes

opérations cover et uncover

La puissance de Dancing Links reside dans les opérations cover et uncover qui travaillent en temps constant O(1).

opération cover(c)

def cover(column):
    # 1. Detacher la colonne de la liste des colonnes
    column.L.R = column.R
    column.R.L = column.L
    
    # 2. Pour chaque ligne i qui a un 1 dans la colonne c
    for i in column.down:
        # Pour chaque colonne j où la ligne i a un 1
        for j in i.right:
            # Detacher le noeud de sa colonne
            j.U.D = j.D
            j.D.U = j.U
            j.C.size -= 1

opération uncover(c) - L’opération inverse!

def uncover(column):
    # L'ordre inverse est CRUCIAL pour restaurer l'etat exact
    for i in column.up:
        for j in i.left:
            j.C.size += 1
            j.U.D = j
            j.D.U = j
    
    # Rattacher la colonne
    column.L.R = column
    column.R.L = column

Point cle : uncover fait exactement l’inverse de cover, dans l’ordre inverse. Cela garantit que la structure retrouve exactement son etat initial.

4. Implementation Python de DLX (~25 min)

Implantons maintenant l’algorithme X avec Dancing Links en Python. Nous allons définir les classes pour les noeuds et les opérations cover/uncover.

# Classes pour la structure Dancing Links

class ColumnNode:
    """Noeud representant une colonne (tete de colonne)."""
    
    def __init__(self, name: str):
        self.name = name
        self.size = 0  # Nombre de 1 dans cette colonne
        # Les 4 pointeurs (initialement pointent vers eux-mêmes)
        self.L = self
        self.R = self
        self.U = self
        self.D = self
        self.C = self  # Pointeur vers la colonne elle-même
    
    def __repr__(self):
        return f"ColumnNode({self.name}, size={self.size})"


class DataNode:
    """Noeud representant un 1 dans la matrice."""
    
    def __init__(self, column: ColumnNode):
        # Les 4 pointeurs
        self.L = self
        self.R = self
        self.U = self
        self.D = self
        self.C = column  # Pointeur vers sa colonne
    
    def __repr__(self):
        return f"DataNode(col={self.C.name})"


class Header(ColumnNode):
    """Racine de la structure Dancing Links."""
    
    def __init__(self):
        super().__init__("ROOT")
        # Le header pointe vers lui-même
        self.L = self
        self.R = self

print("Classes Dancing Links definies:")
print("  - ColumnNode: Tete de colonne avec compteur de taille")
print("  - DataNode: Noeud de donnee representant un 1")
print("  - Header: Racine de la structure")
Classes Dancing Links definies:
  - ColumnNode: Tete de colonne avec compteur de taille
  - DataNode: Noeud de donnee representant un 1
  - Header: Racine de la structure

opérations cover et uncover

# Operations cover et uncover

def cover(column: ColumnNode):
    """
    Couvre une colonne dans la structure Dancing Links.
    
    Detache la colonne de la liste des colonnes et detache toutes les lignes
    qui ont un 1 dans cette colonne.
    """
    # Detacher la colonne de la liste horizontale des colonnes
    column.L.R = column.R
    column.R.L = column.L
    
    # Pour chaque noeud dans la colonne (chaque ligne avec un 1)
    i = column.D
    while i != column:
        # Pour chaque noeud a droite (dans la meme ligne)
        j = i.R
        while j != i:
            # Detacher le noeud de sa colonne verticale
            j.D.U = j.U
            j.U.D = j.D
            j.C.size -= 1  # Decremente le compteur de la colonne
            j = j.R
        i = i.D


def uncover(column: ColumnNode):
    """
    Decouvre une colonne (operation inverse de cover).
    
    IMPORTANT: L'ordre inverse est crucial pour restaurer exactement l'etat.
    """
    i = column.U
    while i != column:
        j = i.L
        while j != i:
            j.C.size += 1  # Incremente le compteur (inverse de cover)
            j.D.U = j
            j.U.D = j
            j = j.L
        i = i.U
    
    # Rattacher la colonne a la liste horizontale
    column.L.R = column
    column.R.L = column

print("Operations cover/uncover definies.")
print("cover: Detache une colonne et ses lignes conflictuelles")
print("uncover: Restaure exactement l'etat (operation inverse)")
Operations cover/uncover definies.
cover: Detache une colonne et ses lignes conflictuelles
uncover: Restaure exactement l'etat (operation inverse)

Avec la structure de données définie (ColumnNode et DataNode), nous allons maintenant implémenter les opérations clés cover et uncover qui permettent de manipuler cette structure de manière efficace.

# Construction de la structure Dancing Links a partir d'une matrice

def build_dlx_structure(matrix: np.ndarray) -> Header:
    """
    Construit la structure Dancing Links a partir d'une matrice binaire.
    
    Args:
        matrix: Matrice binaire (lignes = sous-ensembles, colonnes = elements)
    
    Returns:
        Header pointant vers la structure DLX
    """
    n_rows, n_cols = matrix.shape
    
    # Creer le header
    header = Header()
    
    # Creer les colonnes
    columns = [ColumnNode(str(i)) for i in range(n_cols)]
    
    # Relier les colonnes horizontalement
    for i in range(n_cols):
        columns[i].L = columns[i-1] if i > 0 else header
        columns[i].R = columns[i+1] if i < n_cols-1 else header
    
    header.R = columns[0]
    header.L = columns[-1]
    
    # Creer les noeuds de donnees pour chaque 1
    row_nodes = []  # Garder une trace des noeuds de chaque ligne
    
    for row_idx in range(n_rows):
        first_in_row = None
        prev_in_row = None
        
        for col_idx in range(n_cols):
            if matrix[row_idx, col_idx] == 1:
                # Creer un noeud de donnee
                node = DataNode(columns[col_idx])
                
                # Ajouter a la colonne (verticalement)
                node.U = columns[col_idx].U
                node.D = columns[col_idx]
                columns[col_idx].U.D = node
                columns[col_idx].U = node
                columns[col_idx].size += 1
                
                # Relier horizontalement dans la ligne
                if first_in_row is None:
                    first_in_row = node
                if prev_in_row is not None:
                    node.L = prev_in_row
                    prev_in_row.R = node
                
                prev_in_row = node
        
        # Fermer la boucle horizontale de la ligne
        if first_in_row is not None and prev_in_row is not None:
            first_in_row.L = prev_in_row
            prev_in_row.R = first_in_row
            row_nodes.append(first_in_row)
    
    return header

# Tester la construction
matrix_test = np.array([
    [1, 0, 0, 1, 0, 0, 1],  # S1
    [1, 0, 0, 1, 0, 0, 0],  # S2
    [0, 0, 0, 1, 1, 0, 1],  # S3
    [0, 0, 1, 0, 1, 1, 0],  # S4
    [0, 1, 1, 0, 0, 1, 1],  # S5
    [0, 1, 0, 0, 0, 0, 1],  # S6
])

print("Construction de la structure DLX...")
header = build_dlx_structure(matrix_test)

# Verifier les colonnes
col = header.R
print("\nColonnes creees:")
while col != header:
    print(f"  {col.name}: size={col.size}")
    col = col.R

print("\nStructure DLX construite avec succes!")
Construction de la structure DLX...

Colonnes creees:
  0: size=2
  1: size=2
  2: size=2
  3: size=3
  4: size=2
  5: size=2
  6: size=4

Structure DLX construite avec succes!

Avec la structure de données définie, nous allons maintenant implémenter les opérations clés cover et uncover.

# Algorithme X avec Dancing Links (DLX)

def search(header: Header, solution: List, k: int = 0) -> bool:
    """
    Algorithme X avec Dancing Links.
    
    Args:
        header: Racine de la structure DLX
        solution: Liste pour stocker la solution partielle
        k: Profondeur de recursion
    
    Returns:
        True si une solution est trouvee, False sinon
    """
    # Cas de base : pas de colonnes restantes = solution trouvee
    if header.R == header:
        return True
    
    # Choisir la colonne avec le minimum de 1 (heuristique)
    # C'est comme MRV (Minimum Remaining Values) dans les CSP
    c = None
    min_size = float('inf')
    
    j = header.R
    while j != header:
        if j.size < min_size:
            min_size = j.size
            c = j
        j = j.R
    
    # Si une colonne a size=0, pas de solution possible
    if min_size == 0:
        return False
    
    # Couvrir la colonne choisie
    cover(c)
    
    # Essayer chaque ligne avec un 1 dans cette colonne
    r = c.D
    while r != c:
        # Ajouter la ligne a la solution
        solution.append(r)
        
        # Couvrir toutes les colonnes de cette ligne
        j = r.R
        while j != r:
            cover(j.C)
            j = j.R
        
        # Recursion
        if search(header, solution, k + 1):
            return True
        
        # Backtrack : decouvrir
        r = solution.pop()
        j = r.L
        while j != r:
            uncover(j.C)
            j = j.L
        
        r = r.D
    
    # Decouvrir la colonne avant de retourner
    uncover(c)
    return False


def solve_exact_cover(matrix: np.ndarray) -> Optional[List[int]]:
    """
    Resout un probleme de couverture exacte avec DLX.
    
    Args:
        matrix: Matrice binaire (lignes = sous-ensembles, colonnes = elements)
    
    Returns:
        Liste des indices de lignes solution, ou None si pas de solution
    """
    # Pour retrouver les indices des lignes, on doit les stocker lors de la construction
    # Ici on va modifier build_dlx_structure pour stocker les row_indices
    
    header, row_indices = build_dlx_structure_with_indices(matrix)
    solution_nodes = []
    
    if search(header, solution_nodes):
        # Retrouver les indices des lignes
        # On doit stocker les row_index dans les noeuds...
        # Pour simplifier, on va retourner les noeuds eux-memes
        return solution_nodes
    return None


def build_dlx_structure_with_indices(matrix: np.ndarray):
    """Version modifiee qui stocke les indices des lignes."""
    n_rows, n_cols = matrix.shape
    
    header = Header()
    columns = [ColumnNode(str(i)) for i in range(n_cols)]
    
    for i in range(n_cols):
        columns[i].L = columns[i-1] if i > 0 else header
        columns[i].R = columns[i+1] if i < n_cols-1 else header
    
    header.R = columns[0]
    header.L = columns[-1]
    
    row_nodes = []  # Premier noeud de chaque ligne
    row_indices = []  # Indices des lignes
    
    for row_idx in range(n_rows):
        first_in_row = None
        prev_in_row = None
        
        for col_idx in range(n_cols):
            if matrix[row_idx, col_idx] == 1:
                node = DataNode(columns[col_idx])
                node.row_index = row_idx  # Stocker l'index de la ligne
                
                node.U = columns[col_idx].U
                node.D = columns[col_idx]
                columns[col_idx].U.D = node
                columns[col_idx].U = node
                columns[col_idx].size += 1
                
                if first_in_row is None:
                    first_in_row = node
                if prev_in_row is not None:
                    node.L = prev_in_row
                    prev_in_row.R = node
                
                prev_in_row = node
        
        if first_in_row is not None:
            first_in_row.L = prev_in_row
            prev_in_row.R = first_in_row
            row_nodes.append(first_in_row)
            row_indices.append(row_idx)
    
    return header, row_nodes

# Version finale qui retourne les indices de lignes
def solve_dlx(matrix: np.ndarray) -> Optional[List[int]]:
    """Resout la couverture exacte avec DLX et retourne les indices de lignes."""
    header, _ = build_dlx_structure_with_indices(matrix)
    solution_nodes = []
    
    if search(header, solution_nodes):
        # Extraire les row_index des noeuds solution
        return [node.row_index for node in solution_nodes]
    return None

# Tester DLX
print("Algorithme X avec Dancing Links (DLX)")
print("=" * 50)

start_time = time.perf_counter()
solution_dlx = solve_dlx(matrix_test)
elapsed_dlx = (time.perf_counter() - start_time) * 1000

if solution_dlx:
    print(f"Solution DLX: {[f'S{i+1}' for i in solution_dlx]}")
    print(f"Solution attendue: ['S2', 'S4', 'S6']")
    print(f"Temps: {elapsed_dlx:.3f} ms")
else:
    print("Aucune solution trouvee")
Algorithme X avec Dancing Links (DLX)
==================================================
Solution DLX: ['S2', 'S4', 'S6']
Solution attendue: ['S2', 'S4', 'S6']
Temps: 0.104 ms

Après avoir défini les opérations cover et uncover, nous allons construire la structure Dancing Links complète.

Interpretation : Implementation DLX

L’implementation DLX trouve correctement la solution {S2, S4, S6}.

Aspect Observation
Solution {S2, S4, S6} comme attendu
Performance Beaucoup plus rapide que l’algorithme X naive
Structure Pas de recopie de matrice, opérations O(1)

Avantages de DLX par rapport a l’algorithme X naive : - Pas d’allocation memoire : pas de creation de nouvelles matrices - opérations O(1) : cover/uncover en temps constant - Backtracking efficace : uncover restaure exactement l’etat - Matrices creuses : ne stocke que les 1, pas les 0

Point cle : La structure circulaire et le fait que uncover soit l’inverse exact de cover garantissent que le backtracking fonctionne correctement.

Exercice 3 : Compter toutes les solutions d’un problème de couverture exacte

La fonction solve_dlx s’arrete a la première solution trouvee. Modifiez l’algorithme pour compter le nombre total de solutions d’un problème de couverture exacte.

Indices : - Inspirez-vous de la fonction search(header, solution, k) définie ci-dessus - Au lieu de retourner True a la première solution, incrementez un compteur et continuez l’exploration - Utilisez une variable count passée par reference (liste mutable [0]) pour accumuler le résultat - La condition d’arret change : on n’arrete jamais prematurely, on explore toutes les branches - Testez sur la matrice matrix_test (6x7) définie precedemment — le résultat attendu est 1 solution unique

def count_all_solutions(matrix: np.ndarray) -> int:
    """Compte le nombre total de solutions d'un probleme de couverture exacte.

    Args:
        matrix: Matrice binaire (lignes = sous-ensembles, colonnes = elements)

    Returns:
        Nombre total de solutions distinctes
    """
    # TODO etudiant : implementer le comptage de toutes les solutions
    # Etape 1 : construire la structure DLX avec build_dlx_structure_with_indices
    # Etape 2 : modifier la fonction search pour compter au lieu de s'arreter
    # Etape 3 : lancer la recherche exhaustive et retourner le compteur
    return 0  # TODO etudiant : remplacer par le vrai comptage

print("Exercice a completer : comptage de toutes les solutions")
Exercice a completer : comptage de toutes les solutions

5. Application - Sudoku Solver (~10 min)

Le Sudoku est l’une des applications les plus celebres de Dancing Links. Un Sudoku 9x9 peut etre modelise comme un problème de couverture exacte.

Modelisation Sudoku comme couverture exacte

Pour un Sudoku 9x9 standard : - 9 x 9 x 9 = 729 possibilites (chaque case peut contenir chaque chiffre) - 4 x 81 = 324 contraintes : - Contrainte de ligne : 9 lignes x 9 chiffres = 81 - Contrainte de colonne : 9 colonnes x 9 chiffres = 81 - Contrainte de bloc : 9 blocs x 9 chiffres = 81 - Contrainte de cellule : 81 cases doivent etre remplies

Chaque placement (ligne, colonne, chiffre) satisfait 4 contraintes : 1. La case est remplie 2. La ligne contient le chiffre exactement une fois 3. La colonne contient le chiffre exactement une fois 4. Le bloc contient le chiffre exactement une fois

# Visualisation de la transformation Sudoku -> Couverture Exacte

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(14, 6))

# Sudoku 4x4 pour simplifier (9x9 serait trop grand)
sudoku_grid = np.array([
    [1, 0, 0, 2],
    [0, 0, 3, 0],
    [0, 4, 0, 0],
    [3, 0, 0, 1]
])

# Grille Sudoku
for i in range(4):
    for j in range(4):
        val = sudoku_grid[i, j]
        color = '#FFE5E5' if val != 0 else '#F0F0F0'
        rect = plt.Rectangle((j, 3-i), 1, 1, facecolor=color, edgecolor='black')
        ax1.add_patch(rect)
        if val != 0:
            ax1.text(j+0.5, 2.5-i, str(val), ha='center', va='center', 
                    fontsize=16, fontweight='bold')

# Grille de blocs 2x2
for i in range(3):
    ax1.axhline(i, color='black', linewidth=2)
for j in range(3):
    ax1.axvline(j, color='black', linewidth=2)

ax1.set_xlim(0, 4)
ax1.set_ylim(0, 4)
ax1.set_aspect('equal')
ax1.axis('off')
ax1.set_title('Sudoku 4x4', fontsize=14, fontweight='bold')

# Matrice de couverture exacte (simplifiee)
# Pour Sudoku 4x4:
# - 4*4*4 = 64 possibilites (chaque case peut avoir chaque chiffre 1-4)
# - 4 types de contraintes * 4 * 4 = 64 contraintes
# - Chaque placement satisfait 4 contraintes

# Extrait de la matrice (quelques lignes)
matrice_extrait = [
    [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0],  # (0,0,1): case (0,0), chiffre 1
    [0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0],  # (0,0,2)
    [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0],  # (0,1,3)
    [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],  # (1,2,3)
    [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0],  # (2,1,4)
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],  # (3,0,3)
]

# Afficher la matrice
for i, row in enumerate(matrice_extrait[:6]):
    for j, val in enumerate(row):
        if val == 1:
            color = '#4CAF50'
        else:
            color = '#E0E0E0'
        rect = plt.Rectangle((j, 5.5-i), 1, 1, facecolor=color, edgecolor='gray', linewidth=0.5)
        ax2.add_patch(rect)

ax2.set_xlim(0, 16)
ax2.set_ylim(0, 6)
ax2.set_aspect('equal')
ax2.axis('off')

# Annotations
ax2.text(8, 6.2, 'Matrice de Couverture Exacte', ha='center', fontsize=12, fontweight='bold')
ax2.text(8, -0.5, 'Colonnes: Cellules | Lignes | Colonnes | Blocs', ha='center', fontsize=9)
ax2.text(8, -1, 'Lignes: Placements (ligne, colonne, chiffre)', ha='center', fontsize=9)

# Legendes des colonnes
col_labels = ['C00', 'C01', 'C02', 'C03', 'L0-1', 'L0-2', 'L1-3', 'L1-4', 
              'Col0-1', 'Col1-3', 'Col1-4', 'Col3-3', 'B0-1', 'B1-3', 'B2-4', 'B3-3']
for j, label in enumerate(col_labels):
    ax2.text(j+0.5, 5.7, label, ha='center', va='bottom', fontsize=6, rotation=45)

row_labels = ['(0,0,1)', '(0,0,2)', '(0,1,3)', '(1,2,3)', '(2,1,4)', '(3,0,3)']
for i, label in enumerate(row_labels):
    ax2.text(-0.5, 5-i, label, ha='right', va='center', fontsize=7)

plt.suptitle('Transformation Sudoku -> Probleme de Couverture Exacte', 
             fontsize=14, fontweight='bold')
plt.tight_layout()
plt.show()

print("\nTransformation Sudoku en Couverture Exacte:")
print("  - Chaque placement (ligne, colonne, chiffre) devient une ligne de la matrice")
print("  - Chaque contrainte devient une colonne de la matrice")
print("  - Un 1 indique que le placement satisfait la contrainte")
print("  - Solution: selectionner des lignes pour couvrir toutes les colonnes exactement une fois")


Transformation Sudoku en Couverture Exacte:
  - Chaque placement (ligne, colonne, chiffre) devient une ligne de la matrice
  - Chaque contrainte devient une colonne de la matrice
  - Un 1 indique que le placement satisfait la contrainte
  - Solution: selectionner des lignes pour couvrir toutes les colonnes exactement une fois

Interpretation : Transformation Sudoku en couverture exacte

La visualisation illustre comment un Sudoku 4x4 est transforme en problème de couverture exacte.

Aspect Sudoku 4x4 Sudoku 9x9 (standard)
Placements possibles 64 (4x4x4) 729 (9x9x9)
Contraintes 64 324
Lignes de matrice 64 729
Colonnes de matrice 64 324

Points cles : - Chaque placement satisfait exactement 4 contraintes - La solution est une sélection de lignes couvrant chaque colonne exactement une fois - DLX trouve toutes les solutions possibles

Note technique : Pour un Sudoku 9x9 avec des chiffres donnes, on elimine les lignes correspondant aux placements impossibles. Cela reduit significativement la taille de la matrice.

Le Sudoku est l’une des applications les plus celebres de Dancing Links. Cette section presente la modelisation du Sudoku comme problème de couverture exacte.

Transformation : - Chaque placement (ligne, colonne, chiffre) devient une ligne de la matrice - Chaque contrainte (cellule, ligne, colonne, bloc) devient une colonne - Solution = 81 placements pour couvrir exactement 324 contraintes

Note importante sur Sudoku

Une implementation complete de Sudoku avec DLX necessite : 1. La construction de la matrice 729 x 324 (pour Sudoku 9x9) 2. La prise en compte des chiffres donnes (contraintes initiales) 3. L’extraction de la solution DLX vers une grille resolue

Cette implementation complete est presentee dans le notebook dedie : Sudoku-02-DancingLinks-Python

Concept Description
Liaison Sudoku-DLX Chaque placement (r,c,v) satisfait 4 contraintes
Taille matrice 729 lignes (placements) x 324 colonnes (contraintes)
Performance DLX resout les Sudoku difficiles en < 1 seconde
Avantages Elegant, trouve toutes les solutions, adaptable aux variantes

6. Application - Pavage de Polyominos (~10 min)

Le problème de pavage avec des polyominos consiste a remplir une grille avec des formes données sans chevauchement. C’est un vrai problème de couverture exacte contrairement au N-Queens.

Pourquoi N-Queens n’est PAS une couverture exacte ?

WARNING : Erreur courante - Le problème N-Queens est souvent cite comme exemple de couverture exacte, mais c’est incorrect.

Le problème N-Queens a des contraintes de type différent : - Lignes et colonnes : exactement une reine (egalite) - Diagonales : au plus une reine (inegalite)

La couverture exacte requiert que chaque contrainte soit satisfaite exactement une fois. Pour N-Queens, les diagonales peuvent avoir zero reine, ce qui ne correspond pas au modèle.

Modelisation du pavage comme couverture exacte

Pour une grille de taille W x H avec des polyominos : - Chaque position possible de chaque polyomino devient une ligne - Les contraintes sont : - Chaque case de la grille doit etre couverte exactement une fois - Chaque polyomino doit etre utilise exactement une fois (optionnel)

C’est un vrai problème de couverture exacte car chaque case doit etre couverte exactement une fois.

# Construction de la matrice de pavage pour la couverture exacte

def build_tiling_matrix(grid_width: int, grid_height: int, polyominos: dict) -> np.ndarray:
    """
    Construit la matrice de couverture exacte pour un probleme de pavage.
    
    Args:
        grid_width: Largeur de la grille
        grid_height: Hauteur de la grille
        polyominos: Dictionnaire {nom: [(row, col), ...]} des formes
    
    Returns:
        Matrice binaire (lignes = placements, colonnes = contraintes)
    """
    placements = []
    
    # Generer tous les placements possibles pour chaque polyomino
    for poly_name, shape in polyominos.items():
        shape_array = np.array(shape)
        
        # Normaliser la forme
        min_coords = shape_array.min(axis=0)
        normalized = shape_array - min_coords
        shape_height = normalized[:, 0].max() + 1
        shape_width = normalized[:, 1].max() + 1
        
        # Essayer chaque position et chaque rotation
        for rotation in range(4):
            # Rotation de la forme
            rotated = normalized.copy()
            for _ in range(rotation):
                rotated = np.array([(c, shape_height - 1 - r) for r, c in rotated])
                shape_height, shape_width = shape_width, shape_height
            
            # Essayer chaque position dans la grille
            for start_row in range(grid_height - shape_height + 1):
                for start_col in range(grid_width - shape_width + 1):
                    # Calculer les cases couvertes
                    cells = [(r + start_row, c + start_col) for r, c in rotated]
                    
                    # Verifier que toutes les cases sont dans la grille
                    if all(0 <= r < grid_height and 0 <= c < grid_width for r, c in cells):
                        placements.append({
                            'name': poly_name,
                            'cells': cells,
                            'rotation': rotation
                        })
    
    # Nombre de contraintes : chaque case de la grille
    n_constraints = grid_width * grid_height
    n_placements = len(placements)
    
    # Construire la matrice
    matrix = np.zeros((n_placements, n_constraints), dtype=int)
    
    for i, placement in enumerate(placements):
        for row, col in placement['cells']:
            col_idx = row * grid_width + col
            matrix[i, col_idx] = 1
    
    return matrix, placements

# Exemple simple : paver une grille 3x3 avec des triominos (formes de 3 cases)
print("Exemple de pavage avec DLX")
print("=" * 50)

# Definir des triominos (formes de 3 cases)
triominos = {
    'I': [(0, 0), (1, 0), (2, 0)],  # Ligne verticale
    'L': [(0, 0), (1, 0), (1, 1)],  # Forme L
}

# Construire la matrice pour une grille 3x2
print("\nConstruction de la matrice pour grille 3x2 avec triominos...")
matrix_tiling, placements = build_tiling_matrix(3, 2, triominos)

print(f"Matrice: {matrix_tiling.shape[0]} placements possibles x {matrix_tiling.shape[1]} cases")
print(f"Nombre total de cases: {3 * 2} = 6")
print(f"Placements possibles: {len(placements)}")
print("\nExemple de placements:")
for i in range(min(5, len(placements))):
    p = placements[i]
    cells_str = ', '.join([f'({r},{c})' for r, c in p['cells']])
    print(f"  {p['name']} (rot={p['rotation']}): [{cells_str}]")
Exemple de pavage avec DLX
==================================================

Construction de la matrice pour grille 3x2 avec triominos...
Matrice: 10 placements possibles x 6 cases
Nombre total de cases: 6 = 6
Placements possibles: 10

Exemple de placements:
  I (rot=1): [(0,2), (0,1), (0,0)]
  I (rot=1): [(1,2), (1,1), (1,0)]
  L (rot=0): [(0,0), (1,0), (1,1)]
  L (rot=0): [(0,1), (1,1), (1,2)]
  L (rot=1): [(0,1), (0,0), (1,0)]

Cette section presente une application correcte de DLX : le problème de pavage avec des polyominos. Contrairement au N-Queens, c’est un vrai problème de couverture exacte.

Modelisation : - Chaque placement possible de polyomino est une ligne de la matrice - Les contraintes sont les cases de la grille (chaque case doit etre couverte exactement une fois) - C’est un problème de couverture exacte valide car chaque case doit etre couverte exactement une fois

# Resoudre un probleme de pavage avec DLX

def solve_tiling_dlx(grid_width: int, grid_height: int, polyominos: dict, max_solutions: int = 1) -> List[dict]:
    """
    Resout un probleme de pavage avec DLX.
    
    Args:
        grid_width: Largeur de la grille
        grid_height: Hauteur de la grille
        polyominos: Dictionnaire des formes
        max_solutions: Nombre maximum de solutions a trouver
    
    Returns:
        Liste de solutions (chaque solution est une liste de placements)
    """
    matrix, placements = build_tiling_matrix(grid_width, grid_height, polyominos)
    
    if len(placements) == 0:
        return []
    
    solution_indices = solve_dlx(matrix)
    
    if solution_indices is None:
        return []
    
    # Convertir les indices en placements
    solution = [placements[i] for i in solution_indices]
    return [solution]


def visualize_tiling_solution(grid_width: int, grid_height: int, solution: List[dict], polyominos: dict):
    """Visualise une solution de pavage."""
    fig, ax = plt.subplots(figsize=(8, 8))
    
    # Dessiner la grille
    for i in range(grid_height):
        for j in range(grid_width):
            rect = plt.Rectangle((j, grid_height-1-i), 1, 1, 
                                facecolor='#F0F0F0', edgecolor='gray', linewidth=1)
            ax.add_patch(rect)
    
    # Couleurs pour differents polyominos
    colors = ['#FF6B6B', '#4ECDC4', '#45B7D1', '#FFA07A', '#98D8C8', '#F7DC6F']
    
    # Dessiner les polyominos de la solution
    color_map = {}
    for idx, placement in enumerate(solution):
        name = placement['name']
        if name not in color_map:
            color_map[name] = colors[len(color_map) % len(colors)]
        color = color_map[name]
        
        for row, col in placement['cells']:
            rect = plt.Rectangle((col, grid_height-1-row), 1, 1, 
                                facecolor=color, edgecolor='black', linewidth=2, alpha=0.8)
            ax.add_patch(rect)
            
        # Marquer le centre du polyomino
        cells = placement['cells']
        center_row = sum(r for r, c in cells) / len(cells)
        center_col = sum(c for r, c in cells) / len(cells)
        ax.text(center_col, grid_height-1-center_row, name, 
               ha='center', va='center', fontsize=12, fontweight='bold', color='white', zorder=3)
    
    ax.set_xlim(0, grid_width)
    ax.set_ylim(0, grid_height)
    ax.set_aspect('equal')
    ax.axis('off')
    ax.set_title(f'Solution de Pavage ({grid_width}x{grid_height})', 
                fontsize=14, fontweight='bold')
    
    plt.tight_layout()
    plt.show()

# Resoudre pour differents problemes
print("Pavage avec DLX")
print("=" * 50)

# Probleme 1 : Grille 3x2 avec triominos
print("\nProbleme 1: Grille 3x2 avec triominos I et L")
print("-" * 40)
solutions_3x2 = solve_tiling_dlx(3, 2, triominos)
if solutions_3x2:
    print(f"Solution trouvee avec {len(solutions_3x2[0])} polyominos")
    for p in solutions_3x2[0]:
        cells_str = ', '.join([f'({r},{c})' for r, c in p['cells']])
        print(f"  {p['name']}: [{cells_str}]")
    visualize_tiling_solution(3, 2, solutions_3x2[0], triominos)
else:
    print("Aucune solution trouvee")

# Probleme 2 : Grille 4x4 avec tetra-ominoes (carres 2x2)
print("\nProbleme 2: Grille 4x4 avec carres 2x2")
print("-" * 40)
tetra_ominoes = {
    'O': [(0, 0), (0, 1), (1, 0), (1, 1)],  # Carre 2x2
}
solutions_4x4 = solve_tiling_dlx(4, 4, tetra_ominoes)
if solutions_4x4:
    print(f"Solution trouvee avec {len(solutions_4x4[0])} carres 2x2")
    visualize_tiling_solution(4, 4, solutions_4x4[0], tetra_ominoes)
else:
    print("Aucune solution trouvee")
Pavage avec DLX
==================================================

Probleme 1: Grille 3x2 avec triominos I et L
----------------------------------------
Solution trouvee avec 2 polyominos
  I: [(0,2), (0,1), (0,0)]
  I: [(1,2), (1,1), (1,0)]


Probleme 2: Grille 4x4 avec carres 2x2
----------------------------------------
Solution trouvee avec 4 carres 2x2

Interpretation : Pavage avec DLX

problème Solution trouvee Formes utilisees
Grille 3x2 Oui 2 triominos (deux I)
Grille 4x4 Oui 4 carres 2x2

Observations : - DLX trouve rapidement des solutions pour les problemes de pavage - La modelisation en couverture exacte est naturelle et correcte - Chaque case de la grille est couverte exactement une fois

Comparaison avec N-Queens : - Pavage : Vraie couverture exacte (chaque case doit etre couverte) - N-Queens : Couverture partielle (les diagonales peuvent etre vides)

Note technique : Le pavage est une application ideale pour DLX car les contraintes sont naturellement des egalites (chaque case doit etre couverte exactement une fois).

7. Application - Pentominoes (~5 min)

Les pentominos sont des formes composees de 5 carres connectes. Le problème de pavage consiste a remplir une grille avec des pentominos sans chevauchement.

Modelisation Pentominoes comme couverture exacte

Pour une grille de taille W x H et 12 pentominos (chaque pentomino peut etre utilise exactement une fois) : - Chaque position possible de chaque pentomino dans la grille devient une ligne - Les contraintes sont : - Chaque case de la grille doit etre couverte exactement une fois - Chaque pentomino doit etre utilise exactement une fois

Visualisation des 12 Pentominos

Les 12 pentominos standard sont nommes F, I, L, P, N, T, U, V, W, X, Y, Z selon leur forme.

# Visualisation des 12 Pentominos

# Definition des 12 pentominos (formes standard)
pentominos = {
    'F': [(0, 1), (0, 2), (1, 0), (1, 1), (2, 1)],
    'I': [(0, 0), (1, 0), (2, 0), (3, 0), (4, 0)],
    'L': [(0, 0), (1, 0), (2, 0), (3, 0), (3, 1)],
    'P': [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0)],
    'N': [(0, 1), (1, 1), (2, 0), (2, 1), (3, 0)],
    'T': [(0, 0), (0, 1), (0, 2), (1, 1), (2, 1)],
    'U': [(0, 0), (0, 2), (1, 0), (1, 1), (1, 2)],
    'V': [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)],
    'W': [(0, 0), (1, 0), (1, 1), (2, 1), (2, 2)],
    'X': [(0, 1), (1, 0), (1, 1), (1, 2), (2, 1)],
    'Y': [(0, 0), (1, 0), (2, 0), (3, 0), (2, 1)],
    'Z': [(0, 0), (0, 1), (1, 1), (1, 2), (1, 3)]
}

colors = {
    'F': '#FF6B6B', 'I': '#4ECDC4', 'L': '#45B7D1', 'P': '#FFA07A',
    'N': '#98D8C8', 'T': '#F7DC6F', 'U': '#BB8FCE', 'V': '#85C1E2',
    'W': '#F8C471', 'X': '#82E0AA', 'Y': '#F1948A', 'Z': '#BDC3C7'
}

fig, axes = plt.subplots(3, 4, figsize=(12, 9))
axes = axes.flatten()

for idx, (name, shape) in enumerate(pentominos.items()):
    ax = axes[idx]
    
    # Normaliser pour affichage
    shape_array = np.array(shape)
    min_coords = shape_array.min(axis=0)
    normalized = [(r - min_coords[0], c - min_coords[1]) for r, c in shape]
    
    # Dessiner le pentomino
    for r, c in normalized:
        rect = plt.Rectangle((c, 4-r), 1, 1, facecolor=colors[name], 
                             edgecolor='black', linewidth=2)
        ax.add_patch(rect)
    
    # Labels
    ax.set_xlim(-0.5, 5.5)
    ax.set_ylim(-0.5, 5.5)
    ax.set_aspect('equal')
    ax.axis('off')
    ax.set_title(f'Pentomino {name}', fontsize=14, fontweight='bold')

plt.suptitle('Les 12 Pentominos Standard', fontsize=16, fontweight='bold')
plt.tight_layout()
plt.show()

print("\nProprietes des pentominos:")
print("  - 12 formes differentes (lettres F, I, L, P, N, T, U, V, W, X, Y, Z)")
print("  - Chaque forme est composee de 5 carres connectes")
print("  - Certaines formes sont symetriques (I, X)")
print("  - Les pentominos peuvent etre rotates et retournees")
print("  - Probleme classique: paver une grille 6x10 avec les 12 pentominos")


Proprietes des pentominos:
  - 12 formes differentes (lettres F, I, L, P, N, T, U, V, W, X, Y, Z)
  - Chaque forme est composee de 5 carres connectes
  - Certaines formes sont symetriques (I, X)
  - Les pentominos peuvent etre rotates et retournees
  - Probleme classique: paver une grille 6x10 avec les 12 pentominos

Interpretation : Les 12 Pentominos

Les pentominos illustrent parfaitement comment un problème de pavage peut etre modelise comme couverture exacte.

Aspect Observation
Formes 12 pieces différentes, chacune composee de 5 carres
Symetries Certains pentominos sont symetriques (I, X), d’autres non
Transformations Chaque piece peut etre rotationnee et retournee
problème classique Paver une grille 6x10 avec les 12 pentominos (60 cases = 12 x 5)

Modelisation en couverture exacte : - Chaque position possible de chaque pentomino dans la grille devient une ligne - Les contraintes sont les cases de la grille (chaque case doit etre couverte exactement une fois) - Chaque pentomino doit etre utilise exactement une fois

Note technique : Le nombre de positions possibles croit rapidement avec la taille de la grille. Pour une grille 6x10, il y a des milliers de positions possibles pour chaque pentomino.

8. Comparaison de Performances (~10 min)

Comparons DLX avec d’autres méthodes de resolution de problemes de contraintes : backtracking classique et CSP avec OR-Tools.

méthodes comparees

méthode Principe Avantages Inconvenients
DLX Couverture exacte avec listes liees Elegant, pas de recopie, optimal pour matrices creuses Implementation complexe
Backtracking Exploration systématique avec retour Simple a implementer Recopie couteuse, lent
CSP (OR-Tools) Propagation de contraintes + backtracking Haut niveau, optimise dépendance externe 
# Implementation de backtracking classique pour le pavage

def solve_tiling_backtrack(grid_width: int, grid_height: int, polyominos: dict) -> Optional[List[dict]]:
    """Resout un probleme de pavage avec backtracking classique."""
    
    # Obtenir tous les placements possibles
    _, all_placements = build_tiling_matrix(grid_width, grid_height, polyominos)
    
    if not all_placements:
        return None
    
    n_cells = grid_width * grid_height
    covered = set()
    solution = []
    
    def backtrack(start_idx: int) -> bool:
        """Backtracking recursif."""
        if len(covered) == n_cells:
            return True
        
        for i in range(start_idx, len(all_placements)):
            placement = all_placements[i]
            cells = placement['cells']
            
            # Verifier si ce placement est valide
            if any((r * grid_width + c) in covered for r, c in cells):
                continue
            
            # Placer la piece
            for r, c in cells:
                covered.add(r * grid_width + c)
            solution.append(placement)
            
            if backtrack(i + 1):
                return True
            
            # Retirer la piece
            solution.pop()
            for r, c in cells:
                covered.remove(r * grid_width + c)
        
        return False
    
    if backtrack(0):
        return solution
    return None

# Benchmark comparatif
print("Comparaison DLX vs Backtracking pour le pavage")
print("=" * 60)

results = []

# Problemes de taille croissante
test_cases = [
    (3, 2, triominos, "3x2 triominos"),
    (4, 2, triominos, "4x2 triominos"),
    (4, 4, tetra_ominoes, "4x4 carres"),
]

for width, height, pieces, name in test_cases:
    # DLX
    start = time.perf_counter()
    sol_dlx = solve_tiling_dlx(width, height, pieces)
    time_dlx = (time.perf_counter() - start) * 1000
    
    # Backtracking
    start = time.perf_counter()
    sol_bt = solve_tiling_backtrack(width, height, pieces)
    time_bt = (time.perf_counter() - start) * 1000
    
    found_dlx = sol_dlx is not None and len(sol_dlx) > 0
    found_bt = sol_bt is not None and len(sol_bt) > 0
    
    results.append({
        'name': name,
        'dlx_time': time_dlx,
        'bt_time': time_bt,
        'dlx_found': found_dlx,
        'bt_found': found_bt
    })
    
    print(f"{name}:")
    print(f"  DLX:      {time_dlx:8.3f} ms  (solution: {found_dlx})")
    print(f"  Backtrack: {time_bt:8.3f} ms  (solution: {found_bt})")
    if time_bt > 0:
        print(f"  Ratio:    {time_dlx/time_bt:8.2f}x")
    print()
Comparaison DLX vs Backtracking pour le pavage
============================================================
3x2 triominos:
  DLX:         0.335 ms  (solution: True)
  Backtrack:    0.199 ms  (solution: True)
  Ratio:        1.68x

4x2 triominos:
  DLX:         0.397 ms  (solution: False)
  Backtrack:    0.531 ms  (solution: False)
  Ratio:        0.75x

4x4 carres:
  DLX:         0.752 ms  (solution: True)
  Backtrack:    0.349 ms  (solution: True)
  Ratio:        2.15x

Cette section compare l’efficacite de DLX avec d’autres méthodes classiques de resolution de problemes de contraintes. Nous allons implementer un backtracking classique pour le pavage et comparer les temps d’exécution.

Objectifs : - Mesurer la performance de DLX vs backtracking - Comprendre quand DLX est preferable - Identifier les limites de chaque approche

Note : Le pavage est un vrai problème de couverture exacte (contrairement au N-Queens qui a des contraintes d’inegalite sur les diagonales).

# Visualisation de la comparaison

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(14, 5))

# Temps d'execution
names = [r['name'] for r in results]
dlx_times = [r['dlx_time'] for r in results]
bt_times = [r['bt_time'] for r in results]

x_pos = np.arange(len(names))
width = 0.35

bars1 = ax1.bar(x_pos - width/2, dlx_times, width, label='DLX', color='#4CAF50', alpha=0.8)
bars2 = ax1.bar(x_pos + width/2, bt_times, width, label='Backtracking', color='#FF6B6B', alpha=0.8)

ax1.set_xlabel('Probleme', fontsize=12)
ax1.set_ylabel('Temps (ms)', fontsize=12)
ax1.set_title('Temps de resolution', fontsize=13, fontweight='bold')
ax1.set_xticks(x_pos)
ax1.set_xticklabels(names, rotation=15, ha='right')
ax1.legend(fontsize=11)
ax1.grid(axis='y', alpha=0.3)

# Ratio
ratios = [r['dlx_time']/r['bt_time'] if r['bt_time'] > 0 else 0 for r in results]
bars = ax2.bar(names, ratios, color=['#4CAF50' if r < 1 else '#FF6B6B' for r in ratios], alpha=0.7, edgecolor='black')
ax2.axhline(y=1, color='black', linestyle='--', linewidth=1, alpha=0.5)
ax2.set_xlabel('Probleme', fontsize=12)
ax2.set_ylabel('Ratio (DLX / Backtrack)', fontsize=12)
ax2.set_title('Ratio de performance', fontsize=13, fontweight='bold')
ax2.grid(axis='y', alpha=0.3)

# Annotations
for i, (name, ratio) in enumerate(zip(names, ratios)):
    if ratio > 0:
        ax2.text(i, ratio + 0.05, f'{ratio:.1f}x', ha='center', fontsize=9)

plt.suptitle('Comparaison DLX vs Backtracking - Probleme de Pavage', fontsize=14, fontweight='bold')
plt.tight_layout()
plt.show()

print("\nAnalyse des resultats:")
print("  - DLX a un cout fixe de construction de la structure")
print("  - Pour les petits problemes, backtracking peut etre plus rapide")
print("  - Pour les problemes plus complexes, DLX devient competitif")
print("  - La difference depend de la taille de la matrice de couverture exacte")


Analyse des resultats:
  - DLX a un cout fixe de construction de la structure
  - Pour les petits problemes, backtracking peut etre plus rapide
  - Pour les problemes plus complexes, DLX devient competitif
  - La difference depend de la taille de la matrice de couverture exacte
# Benchmark discriminant : pentominoes (la ou le DLX prend son avantage)

# Les instances triviales precedentes (triominos, carres) ne sollicitent pas
# reellement la recherche : le cout fixe de construction de la structure DLX
# (liste doublement chainee + heuristique MRV) depasse celui d'un backtracking
# quasi immediat. Pour reveler l'avantage du DLX, il faut un probleme dont
# l'arbre de recherche est assez vaste pour que la selection de colonne MRV et
# les operations cover/uncover en O(1) comptent reellement. Les pentominoes
# (formes de 5 carres, nombreuses positions possibles par piece) sont ce cas.

# Sous-ensemble de pentominoes (F asymetrique, desormais distinct de X)
pento_pavage = {
    'F': pentominos['F'],
    'L': pentominos['L'],
    'P': pentominos['P'],
    'Y': pentominos['Y'],
}

print("Benchmark : pavage par pentominoes (min de 3 executions)")
print("=" * 64)

instances = [
    (4, 5, "4x5 (F,L,P,Y)"),
    (5, 4, "5x4 (F,L,P,Y)"),
]

pento_res = []
for width, height, name in instances:
    mat, _ = build_tiling_matrix(width, height, pento_pavage)
    # DLX - meilleur de 3 runs
    t_dlx = None
    for _ in range(3):
        s = time.perf_counter(); solve_tiling_dlx(width, height, pento_pavage); e = time.perf_counter()
        t_dlx = (e - s) * 1000 if t_dlx is None else min(t_dlx, (e - s) * 1000)
    # Backtracking - meilleur de 3 runs
    t_bt = None
    for _ in range(3):
        s = time.perf_counter(); solve_tiling_backtrack(width, height, pento_pavage); e = time.perf_counter()
        t_bt = (e - s) * 1000 if t_bt is None else min(t_bt, (e - s) * 1000)
    ratio = t_dlx / t_bt
    winner = "DLX" if t_dlx < t_bt else "Backtrack"
    sol = solve_tiling_dlx(width, height, pento_pavage)
    used = sorted(set(p['name'] for p in sol[0]))
    pento_res.append((name, mat.shape, t_dlx, t_bt, ratio, winner, used))
    print(f"{name:18} matrice {mat.shape[0]}x{mat.shape[1]:3} | "
          f"DLX {t_dlx:7.2f} ms | Backtrack {t_bt:8.2f} ms | "
          f"ratio {ratio:5.2f} | {winner} gagne")
    print(f"                    pieces utilisees : {used}")

# Visualisation
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(13, 4.5))
labels = [r[0] for r in pento_res]
dlx_v = [r[2] for r in pento_res]
bt_v = [r[3] for r in pento_res]
xpos = np.arange(len(labels)); w = 0.35
ax1.bar(xpos - w/2, dlx_v, w, label='DLX', color='#4CAF50', alpha=0.8)
ax1.bar(xpos + w/2, bt_v, w, label='Backtracking', color='#FF6B6B', alpha=0.8)
ax1.set_xticks(xpos); ax1.set_xticklabels(labels, rotation=10, ha='right')
ax1.set_ylabel('Temps (ms)'); ax1.set_title('Temps de resolution (pentominoes)')
ax1.legend(); ax1.grid(axis='y', alpha=0.3)

ratios_v = [r[4] for r in pento_res]
ax2.bar(labels, ratios_v, color=['#4CAF50' if r < 1 else '#FF6B6B' for r in ratios_v],
        alpha=0.7, edgecolor='black')
ax2.axhline(1, color='black', linestyle='--', linewidth=1, alpha=0.5)
ax2.set_ylabel('Ratio DLX / Backtrack'); ax2.set_title('Avantage du DLX (< 1 = DLX gagne)')
for i, rv in enumerate(ratios_v):
    ax2.text(i, rv + 0.02, f'{rv:.2f}', ha='center', fontsize=10)
plt.tight_layout(); plt.show()

print()
print("Constat : sur les pentominoes, le DLX est environ 3x plus rapide que le")
print("backtracking. Contrairement aux instances triviales, l'arbre de recherche est")
print("assez vaste pour que l'heuristique MRV (case la plus contrainte d'abord) et les")
print("operations cover/uncover en O(1) dominent le cout fixe de construction.")
Benchmark : pavage par pentominoes (min de 3 executions)
================================================================
4x5 (F,L,P,Y)      matrice 81x 20 | DLX    1.49 ms | Backtrack     6.34 ms | ratio  0.23 | DLX gagne
                    pieces utilisees : ['F', 'L', 'P']
5x4 (F,L,P,Y)      matrice 81x 20 | DLX    1.44 ms | Backtrack     3.56 ms | ratio  0.41 | DLX gagne
                    pieces utilisees : ['F', 'L', 'P']


Constat : sur les pentominoes, le DLX est environ 3x plus rapide que le
backtracking. Contrairement aux instances triviales, l'arbre de recherche est
assez vaste pour que l'heuristique MRV (case la plus contrainte d'abord) et les
operations cover/uncover en O(1) dominent le cout fixe de construction.

Interpretation : Comparaison DLX vs Backtracking

Les resultats revelent une asymetrie importante : le DLX n’est pas systematiquement plus rapide. Son avantage depend de la taille de l’arbre de recherche.

Probleme Gagnant Rapport DLX / Backtrack Lecture
3x2 triominos Backtrack ~2x en faveur de Backtrack Instance triviale : le cout fixe de construction de la structure DLX (liste doublement chainee + selection MRV) depasse celui d’une recherche quasi immediate
4x2 triominos Aucun (impossible) - 8 cases non divisibles par 3 : aucun pavage n’existe, les deux methodes echouent
4x4 carres Backtrack ~1.7x en faveur de Backtrack Trop peu de placements pour que la structure DLX amortisse son cout de construction
4x5 / 5x4 pentominoes (F,L,P,Y) DLX ~0.3 (DLX ~3x plus rapide) Des que l’arbre de recherche s’elargit (matrice ~80x20, pieces aux formes asymetriques), la selection de colonne MRV et les cover/uncover en O(1) dominent

Pourquoi le DLX perd-il sur les petites instances ? Le DLX construit d’abord une liste doublement chainee sur toute la matrice de couverture exacte, puis applique l’heuristique MRV a chaque etape. Sur une instance triviale (quelques placements, solution trouvee en 1-2 coupures), ce cout fixe est superieur au backtracking naif qui s’arrete presque immediatement.

Pourquoi le DLX gagne-t-il sur les pentominoes ? - L’heuristique MRV (Minimum Remaining Values) choisit a chaque pas la case de grille offrant le moins de placements possibles, reduisant fortement le facteur de branchement. - Les operations cover/uncover en O(1) (sans recopie de matrice) rendent chaque retour-arriere quasi gratuit, la ou le backtracking naif recopie son ensemble covered.

Conclusion : le DLX excelle precisement sur les matrices creuses a grand arbre de recherche (Sudoku, pentominoes de grande taille) ; sur les instances triviales, un backtracking simple suffit et est meme plus rapide. La capacite annoncee du DLX - etre competitif sur les problemes complexes - se verifie sur les pentominoes, pas sur les instances triviales.

Note technique : Le backtracking pour le pavage peut etre optimise avec des heuristiques de placement (ex: placer d’abord les pieces les plus contraintes) - c’est precisement ce que fait la selection MRV du DLX, mais de maniere systematique et sans recopie.

Benchmark discriminant : pentominoes

Le benchmark ci-dessus resout un pavage par pentominoes (sous-ensemble F, L, P, Y) sur une grille 4x5 et 5x4 avec les deux methodes. C’est ici - et non sur les instances triviales - que l’avantage du DLX devient visible : le rapport DLX / Backtrack passe sous 1 (DLX plus rapide), la ou il restait superieur a 1 sur les triominos et les carres.

Quand utiliser DLX ?

Situation méthode recommande Raison
Sudoku DLX Modelisation naturelle, très efficace
Problemes de pavage (Pentominoes, Polyominos) DLX Contraintes exactes, grande matrice creuse
CSP généraux OR-Tools Propagation de contraintes, haut niveau
Programmation lineaire Simplex/Interior Point Contraintes continues

Conclusion : DLX excelle quand le problème se modelise naturellement comme couverture exacte avec une matrice creuse et des contraintes d’egalite.

Important : N-Queens n’est PAS une bonne application pour DLX car les diagonales sont des contraintes d’inegalite, pas d’egalite. Le pavage est un exemple correct de couverture exacte.

9. Exemple guide

Exemple 1 : Instance simple de couverture exacte

Enonce : Soit l’univers U = {1, 2, 3, 4, 5} et les sous-ensembles : - S1 = {1, 3, 5} - S2 = {2, 4} - S3 = {2, 3} - S4 = {2, 4, 5} - S5 = {3, 4}

  1. Construire la matrice binaire correspondante
  2. Resoudre avec l’algorithme X
  3. Verifier que la solution couvre exactement tous les éléments

Solution : La matrice a 5 lignes (sous-ensembles) et 5 colonnes (éléments). L’algorithme X selectionne les sous-ensembles disjoints qui couvrent exactement l’univers U.

# Exemple 1 : Instance simple de couverture exacte

# Univers U = {1, 2, 3, 4, 5}
# S1 = {1, 3, 5}, S2 = {2, 4}, S3 = {2, 3}, S4 = {2, 4, 5}, S5 = {3, 4}

print("Exemple 1 : Couverture Exacte")
print("=" * 50)

# 1. Construire la matrice binaire (5 lignes x 5 colonnes)
# Chaque ligne = un sous-ensemble, chaque colonne = un element de l'univers
# S1={1,3,5} -> ligne [1, 0, 1, 0, 1]
matrix = np.array([
    [1, 0, 1, 0, 1],  # S1
    [0, 1, 0, 1, 0],  # S2
    [0, 1, 1, 0, 0],  # S3
    [0, 1, 0, 1, 1],  # S4
    [0, 0, 1, 1, 0],  # S5
])

sets = {
    0: {1, 3, 5},
    1: {2, 4},
    2: {2, 3},
    3: {2, 4, 5},
    4: {3, 4}
}

# 2. Appliquer Algorithm X (Dancing Links) pour trouver la couverture exacte
sol = algorithm_x_simple(matrix)

# 3. Verifier la solution et afficher les sous-ensembles selectionnes
print(f"Solution trouvee : {[f'S{i+1}' for i in sol]}")
for idx in sol:
    print(f"  S{idx+1} couvre {sets[idx]}")

# Verification de la couverture exacte
covered = set()
for idx in sol:
    covered |= sets[idx]
print(f"\nElements couverts : {covered}")
print(f"Couverture exacte de U : {covered == {1, 2, 3, 4, 5}}")
Exemple 1 : Couverture Exacte
==================================================
Solution trouvee : ['S1', 'S2']
  S1 couvre {1, 3, 5}
  S2 couvre {2, 4}

Elements couverts : {1, 2, 3, 4, 5}
Couverture exacte de U : True

Exercice 4 : Pavage d’une grille 3x5 avec des trominos

Enonce : On souhaite paver une grille de 3 lignes par 5 colonnes (3x5 = 15 cases) avec des trominos (formes de 3 cases connectees). C’est un vrai problème de couverture exacte car chaque case doit etre couverte exactement une fois.

Les trois trominos disponibles sont : - I : trois cases en ligne droite horizontale [(0,0), (0,1), (0,2)] - L : trois cases en forme de L [(0,0), (1,0), (1,1)] - T : trois cases en forme de T (a vous de définir les coordonnees correctement)

étapes : 1. définir les trominos comme un dictionnaire {nom: [(ligne, colonne), ...]} 2. Construire la matrice de couverture exacte avec build_tiling_matrix() 3. Resoudre avec solve_dlx() ou solve_tiling_dlx() 4. Afficher le nombre de solutions et visualiser la première 5. Verifier que chaque case est couverte exactement une fois

Contraintes : - Toutes les rotations sont autorisees - Chaque case de la grille 3x5 doit etre couverte exactement une fois - Les pieces ne doivent pas depasser de la grille

Indice : Utilisez les fonctions build_tiling_matrix(), solve_dlx() et visualize_tiling_solution() définies dans les sections précédentes.

# Exercice 4 : Pavage d'une grille 3x5 avec des trominos

print("Exercice 2 : Pavage d'une grille 3x5")
print("=" * 50)

# Exercice: 1. Definir les trominos (formes de 3 cases connectees)
# Indice : utilisez un dictionnaire {nom: [(ligne, colonne), ...]}
# Exemple : 'I' : [(0, 0), (0, 1), (0, 2)] pour une ligne horizontale
trominos = {
    # Exercice: definir les formes I, L et T
}

# Exercice: 2. Construire la matrice de couverture exacte
# Indice : utilisez build_tiling_matrix(largeur, hauteur, trominos)
# matrix_tiling, placements = ...

# Exercice: 3. Resoudre avec DLX
# Indice : utilisez solve_tiling_dlx(largeur, hauteur, trominos)
# solutions = ...

# Exercice: 4. Afficher le resultat
# - Nombre de solutions trouvees
# - Afficher les placements de la premiere solution

# Exercice: 5. Visualiser la solution
# Indice : utilisez visualize_tiling_solution(largeur, hauteur, solution, trominos)

# Exercice: 6. Verifier que chaque case est couverte exactement une fois
print("Exercice a completer")
Exercice 2 : Pavage d'une grille 3x5
==================================================
Exercice a completer

10. Resume

Concepts cles

Concept Definition
Couverture exacte sélectionner des sous-ensembles disjoints couvrant exactement l’univers
Algorithme X Backtracking récursif avec opérations cover/uncover
Dancing Links (DLX) Structure de listes doublement liees circulaires
cover(c) Detacher une colonne et ses lignes conflictuelles (O(1))
uncover(c) Restaurer exactement l’etat (inverse de cover, O(1))

Avantages de DLX

Aspect Avantage
Efficacite opérations O(1), pas d’allocation memoire
Elegance Structure de données ingenieuse, backtrack parfait
Generalite Applicable a tout problème de couverture exacte
Performance Excellent sur les matrices creuses

Applications valides de DLX

problème Modelisation Performance
Sudoku 729x324 matrice < 1 seconde
Pavage (Polyominos) Positions x contraintes Variable
Pentominoes Positions x contraintes Variable
Exact Cover Direct Optimal

Pour aller plus loin

Navigation : << MCTS | Index | Programmation lineaire >>

Series connexes : - Sudoku-02-DancingLinks-Python - Application complete pour Sudoku - Search-App-11-Picross - DLX pour Picross

Conclusion

Ce notebook a presente l’Algorithme X de Knuth et les Dancing Links (DLX), la structure de données qui le rend efficace pour les problemes de couverture exacte.

Ce que nous avons appris

Concept Apport
Couverture exacte Trouver un sous-ensemble de lignes couvrant exactement chaque colonne une fois
Algorithme X Procedure récursive abstraite de resolution par couverture
Dancing Links Cover/uncover en O(1) via listes doublement chainees, l’astuce de Knuth
MRV sur colonnes Choisir la colonne avec le moins de 1 pour minimiser le branching

résultats mesures

L’implementation DLX surpasse l’Algorithme X naif dès que l’arbre de recherche devient vaste. Les temps absolus mesurés ci-dessus dépendent de la machine et fluctuent à chaque exécution ; le benchmark discriminant sur pentominoes montre l’avantage du DLX se creuser quand le problème grandit (rapport lu dans la sortie de la cellule de mesure, non figé en prose). Sur de très petites instances, le cout de construction de la structure DLX peut contrebalancer le gain.

Applications

La couverture exacte modelise naturellement le Sudoku (chaque cellule, ligne, colonne, bloc = colonne de contrainte) et le pavage de polyominos (pentominoes 6x10). Attention : N-Queens n’est PAS un problème de couverture exacte.

Suite : Search-9 - Programmation lineaire | Retour au sommaire

Retour au sommet