Introduction au problème de couverture exacte

Considérons une matrice binaire A de N lignes et M colonnes (N,M ≤ 500). L'objectif est de sélectionner un ensemble de lignes tel que pour chaque colonne, il y a exactement une ligne sélectionnée avec un 1 dans cette colonne. Une approche par force brute consisterait à itérer sur toutes les combinaisons possibles de lignes, conduisant à une complexité temporelle de O(nm·2^n), ce qui est impraticable pour de grandes instances. L'algorithme Dancing Links (DLX) propose une solution efficace basée sur la récursion et le backtracking.

L'algorithme X

Flux de l'algorithme X

L'algorithme X fonctionne comme suit : initialement, on prend la matrice binaire. On sélectionne une colonne, et pour chaque ligne ayant un 1 dans cette colonne, on réduit la matrice en supprimant la ligne sélectionnée, ainsi que toutes les colonnes où cette ligne a un 1, et toutes les lignes ayant un 1 dans ces colonnes supprimées. Ce processus se répète récursivement jusqu'à obtenir une matrice vide, indiquant une solution, ou jusqu'à ce qu'aucune colonne ne reste, ce qui signifie une solution partielle si la dernière ligne supprimée est entièrement composée de 1. Sinon, on revient en arrière pour essayer d'autres lignes.

Prenons un exemple avec une matrice donnée. En sélectionnant la première ligne, on supprime les colonnes correspondantes et les lignes conflictuelles, réduisant ainsi le problème. En poursuivant de manière récursive, on peut explorer toutes les possibilités jusqu'à trouver une solution valide.

Princiep de l'algorithme X

Lors de la suppression, on élimine la ligne choisie et les colonnes où elle a des 1 pour garantir que chaque colonne n'ait qu'un seul 1 dans la solution. De plus, on supprime les lignes ayant des 1 dans ces colonnes car elles ne peuvent plus être sélectionnées. Une matrice vide peut résulter de la suppression de toutes les lignes ou de toutes les colonnes ; seule la seconde situation correspond à une solution complète, d'où la condition de vérifier si la dernière ligne supprimée est entièrement composée de 1.

Dancing Links (DLX)

Structure de données : liste chaînée croisée bidirectionnelle

Pour implémenter efficacement l'algorithme X, on utilise une liste chaînée croisée bidirectionnelle où chaque élément stocke des pointeurs vers ses voisins gauche, droite, haut et bas, ainsi que son numéro de ligne et de colonne. De plus, on maintient des indicateurs pour le premier élément de chaque ligne et des nœuds virtuels pour les colonnes, permettant de naviguer et de manipuler la structure rapidement.

Opérations de base

Suppression d'une colonne

L'opération remove(p) supprime la colonne p et toutes les lignes associées. On retire d'abord la colonne de la liste des colonnes, puis pour chaque élément dans cette colonne, on supprime sa ligne entière en mettant à jour les pointeurs verticaux et en décrémentant les compteurs de colonnes.

void supprimer(int colonne) {
    // Détacher la colonne de la liste horizontale
    gauche[droite[colonne]] = gauche[colonne];
    droite[gauche[colonne]] = droite[colonne];
    for (int i = bas[colonne]; i != colonne; i = bas[i]) {
        for (int j = droite[i]; j != i; j = droite[j]) {
            haut[bas[j]] = haut[j];
            bas[haut[j]] = bas[j];
            taille[col[j]]--;
        }
    }
}

Récupération d'une colonne

L'opération recover(p) restaure la colonne p et ses lignes, inversant les opérations de suppression en rétablissant les pointeurs et les compteurs.

void recuperer(int colonne) {
    for (int i = haut[colonne]; i != colonne; i = haut[i]) {
        for (int j = gauche[i]; j != i; j = gauche[j]) {
            haut[bas[j]] = j;
            bas[haut[j]] = j;
            taille[col[j]]++;
        }
    }
    gauche[droite[colonne]] = colonne;
    droite[gauche[colonne]] = colonne;
}

Construction et insertion

La fnoction build initialise la structure avec des nœuds de colonnes virtuels, tandis que insert ajoute un élément à une ligne et colonne spécifiques, en le liant verticalement et horizontalement.

