Voir la source de Algorithme X de Knuth

L''''algorithme X de [[Donald Knuth]]''' est un [[algorithme]] [[Algorithme récursif|récursif]] {{Lien|trad=Nondeterministic algorithm|Algorithme non-déterministe|texte=non-déterministe}}, de [[parcours en profondeur]] et à [[retour sur trace]]. Il permet de trouver des{{vague}} 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<ref name="knuth">{{lien arXiv|auteur=Knuth, Donald|lien auteur=Donald Knuth|titre=Dancing links|année=2000|eprint=cs/0011047}}</ref>.

== Problème de couverture exacte ==
{{Article détaillé|problème de la couverture exacte}}
Le problème de couverture exacte consiste à calculer une couverture d'un univers. Plus précisément, on se donne un univers <math>\mathcal{U}</math> et une collection <math>\mathcal{S}</math> de sous-ensembles. Il s'agit de sélectionner, si possible, des sous-ensembles de <math>\mathcal{S}</math> 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 <math>\mathcal{U} = \{1, 2, 3, 4, 5, 6, 7\}</math>, avec la collection d'ensembles <math>\mathcal{S} = \{A, B, C, D, E, F\}</math> telle que :
*<math>A = \{1, 4, 7\}</math>;
*<math>B = \{1, 4\}</math>;
*<math>C = \{4, 5, 7\}</math>;
*<math>D = \{3, 5, 6\}</math>;
*<math>E = \{2, 3, 6, 7\}</math> et
*<math>F = \{2, 7\}</math>.
Une solution consister à sélectionner les sous-ensembles <math>B, D, F</math>. 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 :
{| cellspacing="0" cellpadding="5" border="1"
 |-----
 |
 ! scope="col" | 1
 ! scope="col" | 2
 ! scope="col" | 3
 ! scope="col" | 4
 ! scope="col" | 5
 ! scope="col" | 6
 ! scope="col" | 7
 |----- 
 ! scope="row" | A
 | 1 || 0 || 0 || 1 || 0 || 0 || 1
 |-----
 ! scope="row" | B
 | 1 || 0 || 0 || 1 || 0 || 0 || 0
 |-----
 ! scope="row" | C
 | 0 || 0 || 0 || 1 || 1 || 0 || 1
 |-----
 ! scope="row" | D
 | 0 || 0 || 1 || 0 || 1 || 1 || 0
 |-----
 ! scope="row" | E
 | 0 || 1 || 1 || 0 || 0 || 1 || 1
 |-----
 ! scope="row" | F
 | 0 || 1 || 0 || 0 || 0 || 0 || 1
 |}
== Principe ==
L'algorithme X utilise la [[Problème de la couverture exacte#Représentation matricielle|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 :

 1  '''Tant que''' ''la matrice'' <math>M</math> ''n'est pas vide''
 2  |  Choisir la première colonne <math>c</math> contenant un minimum de 1 (déterministe)
 3  |  Choisir une ligne <math>\ell</math> telle que <math>M_{\ell, c} = 1</math> (non-déterministe)
 4  |  Ajouter la ligne <math>\ell</math> à la solution partielle
 5  |  '''Pour''' chaque ''colonne'' <math>j</math> ''telle que'' <math>M_{\ell, j} = 1</math>
 6  |  |  '''Pour''' chaque ''ligne'' <math>i</math> ''telle que'' <math>M_{i, j} = 1</math>
 7  |  |  |   Supprimer la ligne <math>i</math> de la matrice <math>M</math>
 9  |  |  Supprimer la colonne <math>j</math> de la matrice <math>M</math>
 12 '''succès'''

Le non-déterminisme de l'algorithme vient de la ligne 3. En effet, on ne sait pas déterminer si une ligne <math>\ell</math> précise conduit à une solution du problème. On crée alors un ensemble de sous-algorithmes qui partent tous de la matrice <math>M</math> mais la réduisent par rapport à des lignes <math>\ell</math> différentes. Cela revient à former un [[Arbre (informatique)|arbre]] de recherche, avec le problème original à la racine et chaque branche correspondant à un sous-algorithme avec une ligne différente.<br />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 <math>\ell</math> 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 <math>c</math>, 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 <math>c</math> est composée uniquement de 0, on ne peut créer aucune sous-branche dans l'algorithme alors que la matrice <math>M</math> n'est pas vide, et on a donc l'échec de l'algorithme sur la branche en cours.

