Liens dansants

Cet été, en lisant 'Le Temps', apporté par des amis suisses, j'ai découvert le Sudoku. Typiquement une grille de 9x9, découpées en 3x3 blocs de neuf cases, dans laquelle les nombres de 1 à 9 doivent se trouver sur chaque ligne, chaque colonne et chaque bloc.

Donald Knuth est l'inventeur du LateX, ce langage de description de documents. Professeur à la Stanford university, D Knuth a produit de nombreux articles mathématiques ou traitant d'algorithmique.

L'article sur les liens dansants (dancing links) part d'un constat évident et en tire des conséquences inattendues.

Le constat est le suivant, dans une liste circulaire (double chaînée), d'élements, alors

n.gauche.droite ← n.droite;
n.droite.gauche ← n.gauche;

indifferement, suppriment l'élement n de la liste, et par conséquent :

n.gauche.droite ← n;
n.droite.gauche ← n;

le remettent en place.

Souvent, après une suppression de ce type, le développeur fera pointer n.droite (n.gauche respectivement) vers le pointeur nul, pour faire le ménage. Il peut être interessant de le conserver pour garder un 'historique' des modifications de la liste.

D Knuth développe son idée jusqu'à un algorithme complet de programmation sous contrainte qu'il appele les 'dancing links'. Il l'applique au problème des dames de Dijkstra, au problèmes des pentominos, des hexadiamants et aux tetrasticks.

On remarquera la présence de cet algorithme, appliqué à la résolution des célèbres problèmes de sudoku, dans cet article du wikipedia.