Algo de Donald Knuth
Algo de Donald Knuth - Algo - Programmation
Marsh Posté le 10-05-2006 à 19:24:57
Reply
Marsh Posté le 11-05-2006 à 18:58:37
Reply
Marsh Posté le 16-05-2006 à 09:54:48
moi je voyais plus une utilisation d'une heuristique type min-conflicts pour résoudre ce problème (un peu comme le problème des n-reines) 
Message édité par Giz le 16-05-2006 à 09:55:01
Marsh Posté le 16-05-2006 à 13:13:20
| blastman a écrit : Bonjour tout le monde
|
| Citation : Le problème de placer des chiffres sur une grille de n2×n2 comprenant n×n régions est prouvé NP-complet |
d'après le wikipedia.
Alors ton algo, j'aimerais bien le voir ! 
Marsh Posté le 16-05-2006 à 13:43:23
Plus de details sur le principe:
http://en.wikipedia.org/wiki/Dancing_Links
Marsh Posté le 23-05-2006 à 10:38:15
En fait c'est parce que c'est une grille de 9*9 que l'algo est rapide. D'autre part, l'algo s'interesse à la résolution du problème, pas à la génération d'un problème ce qui n'est pas exactement pareil car la résolution part déjà de nombres fixés sur la grille (donc plus rapide à résoudre car des contraintes sont déjà posées) plutôt que d'une grille vide.
Message édité par Giz le 23-05-2006 à 10:39:15
Sujets relatifs:
- [Algo][Résolut]Cherche algorithmes pour le Jeu du Taquin
- Algo de cryptage de texte
- [Algo] Recherche de sous chaîne
- Recherche algo ou programme pour détection de plan
- Algo pour corrigé des fautes de frappes...
- sit exo algo
- Algo génétique
- Algo du CRC
- algo de base
- Algo de combinaison
Marsh Posté le 10-05-2006 à 19:12:08
Bonjour tout le monde
Voilà, je cherche un algo. (le plus rapide possible) sur la menière de résoudre une grille de Sudoku. En cherchant sur la wikipedia j'ai trouvé ça
Donald Knuth a mis au point un algorithme qui fait appel aux listes doublement chaînées, et qui se révèle très efficace pour résoudre ce type de problème. Il est démontré que cet algorithme est tout indiqué pour la résolution d'un Sudoku, ne prenant que quelques millisecondes. Grâce à sa vitesse, il est maintenant préféré par la plupart des concepteurs logiciels.
est ce que vous avez un exemple de son algorithme (en c++ serait l'idéal) où alors avez vous un algorithme sous la main encore plus rapide ?
si vous avez des liens sur les listes doublement chainée en c++ ce serait sympa de les posté
Message édité par blastman le 10-05-2006 à 19:21:13
---------------
http://www.blastmanu.info