# Algorithme X de Knuth

L'algorithme X de Donald Knuth est un algorithme récursif non-déterministe(en), de parcours en profondeur et à retour sur trace. Il permet de trouver des solutions au problème de la couverture exacte, représenté sous la forme d'une matrice contenant des 0 et des 1. L'objectif est de déterminer un sous-ensemble de lignes tel que le chiffre 1 n'apparaisse dans chaque colonne qu'une et une seule fois. Une implémentation efficace appelée DLX utilise la structure de données des liens dansants.

## Problème de couverture exacte

Le problème de couverture exacte consiste à calculer une couverture d'un univers. Plus précisément, on se donne un univers ${\mathcal {U}}$ et une collection ${\mathcal {S}}$ de sous-ensembles. Il s'agit de sélectionner, si possible, des sous-ensembles de ${\mathcal {S}}$ de façon que chaque élément de l'univers soit couvert par un et un seul de ces sous-ensembles. Par exemple, considérons l'univers ${\mathcal {U}}=\{1,2,3,4,5,6,7\}$, avec la collection d'ensembles ${\mathcal {S}}=\{A,B,C,D,E,F\}$ telle que :
* $A=\{1,4,7\}$;
* $B=\{1,4\}$;
* $C=\{4,5,7\}$;
* $D=\{3,5,6\}$;
* $E=\{2,3,6,7\}$ et
* $F=\{2,7\}$.
Une solution consister à sélectionner les sous-ensembles $B,D,F$. L'algorithme X de Knuth utilise la représentation matricielle suivante. Les colonnes sont les éléments de l'univers. Les lignes sont les sous-ensembles. On place un 1 dans une cellule lorsque l'élément appartient au sous-ensembles. La matrice de l'exemple présenté plus haut est :
| | 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 |

## Principe

L'algorithme X utilise la représentation matricielle du problème de la couverture exacte. On suppose que ladite matrice a été préalablement déterminée. À partir de cette matrice, l'algorithme fonctionne ainsi :
Le non-déterminisme de l'algorithme vient de la ligne 3. En effet, on ne sait pas déterminer si une ligne $\ell$ précise conduit à une solution du problème. On crée alors un ensemble de sous-algorithmes qui partent tous de la matrice $M$ mais la réduisent par rapport à des lignes $\ell$ différentes. Cela revient à former un arbre de recherche, avec le problème original à la racine et chaque branche correspondant à un sous-algorithme avec une ligne différente. En pratique, on calcule la première branche et ses sous-branches si elles existent (principe de parcours en profondeur). En cas d'échec de l'algorithme sur une branche, on remonte d'un niveau et on calcule la branche suivante, c'est-à-dire qu'on prend la ligne $\ell$ suivante dans la liste des possibilités, et on s'arrête dès la réussite d'une branche, c'est le principe du retour sur trace. Il est aussi possible de continuer les calculs sur toutes les branches pour obtenir l'ensemble des solutions du problème.
Pour le choix de la colonne $c$, n'importe quelle règle appliquée de manière systématique fonctionnera, mais certaines sont plus performantes que d'autres. Afin de réduire le nombre d'itérations, Knuth suggère de prendre une colonne avec un minimum de 1, comme présenté dans le fonctionnement de l'algorithme, ci-dessus. De plus, toujours pour réduire les calculs, il est clair que si la colonne $c$ est composée uniquement de 0, on ne peut créer aucune sous-branche dans l'algorithme alors que la matrice $M$ n'est pas vide, et on a donc l'échec de l'algorithme sur la branche en cours.

## Exemple

Exécutons l'algorithme sur la matrice suivante.
    1 2 3 4 5 6 7 A 1001001 B 1001000 C 0001101 D 0010110 E 0110011 F 0100001
Nous sommes actuellement à la racine de l'arbre de recherche de la solution. On commence la résolution.
Niveau 0 Étape 1 — La matrice n'est pas vide, on n'est donc pas arrivé à une solution. Étape 2 — La première colonne avec un minimum de 1 est la colonne 1, qui est donc sélectionnée.
    1 2 3 4 5 6 7 A 1001001 B 1001000 C 0001101 D 0010110 E 0110011 F 0100001
