L'algorithme Dancing Links - Une explication moins explicative mais plus sur la mise en œuvre?

Question

J'ai travaillé sur un Sudoku Solver, mon solveur actuel utilise l'algorithme de retour arrière mais il prend encore trop de temps. Je souhaite réduire à moins d'une seconde pour la plupart des cas. En tant que tel, j'ai décidé de le réécrire avec l'algorithme des liens de danse, en comprenant que c'est l'une des meilleures méthodes de bruteforce qui fonctionne bien, en particulier avec un problème de contrainte tel que le Sudoku Puzzle.

J'ai essayé de lire le Wiki et Knuth's paper, mais les deux sont difficiles à comprendre et extrêmement verbeux. J'ai également lu la version de Sudopedia dessus, et il semble qu'une fois qu'il est arrivé à l'implémentation du Sudoku, il est devenu trop abstrait.

Quelqu'un peut-il essayer d'expliquer l'algorithme de Dancing Links non pas en termes de dérivation mais de mise en œuvre? (serait génial d'utiliser le Sudoku comme exemple)

Merci!

Answer 1

Vous pourriez être intéressé par my implementation in javascript.

---

Tout d'abord, vous devez comprendre la couverture exacte. Un problème de couverture exacte est un problème où vous avez un tas de choix, et un ensemble de contraintes et votre défi est de sélectionner un tas de choix qui rempliront chaque contrainte exactement une fois. Par exemple, prenons le cas de quelqu'un qui crée sa routine de danse sur glace. Ils ont un certain nombre de trucs dont ils ont besoin pour montrer aux juges, et ne veulent pas faire n'importe quel tour plus d'une fois. Ils ont un certain nombre de séquences qui sont des groupes de trucs qui peuvent être assemblés et ils veulent choisir la sélection idéale de séquences pour couvrir toutes les figures une fois. Dans cet exemple, les contraintes sont qu'ils doivent effectuer chaque tour. Les choix sont les séquences possibles qu'ils pourraient intégrer dans leur routine. Une bonne façon de représenter les problèmes de ce genre consiste à dessiner une table où les contraintes sont des colonnes et les choix sont des lignes, et vous avez un grand X dans les cellules où un choix particulier remplit cette contrainte. Il se trouve que, compte tenu des contraintes et des choix appropriés, le sudoku peut être décrit comme un problème de couverture exacte.

---

Ok, en supposant que vous avez que, maintenant, vous devez comprendre l'algorithme X. Knuth a dit de lui « l'algorithme X est simplement une déclaration de l'approche évidente d'essais et d'erreurs. (En effet, je peux ne pense à aucun autre moyen raisonnable de faire le travail, en général.) ". Donc, voici ma description de l'algorithme X:

1. Si votre table n'a pas de colonnes, arrêtez - vous l'avez résolu. Si vous avez une solution partielle stockée, alors c'est en fait une vraie solution, renvoyez-la.
2. Sélectionnez une colonne (représentant une contrainte).
3. Recherchez une ligne avec une croix dans cette colonne (représentant un choix qui remplit cette contrainte). Ajoutez-le à un type de structure où vous stockez des solutions potentielles. Si vous ne pouvez pas trouver une rangée, abandonnez - il n'y a pas de solutions.
4. Supposons que la ligne que vous avez trouvée dans 3 figure dans la solution, donc supprimez toutes les colonnes dont le X est dans cette ligne.Tout en supprimant toutes ces colonnes, supprimez également toutes les lignes qui ont un X dans les colonnes que vous supprimez (parce que vous avez déjà satisfait la contrainte, donc vous êtes empêché de choisir quelque chose qui le satisferait à nouveau).
5. Essayez maintenant récursivement de résoudre la table réduite. Si vous ne pouvez pas, supprimez la ligne que vous avez essayée de la structure de solution potentielle, restaurez toutes les lignes et colonnes que vous avez supprimées aux étapes 3 et 4 et essayez une ligne différente. Si vous n'avez plus de lignes, abandonnez - il n'y a pas de solutions.

---

Maintenant que vous comprenez cela, vous pouvez comprendre les liens de danse. Dancing Links est un moyen efficace de mettre en œuvre cet algorithme. Le point clé des liens de danse est que dans une liste chaînée, lorsque vous supprimez un nœud (ce qui peut être fait efficacement en modifiant les pointeurs de ses voisins), le nœud que vous avez supprimé contient toutes les informations dont vous avez besoin pour le rajouter à la liste liée (dans le cas où il se trouve que vous aviez tort quand vous avez deviné que cela faisait partie de la solution). Cela s'ajoute au fait que si vous faites circuler toutes vos listes liées alors soudainement vous perdez beaucoup de cas spéciaux, c'est à peu près tous les liens de danse.

Answer 2

Bien que cette question est très vieux, je pensais que je rajouterais:

Cette page fait l'algorithme très facile à comprendre: Zendoku writeup. Jusqu'à ce que je lise à ce lien, je pensais que ce doit être un algorithme super-avancé, mais vraiment une fois que vous pouvez le visualiser, c'est juste une solution vraiment ingénieuse mais simple.

Aussi my implementation en C# devrait être assez facile à lire ... serait utile de diviser les différentes classes en différents fichiers, je suis sûr.
Il s'agit en grande partie d'une implémentation directe du pdf de Knuth, mais avec quelques optimisations orientées objet (en fait depuis quelques mois je ne me souviens pas combien je me suis écarté du pdf)