Je ne suis pas un très grand fan des sudokus, mais ça fait un moment déjà que je me demande s’il serait facile ou non de faire un programme pour les résoudre.
J’ai donc mis les mains dans le cambouis et voilà une appli java qui résoud tous les niveaux (enfin je crois) de ce jeu particulièrement à la mode actuellement.
Pour exemple, j’ai utilisé trois grilles et deux façon (algorithmes pour les intimes) - une plutôt brute force et l’autre un peu plus fine - pour résoudre la grille et voici les résultats :
Grille 1 : niveau normal
méthode 1 : 15ms et 874 itérations
méthode 2 : 15ms et 123 itérations
Grille 2 : niveau diabolique
méthode 1 : 47ms et 11586 itérations
méthode 2 : 16ms et 289 itérations
Grille 3 : niveau crazy
méthode 1 : 15ms et 162 itérations
méthode 2 : 2407ms et 104367 itérations
Comme on peut le constater les méthodes sont inégales, il faut dire que la grille diabolique ne comporte que 10 chiffres de départ ce qui peut expliquer l’avantage de la brute force.
Commentaires récents