== Exemple ==
[[Fichier:Search Tree for Exact Cover.svg|vignette|Arbre de recherche exploré par l'algorithme X. On considère l'élément 1 que l'on essaie de couvrir avec A = {1, 4, 7}. Mais on est bloqué car on ne peut couvrir 2. On le couvre donc avec B = {1, 4}. Il y a alors une unique possibilité pour couvrir 5 : avec D = {3, 5, 6}. Puis unique possibilité pour couvrir 2 : avec F = {2, 7}.]]
Exécutons l'algorithme sur la matrice suivante.
:{| border="1" cellpadding="5" cellspacing="0"
 |-----
 |
 ! scope="col" | 1
 ! scope="col" | 2
 ! scope="col" | 3
 ! scope="col" | 4
 ! scope="col" | 5
 ! scope="col" | 6
 ! scope="col" | 7
 |----- 
 ! scope="row" | A
 | 1 || 0 || 0 || 1 || 0 || 0 || 1
 |-----
 ! scope="row" | B
 | 1 || 0 || 0 || 1 || 0 || 0 || 0
 |-----
 ! scope="row" | C
 | 0 || 0 || 0 || 1 || 1 || 0 || 1
 |-----
 ! scope="row" | D
 | 0 || 0 || 1 || 0 || 1 || 1 || 0
 |-----
 ! scope="row" | E
 | 0 || 1 || 1 || 0 || 0 || 1 || 1
 |-----
 ! scope="row" | F
 | 0 || 1 || 0 || 0 || 0 || 0 || 1
 |}

Nous sommes actuellement à la racine de l'arbre de recherche de la solution. On commence la résolution.

'''Niveau 0'''<br />
Étape 1 — La matrice n'est pas vide, on n'est donc pas arrivé à une solution.<br />
Étape 2 — La première colonne avec un minimum de 1 est la colonne ''1'', qui est donc sélectionnée.

:{| border="1" cellpadding="5" cellspacing="0"
 |-----
 |
 ! bgcolor="#BBBBBB" scope="col" | 1
 ! scope="col" | 2
 ! scope="col" | 3
 ! scope="col" | 4
 ! scope="col" | 5
 ! scope="col" | 6
 ! scope="col" | 7
 |----- 
 ! scope="row" | A
 | bgcolor="#BBBBBB" | {{rouge|1}} || 0 || 0 || 1 || 0 || 0 || 1
 |-----
 ! scope="row" | B
 | bgcolor="#BBBBBB" | {{rouge|1}} || 0 || 0 || 1 || 0 || 0 || 0
 |-----
 ! scope="row" | C
 | bgcolor="#BBBBBB" | 0 || 0 || 0 || 1 || 1 || 0 || 1
 |-----
 ! scope="row" | D
 | bgcolor="#BBBBBB" | 0 || 0 || 1 || 0 || 1 || 1 || 0
 |-----
 ! scope="row" | E
 | bgcolor="#BBBBBB" | 0 || 1 || 1 || 0 || 0 || 1 || 1
 |-----
 ! scope="row" | F
 | bgcolor="#BBBBBB" | 0 || 1 || 0 || 0 || 0 || 0 || 1
 |}

É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'' :

::{| border="1" cellpadding="5" cellspacing="0"
 |-----
 |
 ! scope="col" | 1
 ! scope="col" | 2
 ! scope="col" | 3
 ! scope="col" | 4
 ! scope="col" | 5
 ! scope="col" | 6
 ! scope="col" | 7
 |----- 
 ! bgcolor="#BBBBBB" scope="row" | A
 | bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | {{rouge|1}}
 |-----
 ! scope="row" | B
 | 1 || 0 || 0 || 1 || 0 || 0 || 0
 |-----
 ! scope="row" | C
 | 0 || 0 || 0 || 1 || 1 || 0 || 1
 |-----
 ! scope="row" | D
 | 0 || 0 || 1 || 0 || 1 || 1 || 0
 |-----
 ! scope="row" | E
 | 0 || 1 || 1 || 0 || 0 || 1 || 1
 |-----
 ! scope="row" | F
 | 0 || 1 || 0 || 0 || 0 || 0 || 1
 |}

:É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.

::{| border="1" cellpadding="5" cellspacing="0"
 |-----
 |
 ! bgcolor="#BBBBBB" scope="col" | 1
 ! scope="col" | 2
 ! scope="col" | 3
 ! bgcolor="#BBBBBB" scope="col" | 4
 ! scope="col" | 5
 ! scope="col" | 6
 ! bgcolor="#BBBBBB" scope="col" | 7
 |----- 
 ! bgcolor="#BBBBBB" scope="row" | A
 | bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | {{rouge|1}}
 |-----
 ! bgcolor="#BBBBBB" scope="row" | B
 | bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0
 |-----
 ! bgcolor="#BBBBBB" scope="row" | C
 | bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 1 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | {{rouge|1}}
 |-----
 ! scope="row" | D
 | bgcolor="#BBBBBB" | 0 || 0 || 1 || bgcolor="#BBBBBB" | 0 || 1 || 1 || bgcolor="#BBBBBB" | 0
 |-----
 ! bgcolor="#BBBBBB" scope="row" | E
 | bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 1 || bgcolor="#BBBBBB" | 1 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 1 || bgcolor="#BBBBBB" | {{rouge|1}}
 |-----
 ! bgcolor="#BBBBBB" scope="row" | F
 | bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 1 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | {{rouge|1}}
 |}

:Il reste la matrice réduite suivante, où seule la ligne D et les colonnes 2, 3, 5, 6 restent :

::{| border="1" cellpadding="5" cellspacing="0"
 |-----
 |
 ! scope="col" | 2
 ! scope="col" | 3
 ! scope="col" | 5
 ! scope="col" | 6
 |-----
 ! scope="row" | D
 | 0 || 1 || 1 || 1
 |}

: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'' :

:{| border="1" cellpadding="5" cellspacing="0"
 |-----
 |
 ! scope="col" | 1
 ! scope="col" | 2
 ! scope="col" | 3
 ! scope="col" | 4
 ! scope="col" | 5
 ! scope="col" | 6
 ! scope="col" | 7
 |----- 
 ! scope="row" | A
 | 1 || 0 || 0 || 1 || 0 || 0 || 1
 |-----
 ! bgcolor="#BBBBBB" scope="row" | B
 | bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0
 |-----
 ! scope="row" | C
 | 0 || 0 || 0 || 1 || 1 || 0 || 1
 |-----
 ! scope="row" | D
 | 0 || 0 || 1 || 0 || 1 || 1 || 0
 |-----
 ! scope="row" | E
 | 0 || 1 || 1 || 0 || 0 || 1 || 1
 |-----
 ! scope="row" | F
 | 0 || 1 || 0 || 0 || 0 || 0 || 1
 |}

:É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.

::{| border="1" cellpadding="5" cellspacing="0"
 |-----
 |
 ! bgcolor="#BBBBBB" scope="col" | 1
 ! scope="col" | 2
 ! scope="col" | 3
 ! bgcolor="#BBBBBB" scope="col" | 4
 ! scope="col" | 5
 ! scope="col" | 6
 ! scope="col" | 7
 |----- 
 ! bgcolor="#BBBBBB" scope="row" | A
 | bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 1
 |-----
 ! bgcolor="#BBBBBB" scope="row" | B
 | bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0
 |-----
 ! bgcolor="#BBBBBB" scope="row" | C
 | bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 1 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 1
 |-----
 ! scope="row" | D
 | bgcolor="#BBBBBB" | 0 || 0 || 1 || bgcolor="#BBBBBB" | 0 || 1 || 1 || 0
 |-----
 ! scope="row" | E
 | bgcolor="#BBBBBB" | 0 || 1 || 1 || bgcolor="#BBBBBB" | 0 || 0 || 1 || 1
 |-----
 ! scope="row" | F
 | bgcolor="#BBBBBB" | 0 || 1 || 0 || bgcolor="#BBBBBB" | 0 || 0 || 0 || 1
 |}

:Il reste la matrice réduite où seules lignes D, E, F, et les colonnes 2, 3, 5, 6, 7 restent :

::{| border="1" cellpadding="5" cellspacing="0"
 |-----
 |
 ! scope="col" | 2
 ! scope="col" | 3
 ! scope="col" | 5
 ! scope="col" | 6
 ! scope="col" | 7
 |-----
 ! scope="row" | D
 | 0 || 1 || 1 || 1 || 0
 |-----
 ! scope="row" | E
 | 1 || 1 || 0 || 1 || 1
 |-----
 ! scope="row" | F
 | 1 || 0 || 0 || 0 || 1
 |}

: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.

::{| border="1" cellpadding="5" cellspacing="0"
 |-----
 |
 ! scope="col" | 2
 ! scope="col" | 3
 ! bgcolor="#BBBBBB" scope="col" | 5
 ! scope="col" | 6
 ! scope="col" | 7
 |-----
 ! scope="row" | D
 | 0 || 1 || bgcolor="#BBBBBB" | {{rouge|1}} || 1 || 0
 |-----
 ! scope="row" | E
 | 1 || 1 || bgcolor="#BBBBBB" | 0 || 1 || 1
 |-----
 ! scope="row" | F
 | 1 || 0 || bgcolor="#BBBBBB" | 0 || 0 || 1
 |}

:É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'' :

:::{| border="1" cellpadding="5" cellspacing="0"
 |-----
 |
 ! scope="col" | 2
 ! scope="col" | 3
 ! scope="col" | 5
 ! scope="col" | 6
 ! scope="col" | 7
 |-----
 ! bgcolor="#BBBBBB" scope="row" | D
 | bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 0
 |-----
 ! scope="row" | E
 | 1 || 1 || 0 || 1 || 1
 |-----
 ! scope="row" | F
 | 1 || 0 || 0 || 0 || 1
 |}

::É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.

:::{| border="1" cellpadding="5" cellspacing="0"
 |-----
 |
 ! scope="col" | 2
 ! bgcolor="#BBBBBB" scope="col" | 3
 ! bgcolor="#BBBBBB" scope="col" | 5
 ! bgcolor="#BBBBBB" scope="col" | 6
 ! scope="col" | 7
 |-----
 ! bgcolor="#BBBBBB" scope="row" | D
 | bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 0
 |-----
 ! bgcolor="#BBBBBB" scope="row" | E
 | bgcolor="#BBBBBB" | 1 || bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | 1
 |-----
 ! scope="row" | F
 | 1 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || bgcolor="#BBBBBB" | 0 || 1
 |}

::Il reste la matrice réduite où seule la ligne F et les colonnes 2, 7 restent :

:::{| border="1" cellpadding="5" cellspacing="0"
 |-----
 |
 ! scope="col" | 2
 ! scope="col" | 7
 |-----
 ! scope="row" | F
 | 1 || 1
 |}

::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.

:::{| border="1" cellpadding="5" cellspacing="0"
 |-----
 |
 ! bgcolor="#BBBBBB" scope="col" | 2
 ! scope="col" | 7
 |-----
 ! scope="row" | F
 | bgcolor="#BBBBBB" | {{rouge|1}} || 1
 |}

::É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'' :

::::{| border="1" cellpadding="5" cellspacing="0"
 |
 ! scope="col" | 2
 ! scope="col" | 7
 |-----
 ! bgcolor="#BBBBBB" scope="row" | F
 | bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | {{rouge|1}}
 |}

:::É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.

::::{| border="1" cellpadding="5" cellspacing="0"
 |
 ! bgcolor="#BBBBBB" scope="col" | 2
 ! bgcolor="#BBBBBB" scope="col" | 7
 |-----
 ! bgcolor="#BBBBBB" scope="row" | F
 | bgcolor="#BBBBBB" | {{rouge|1}} || bgcolor="#BBBBBB" | {{rouge|1}}
 |}

:::La matrice obtenue est vide. Les lignes sélectionnées ont été B, D, F. L'algorithme s'arrête avec la solution <math>\mathcal{S^{*}} = \{B, D, F\}</math>
== Implémentations ==
[[Fichier:Dancing links.svg|vignette|Liens dansants<ref>{{Lien web |titre=Outil en ligne pour manipuler les liens dansants |url=https://playwithalgos.github.io/dancing-links/}}</ref>.]]
Les {{lien |lang=en |trad=Dancing links| fr=Liens dansants}} (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 [[Liste chaînée#Liste doublement cha.C3.AEn.C3.A9e|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.

== Références ==
{{Références}}
{{Traduction/Référence|en|Knuth's Algorithm X|495309363}}
*{{chapitre
 | langue = en
 | prénom1 = Donald E. | nom1 = Knuth | lien auteur1 = Donald Knuth
 | titre chapitre = Dancing links
 | page début chapitre = 187
 | passage = 187-214
 | titre ouvrage = Millennial Perspectives in Computer Science
 | sous-titre ouvrage = Proceedings of the 1999 Oxford-Microsoft Symposium in Honour of Sir Tony Hoare
 | auteurs ouvrage = Jim Davies ; Bill Roscoe et Jim Woodcock   
 | jour = 30
 | mois = 11
 | année = 2000
 | éditeur = Palgrave
 | collection = Cornerstones of Computing
 | pages totales = 432
 | isbn = 978-0-333-92230-9
 | lire en ligne = https://arxiv.org/abs/cs/0011047
 | consulté le = 11 novembre 2013 }}.

== Voir aussi ==
=== Articles connexes ===
* [[Problème de la couverture exacte]]

=== Liens externes ===
* {{en}} {{lien brisé|url=http://cheeso.members.winisp.net/srcview.aspx?dir=Sudoku&file=ExactCover.cs |titre=Implémentation en C# d'un solveur du problème de couverture exacte }} - utilise l'algorithme X et les liens dansants.
* {{en}} [http://github.com/mlepage/polycube-solver Polycube solver] Programme (et [[code source]] [[Lua]]) pour remplir des boîtes avec des [[polycube]]s, utilisant l'algorithme X.
* {{en}} [http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz Article de Donald Knuth sur les Dancing Links].

{{Palette Donald Knuth}}

{{Portail|informatique théorique}}

[[Catégorie:Algorithme|X de Knuth]]
[[Catégorie:Donald Knuth]]