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:
- 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.
- Sélectionnez une colonne (représentant une contrainte).
- 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.
- 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).
- 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.
Voir aussi: http : //stackoverflow.com/questions/1518346/ –
Eh bien, je vais deviner que cela devrait vous aider: [Un résolveur de Sudoku en Java implémentant l'algorithme de Knuth's Dancing Links] (http://www.ocf.berkeley.edu/~jchu /publicportal/sudoku/sudoku.paper.html) –
Le code source complet de ce lien n'est plus disponible. Et les extraits de code contiennent des bogues. Plus précisément, la méthode uncover (ColumnNode c). Dans cet article, ce code est une copie de la méthode de couverture avec des éléments de la boucle for modifiés. L'itérateur de la boucle interne doit aller à gauche et non à droite, et les liens doivent être restaurés à l'original, pas répéter l'opération de couverture. Exemple: leftNode.getUp(). SetDown (leftNode); au lieu de leftNode.getUp(). setDown (leftNode.getDown()); –