FICHIER EXCEL PERMETTANT DE RÉSOUDRE UN PROBLÈME SUDOKU. APRÈS LANCEMENT D'UNE M
Cacophrene
Messages postés251Date d'inscriptionlundi 29 mars 2004StatutMembreDernière intervention 4 mars 2008
-
17 mars 2006 à 20:02
cdef
Messages postés10Date d'inscriptionvendredi 10 février 2006StatutMembreDernière intervention10 mars 2011
-
10 avril 2006 à 13:49
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
cdef
Messages postés10Date d'inscriptionvendredi 10 février 2006StatutMembreDernière intervention10 mars 2011 10 avril 2006 à 13:49
Bonjour,
Je n'ai pas vu la solution us_30, mais pour le plaisir de réaliser un algorithme avec backtrack en VBA (J'ai fait par le passé un compilateur Prolog), je me suis fait une macro Excel qui résoud les Sudoku, même diabolique en quelques secondes. Je ne l'ai pas diffusé pour ne pas casser le plaisir des passionnés de Sudoku. L'algorithme est simple :
Après avoir saisi la grille initiale, et stockée dans un tableau, il suffit de boucler sur toutes les solutions possibles.
S'il y une solution, la macro la trouvera (parfois il y en a plusieurs).
L'astuce est de calculer à chaque fois les solutions possibles pour chaque case, et de fixer en premier les cases qui n'ont qu'une solution.
Le tout fait environ 50 lignes.
Cacophrene
Messages postés251Date d'inscriptionlundi 29 mars 2004StatutMembreDernière intervention 4 mars 20081 17 mars 2006 à 20:02
Salut !
On en revient toujours au débat entre la stratégies difficilement démontrable" et le "rebroussement difficilement stratégique" ! Je m'explique... D'un côté, les stratégies de résolution garantissent une solution rapide, mais démontrer qu'elles résolvent toutes les grilles est délicat (parfois même très ardu, car ce sont des problèmes d'algorithmique qui sont loin d'être triviaux !). La technique rebroussement (pour plus d'infos : clic sur mon nom et clic sur la source "Solveur de sudoku" déposée il y a quelque temps déjà sur VBFrance), quant à elle, satisfera le matheux rigoureux en se prêtant bien à une démonstration d'algorithmique, MAIS le temps de calcul sera globalement plus long (quoique raisonnable, il ne s'agit pas de millions d'années !) que celui des stratégies (autre avantage des stratégies : la méthode de résolution est plus "humaine" que celle d'un rebroussement). D'où ce que je disais : des stratégies peu démontrables et un rebroussement peu stratégique ! Cela dit, c'est une bonne source (mais il existait déjà celle de us_30, également pour Excel).
10 avril 2006 à 13:49
Je n'ai pas vu la solution us_30, mais pour le plaisir de réaliser un algorithme avec backtrack en VBA (J'ai fait par le passé un compilateur Prolog), je me suis fait une macro Excel qui résoud les Sudoku, même diabolique en quelques secondes. Je ne l'ai pas diffusé pour ne pas casser le plaisir des passionnés de Sudoku. L'algorithme est simple :
Après avoir saisi la grille initiale, et stockée dans un tableau, il suffit de boucler sur toutes les solutions possibles.
S'il y une solution, la macro la trouvera (parfois il y en a plusieurs).
L'astuce est de calculer à chaque fois les solutions possibles pour chaque case, et de fixer en premier les cases qui n'ont qu'une solution.
Le tout fait environ 50 lignes.
17 mars 2006 à 20:02
On en revient toujours au débat entre la stratégies difficilement démontrable" et le "rebroussement difficilement stratégique" ! Je m'explique... D'un côté, les stratégies de résolution garantissent une solution rapide, mais démontrer qu'elles résolvent toutes les grilles est délicat (parfois même très ardu, car ce sont des problèmes d'algorithmique qui sont loin d'être triviaux !). La technique rebroussement (pour plus d'infos : clic sur mon nom et clic sur la source "Solveur de sudoku" déposée il y a quelque temps déjà sur VBFrance), quant à elle, satisfera le matheux rigoureux en se prêtant bien à une démonstration d'algorithmique, MAIS le temps de calcul sera globalement plus long (quoique raisonnable, il ne s'agit pas de millions d'années !) que celui des stratégies (autre avantage des stratégies : la méthode de résolution est plus "humaine" que celle d'un rebroussement). D'où ce que je disais : des stratégies peu démontrables et un rebroussement peu stratégique ! Cela dit, c'est une bonne source (mais il existait déjà celle de us_30, également pour Excel).
Cordialement,
Cacophrène