int compteur;
int ligne[N], colonne[M], taille[M], premier[N];

void construire(int nb_lignes, int nb_colonnes) {
    for (int c = 0; c <= nb_colonnes; c++) {
        gauche[c] = c - 1;
        droite[c] = c + 1;
        haut[c] = bas[c] = c;
    }
    gauche[0] = nb_colonnes;
    droite[nb_colonnes] = 0;
    compteur = nb_colonnes;
}

void inserer(int l, int c) {
    compteur++;
    ligne[compteur] = l;
    colonne[compteur] = c;
    taille[c]++;
    // Insérer verticalement
    haut[compteur] = c;
    bas[compteur] = bas[c];
    haut[bas[c]] = compteur;
    bas[c] = compteur;
    // Insérer horizontalement
    if (!premier[l]) {
        premier[l] = gauche[compteur] = droite[compteur] = compteur;
    } else {
        gauche[compteur] = premier[l];
        droite[compteur] = droite[premier[l]];
        gauche[droite[premier[l]]] = compteur;
        droite[premier[l]] = compteur;
    }
}

Fonction principale de recherche

La fonction dance implémente l'algorithme X de manière récursive. Elle vérifie d'abord si la matrice est vide (solution trouvée), sinon elle sélectionne la colonne avec le moins d'éléments pour une heuristique efficace, puis itère sur les lignes de cette colonne en appliquant suppression et récupération.

int solution[MAX];

void danser(int profondeur) {
    if (droite[0] == 0) { // Solution trouvée
        for (int i = 1; i < profondeur; i++) {
            cout << solution[i] << " ";
        }
        exit(0);
    }
    int col_choisie = droite[0];
    for (int c = droite[0]; c != 0; c = droite[c]) {
        if (taille[c] < taille[col_choisie]) {
            col_choisie = c;
        }
    }
    supprimer(col_choisie);
    for (int r = bas[col_choisie]; r != col_choisie; r = bas[r]) {
        solution[profondeur] = ligne[r];
        for (int c = droite[r]; c != r; c = droite[c]) {
            supprimer(colonne[c]);
        }
        danser(profondeur + 1);
        for (int c = gauche[r]; c != r; c = gauche[c]) {
            recuperer(colonne[c]);
        }
    }
    recuperer(col_choisie);
}

Applications de Dancing Links

Problèmes de couverture exacte

Dans un problème de couverture exacte, on a un ensemble X et une collection de sous-ensembles. L'objectif est de sélectionner des sous-ensembles disjoints qui couvrent exactement X. On peut modéliser cela avec une matrice binaire où les lignes représentent les sous-ensembles et les colonnes représentent les éléments de X, puis appliquer DLX.

Problème du Sudoku

Le Sudoku typique est un problème de couverture exacte. Pour chaque cellule (r, c) contenant un nombre x, on a des contraintes : chaque ligne, colonne et bloc doit contenir chaque nombre exactement une fois, et chaque cellule doit avoir un seul nombre. On crée des colonnes pour ces contraintes et des lignes pour chaque placement possible, formant ainsi une matrice binaire adoptée à DLX.

Problèmes de couverture répétée

Dans la couverture répétée, chaque colonne doit avoir au moins un 1 dans les lignes sélectionnées. L'adaptation de DLX consiste à supprimer uniquement les colonnes associées à la ligne choisie, sans supprimer les lignes conflictuelles de manière permanente. Cela ralentit la recherche, donc on utilise une fonction d'estimation heuristique pour le pruning optimal, comme dans l'algorithme A* ou IDA*.

Exemples de problèmes

Problèmes d'empilage de formes

Pour des puzzles comme le placement de polyominos, on modélise chaque placement possible comme une ligne et chaque cellule ou contrainte comme une colonne, permettant de résoudre via DLX.

Problème des N-Dames

Le placement de N dames sur un échiquier sans conflit est une couverture exacte. Les colonnes représentent les lignes, colonnes et diagonales, et les lignes représentent les positions des dames. En ajustant pour couvrir seulement les lignes et colonnes principales, on peut utiliser DLX efficacement.