lundi 10 janvier 2011

Étape 9 : Jouer et résoudre le Sudoku

Traitement pour trouver la grille et les chiffres

C'est vraiment étonnant de constater comme il est simple d'écrire un programme pour trouver une solution ou toutes les solutions d'un Sudoku.

Voici le pseudo-code pour le faire:

Fonction Trouver_toutes_les_solutions (Le_Sudoku)

    trouver le premier carré vide dans Le_sudoku
    s'il n'y a pas de carré vide
          vous avez trouvé une solution
          vous pouvez afficher, enregistrer ou imprimer Le_Sudoku
    sinon
          pour i = 1 à 9
               si vous pouvez placer i dans le carré vide
                    placer i dans le carré vide
                    appeler Trouver_toutes_les_solutions(Le_Sudoku)
                    placer 0 dans le carré vide

Fin de Trouver_toutes_les_solutions

Vous n'avez plus qu'à traduire ce pseudo-code en Java et ça marche!

Mais, ce code n'est pas le code plus performant. Nous pouvons l'améliorer, notamment avec  Dancing Links, ou DLX, qui est une technique proposée par le célèbre Donald Knuth. Voici quelques ressources très intéressantes concernant cette technique:
Dancing links
Knuth's Algorithm X
Exact Cover Matrix

Bien sûr, nous avons implanté cette excellente technique dans notre application.

Donc, maintenant, il vous suffit de jouer avec votre Sudoku. Mais parfois, le Sudoku est très difficile. Bien sûr, notre application peut donner une solution. Et notre application peut même dire s'il existe plus qu'une solution. Mais, demander la solution ne permet pas de savoir comment résoudre un Sudoku. Alors, pourquoi ne pas demander juste un indice? Si vous le faites, notre application vous donnera le chiffre suivant qu'il jouerait. À ce moment-là, vous pouvez avoir une de ces réactions:
  1. Oui, bien entendu, pourquoi n'ai-je pas trouvé ce chiffre  moi-même?
  2. Pourquoi ce chiffre est-il suggéré par l'application? Vous vérifiez le Sudoku un peu plus et vous comprenez! Maintenant, vous apprenez rapidement à résoudre un Sudoku
  3. Je ne sais pas pourquoi l'application propose ce chiffre, mais, au moins, je peux continuer

Voici l'écran affiché lorsque vous appuyez sur le bouton Indice. Il faut l'essayer! Vous le comprendrez très vite :



Quelle technique utilisons-nous pour proposer un chiffre pour donner un indice, pour les lignes par exemple? Très simple. . . comme d'habitude! Nous utilisons la fonction Trouver_toutes_les_solutions pas pour tous le Sudoku, mais plutôt pour la première ligne; après, pour toutes les solutions trouvées dans la première ligne, nous vérifions si un chiffre est toujours dans le même carré. Si oui, nous suggérons ce chiffre. Sinon, nous vérifions la ligne 2 jusqu'à la ligne 9. Si nous ne trouvons pas un chiffre toujours dans le même carré, nous disons que nous n'avons pas d'indice pour les lignes.

Vous voulez un conseil pour les colonnes? Il suffit d'appuyer sur le bouton Colonnes. Et ainsi de suite.

Amusez-vous bien!

Note : Vous pouvez enregistrer le Sudoku courant. Il est enregistré dans la mémoire auxiliaire dans le répertoire nommé com.rogerlebo.sudokuvision. Bien sûr, vous pouvez également récupérer un Sudoku que vous avez enregistré précédemment.

Aucun commentaire:

Enregistrer un commentaire