Étape 3 — Les lignes A et B ont des 1 dans la colonne 1, on lance un sous-algorithme pour chacune de ces deux lignes.
    Niveau 1 : ligne A
    Étape 4 — On ajoute la ligne A à la solution partielle.
    Étape 5 — La ligne A possède des 1 dans les colonnes 1, 4, 7 :
       1 2 3 4 5 6 7 A 1001001 B 1001000 C 0001101 D 0010110 E 0110011 F 0100001
    Étape 6 — La colonne 1 contient des 1 aux lignes A et B ; la colonne 4, aux lignes A, B, C ; la colonne 7, aux lignes A, C, E et F.
    On élimine donc les lignes et colonnes susmentionnées.
       1 2 3 4 5 6 7 A 1001001 B 1001000 C 0001101 D 0010110 E 0110011 F 0100001
    Il reste la matrice réduite suivante, où seule la ligne D et les colonnes 2, 3, 5, 6 restent :
       2 3 5 6 D 0111
    L'algorithme reprend depuis l'étape 1 sur cette nouvelle matrice :
    Étape 1 — La matrice n'est pas vide, on n'est donc pas arrivé à une solution.
    Étape 2 — La première colonne avec un minimum de 1 est la colonne 2, qui n'en contient aucun. Mais comme il n'y a pas de 1, on ne peut plus réduire la matrice, et cette branche de l'algorithme échoue.
    On passe à la ligne suivante du niveau 1 : la ligne B.
    Niveau 1 : ligne B
    Étape 4 — On ajoute la ligne B à la solution partielle.
    Étape 5 — La ligne B possède des 1 dans les colonnes 1 et 4 :
    1 2 3 4 5 6 7 A 1001001 B 1001000 C 0001101 D 0010110 E 0110011 F 0100001
    Étape 6 — La colonne 1 contient des 1 aux lignes A et B ; la colonne 4, aux lignes A, B et C.
    On élimine les lignes et colonnes susmentionnées.
       1 2 3 4 5 6 7 A 1001001 B 1001000 C 0001101 D 0010110 E 0110011 F 0100001
    Il reste la matrice réduite où seules lignes D, E, F, et les colonnes 2, 3, 5, 6, 7 restent :
       2 3 5 6 7 D 01110 E 11011 F 10001
    L'algorithme reprend depuis l'étape 1 sur cette nouvelle matrice :
    Étape 1 — La matrice n'est pas vide, on n'est donc pas arrivé à une solution.
    Étape 2 — La première colonne avec un minimum de 1 est la colonne 5, qui n'en a qu'un. On la sélectionne.
       2 3 5 6 7 D 01110 E 11011 F 10001
    Étape 3 — La ligne D a un 1 dans la colonne 5, on lance un sous-algorithme sur cette ligne.
       Niveau 2 : ligne D
       Étape 4 — On ajoute la ligne D à la solution partielle.
       Étape 5 — La ligne D possède des 1 dans les colonnes 3, 5 et 6 :
          2 3 5 6 7 D 01110 E 11011 F 10001
       Étape 6 — La colonne 3 contient des 1 aux lignes D et E ; la colonne 5, à la ligne D ; la colonne 6, aux lignes D et E.
       On élimine les lignes et colonnes susmentionnées.
          2 3 5 6 7 D 01110 E 11011 F 10001
       Il reste la matrice réduite où seule la ligne F et les colonnes 2, 7 restent :
          2 7 F 11
       L'algorithme reprend depuis l'étape 1 sur cette nouvelle matrice :
       Étape 1 — La matrice n'est pas vide, on n'est donc pas arrivé à une solution.
       Étape 2 — La première colonne avec un minimum de 1 est la colonne 2, qui n'en a qu'un. On la sélectionne.
          2 7 F 11
       Étape 3 — La ligne F a un 1 dans la colonne 5, on lance un sous-algorithme sur cette ligne.
          Niveau 3 : ligne F
          Étape 4 — On ajoute la ligne F à la solution partielle.
          Étape 5 — La ligne F possède des 1 dans les colonnes 2 et 7 :
             2 7 F 11
          Étape 6 — La colonne 2 contient un 1 à la ligne F ; la colonne 7, à la ligne F aussi.
          On élimine la ligne et les colonnes susmentionnées.
             2 7 F 11
          La matrice obtenue est vide. Les lignes sélectionnées ont été B, D, F. L'algorithme s'arrête avec la solution ${\mathcal {S^{*}}}=\{B,D,F\}$

## Implémentations

Les Liens dansants (en) (en anglais Dancing links), plus connus sous le nom DLX, sont une technique suggérée par Knuth pour implémenter de façon efficace l'algorithme X à l'aide d'un ordinateur. Ils utilisent des listes doublement chaînées. Il y a une liste de 1 pour chaque colonne et une liste pour chaque ligne. Chaque 1 de la matrice se retrouve lié à ceux situés au-dessus, en dessous, à gauche et à droite.