É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.

Étape 8 : Donner les chiffres

Nous retournons le chiffres du Sudoku avec le très simple code Java suivant :

Uri data = Uri.parse(sudoku_capture);

Intent result = new Intent(null, data);

setResult(RESULT_OK, result);

finish();

Display

Dans cette étape, toutes les photos donnent le même résultat. Ci-dessous, vous pouvez voir le résultat final avec 3 téléphones Android différents.

Voici quelques observations concernant les images :

• l'application peut être en anglais ou en français selon la langue dans laquelle vous définissez pour votre téléphone
• plus grande est la hauteur de l'écran du téléphone, plus vous voyez de nouveaux boutons ou des boutons plus hauts; les mêmes fonctions des boutons manquants dans les 2 premières images peuvent être obtenues avec le bouton menu

Étape 7 : Placer les chiffres sur la photo

Traitement pour trouver la grille et les chiffres

Tous les chiffres sont trouvées. Il s'agit maintenant de les afficher sur la photo.

Afficher

Donc, maintenant, nous voulons seulement  afficher les chiffres sur la photo originale. Le défi est de donner la perspective originale pour les chiffres trouvés et d'appliquer cette perspective sur la photo. Pour ce faire, nous utilisons cette fois la miraculeuse méthode  setPolyToPoly de la classe Matrix. Mais, à première vue, ce n'est pas très facile à comprendre. Il m'a fallu beaucoup de temps pour bien utiliser la classe correctement.C'est pourquoi nous présentons le code exact de notre programme Java.

Voici quelques variables déjà définies :

bitmap : la photo originale de dimension 512X512
sudoku_dim : la dimension de la grille extraite (sudoku_dim = largueur = hauteur)
(x1,y1), (x2,y2), (x3,y3), (x4,y4) : les coordonnées des 4 coins de la grille sur la photo originale
sudoku_capture : les 81 chiffres trouvés (une cellule vide est représentée par un blanc)

 Voici le code complet :

Bitmap bitmap_to_display = bitmap.copy(Bitmap.Config.RGB_565, true);

    

float orig [] = new float [] {

            0, 0,

            sudoku_dim, 0,

            sudoku_dim, sudoku_dim,

            0, sudoku_dim

            };        

float dest [] = new float [] {

            (float) x1, (float) y1,

            (float) x2, (float) y2,

            (float) x3, (float) y3,

            (float) x4, (float) y4

            };

Matrix matrice = new Matrix();

matrice.setPolyToPoly(orig, 0, dest, 0, 4);

       

Canvas canvas;                  

canvas = new Canvas(bitmap_to_display);

canvas.setMatrix(matrice);

       

int width_square, height_square;                       

width_square = sudoku_dim / 9;

height_square = width_square;

                 

Paint paint_chiffre = new Paint();

paint_chiffre.setTextSize(34);

paint_chiffre.setTypeface(Typeface.DEFAULT_BOLD);

paint_chiffre.setColor(Color.GREEN);

     

String le_nombre;

int iimage, jimage;

int deb_x_square, deb_y_square;

int idx = -1;

for (iimage = 0; iimage < 9; iimage++) {

      deb_y_square = iimage * height_square + 12 + iimage * 2 / 3 ;

      for (jimage = 0; jimage < 9 ; jimage++){

        deb_x_square = jimage * width_square + 2 + jimage / 3; 

        idx++;           

        le_nombre = sudoku_capture.substring(idx,idx + 1);

        if (!le_nombre.equals(" "))

            canvas.drawText(le_nombre,

                        deb_x_square + 8, deb_y_square + 18,
                        paint_chiffre);                         

      }

}

image.setImageBitmap(bitmap_to_display);

Et ça marche!

Pour afficher les chiffres à n'importe quel angle de 0° à 360°, il s'agit de changer les points (x,y) en conséquence.

Dans les captures d'écrans des mêmes photos, nous voyons les chiffres avec la bonne perspective :

Étape 6 : Trouver les chiffres et les placer sur la grille

Traitement pour trouver la grille et les chiffres

Nous avons trouvé la grille et cette grille est maintenant carrée. L'objectif de l'étape 6 est de trouver les chiffres. Il y a 3 étapes pour pour ce faire:

1. trouver les 81 carrés
2. trouver et isoler le chiffre dans un carré 
3. reconnaître le chiffre dans un carré

Comme nous avons les coordonnées des 4 coins, il est maintenant très simple de calculer les coordonnées des 81 carrés du Sudoku. Il suffit de diviser la largeur par 9 et la hauteur de 9.

Pour trouver et isoler le chiffre dans un carré, nous utilisons 2 techniques:

1. supprimer les 1 isolés (c'est ce que nous appelons la transformation Pac-Man)
2. inonder les régions

La transformation de Pac-Man vient de l'ancien jeu Pac-Man. Sur un carré, nous supprimons d'abord tous les 1 isolés collés à une région. Et avec la technique de l'inondation, on trouve la plus grande région qui est, soit dit en passant, le chiffre. Voici maintenant un exemple pour le chiffre 8:

Afin de reconnaître le chiffre, il y a un nombre très important de techniques. Nous avons testé beaucoup d'entre elles. Celle que nous n'avons pas encore testé est le réseau de neurones. Nous allons probablement l'utiliser dans une prochaine version de notre application. Pour l'instant, nous utilisons notre propre technique qui est en fonction de la forme du chiffre. Et la technique est basée sur le fameux algorithme de l'inondation.

Donc, pour reconnaître le chiffre, nous appliquons la très utile technique de l'inondation comme suit:

• inonder la région supérieure gauche avec 2
• inonder la région inférieure gauche avec 3
• inonder la région supérieure droite avec 4
• inonder la région inférieure droite avec 5
• inonder toutes les régions autres (trous) avec 6 et plus
• ne pas inonder la première ligne, la dernière ligne, la première colonne et la dernière colonne

Nous obtenons ceci pour le chiffre 8:

Ensuite, nous définissons un seuil qui dépend de la hauteur du chiffre. Quand :

• la plus grande région en haut à gauche < seuil
• la plus grande région en bas à gauche < seuil
• la plus grande région en haut à droite < seuil
• la plus grande région en bas à droite < seuil
• la prochaine plus grande région dans la partie supérieure du chiffre >= seuil
• la prochaine plus grande région dans la partie inférieure du chiffre >= seuil

nous reconnaissons le chiffre 8.

Voici un autre exemple. Quand:

• la plus grande région en haut à gauche < seuil
• la plus grande région en bas à gauche >= seuil
• la plus grande région en haut à droite >= seuil
• la plus grande région en bas à droite < seuil

nous reconnaissons le numéro 5.

Voici quelques caractéristiques de notre technique:

• c'est très facile à comprendre
• c'est  très simple à programmer
• c'est  très rapide
• c'est presque complètement indépendant des polices généralement utilisées dans une grille de Sudoku (nous avons choisi une police différente pour chaque photo présentée ci-dessous)
• le taux de reconnaissance est très bon

Mais, nous pensons que le taux de reconnaissance de l'algorithme de réseau neuronal est probablement meilleur. Nous allons le tester dans une prochaine version.

Maintenant, que faisons-nous pour trouver les chiffres à n'importe quel angle de 0° à 360°? Voici le pseudo-code:

Trouver les chiffres

S’il y a 0 chiffre

                Pivoter 90°

                Trouver les chiffres

                S’il y a des chiffres en double dans les lignes,  les colonnes ou les grilles 3X3

                               Pivoter 270°

                               Trouver les chiffres

                               Si nombre de chiffres en double à 90° < nombre de chiffres en double à 270°

                                               Donner chiffres à 90°

                               Sinon

                                               Donner chiffres à 270°

                Sinon

                               Donner chiffres à 90°

Sinon

S’il y a des chiffres en double dans les lignes,  les colonnes ou les grilles 3X3

                Pivoter 180°

                Trouver les chiffres

                Si nombre de chiffres en double à 0° < nombre de chiffres en double à 180°

                               Donner chiffres à 0°

                Sinon

                               Donner chiffres à 180°

                Sinon

                               Donner chiffres à 0°

Voilà!

Soit dit en passant, tous les chiffres et les lettres ont normalement une hauteur supérieure à la largeur. Lorsque nous trouvons un chiffre dont la largeur est supérieure à la hauteur, nous considérons que ce n'est pas un chiffre. C'est pourquoi nous pouvons avoir cette condition "S'il y a 0 chiffre".

Afficher

Comme vous vous en souvenez certainement, nous avons démarré une unité de traitement à l'étape 1 pour trouver la grille et les chiffres. Donc, avant d'afficher l'écran suivant, il ne faut pas oublier d'attendre que l'unité de traitement soit terminée.

Dans les captures d'écran des mêmes photos, nous voyons maintenant les chiffres :

Il y a 2 étapes pour demo 5:

Il y a 3 étapes pour demo 6; dans l'étape 1, nous trouvons 0 chiffre :

Étape 5 : Transformation de perspective

Traitement pour trouver la grille et les chiffres

Souvent, la grille est déformée et il est presqu'impossible de trouver des chiffres si la grille n'est pas carrée. Nous avons besoin d'un moyen pour passer d'une grille déformée à une grille carrée. La façon miraculeuse est d'utiliser la transformation de perspective aussi appelée "projective mapping"  ou  "2D mapping". Donc, nous voulons transformer la grille verte entourée à gauche vers la grille à droite :

Pour utiliser la transformation de perspective, il y a une méthode nommée setPolyToPoly dans la classe Matrix de Android. Mais, parfois, une partie des coins de la grille est perdue et, par conséquent, certains chiffres peuvent être perdus également. Donc, nous avons décidé d'écrire notre propre code Java pur pour réaliser la transformation de perspective.

Mais, où trouver toutes les informations dont nous avons besoin pour faire cela? Pour sûr, maintenant, vous connaissez la réponse. . . dans le merveilleux livre de Burger et Burge. . . bien sûr. Ceci est très clairement expliqué dans le chapitre 16 page 380. C'est appelé "projective mapping" dans le livre. Comme d'habitude, vous pouvez trouver le code Java ici:

Chapter 16 Geometric Operations

Vous pouvez voir des exemples de vraies codes Java sur le blogue anglais de la page actuelle:

Code Java sur le blogue anglais



Afficher

Dans les captures d'écran des 4 mêmes photos, on voit les transformations de perspective. Noter la quatrième où nous n'avions pas les 4 coins de la photo originale :

Code Java

Vous pouvez voir des exemples de vraies codes Java sur le blogue anglais de la page actuelle:

Code Java sur le blogue anglais

Étape 4 : Trouver la grille

Traitement pour trouver la grille et les chiffres

Maintenant, nous devons trouver les 4 coins de la grille. Il y a 2 étapes:

1. trouver toutes les lignes droites possibles dans la grille
2. trouver les 4 coins de l'intersection des 4 lignes droites les plus éloignées

Pour trouver toutes les lignes droites possibles dans la grille, nous utilisons le célèbre algorithme de la transformation de Hough.

Voici l'équation d'une ligne droite dans la forme normale de Hesse:

      r = x . cos(θ) + y . sin(θ)

Pour chaque point (x,y) dans l'image obtenue dans l'étape précédente, nous varions θ de 0 à 180 pour obtenir r. Et, (θ,r) devient les coordonnées d'un nouveau tableau nommé accumulateur.

Une explication très compréhensible de cet algorithme est donnée dans . . . le merveileux libre de Burger et Burge encore une fois, dans le chapitre 9 à la page 155.

Voulez-vous voir quelques lignes de code Java pour cet algorithme? Pourquoi pas? Vérifiez le chapitre 9 juste ici:

Chapter 9 Detecting Simple Curves

Vous pouvez également trouver quelques explications utiles, courtes et visuelles de l'algorithme ici :
Hough Transform in Wikipedia

Maintenant, essayons de trouver les 4 coins. Comment pouvons-nous faire? Premièrement, nous trouvons la ligne la plus à gauche, la ligne la plus à droite, la ligne la plus haute et la ligne la plus basse dans le tableau accumulateur. Avec l'intersection de chacune de ces 4 lignes, nous trouvons les 4 coins. N'est-ce pas que c'est simple? Dans le merveilleux livre  de Burger et Burge, il y a une section dont le titre est "Analyzing the Accumulator Array", page 163, qui décrit exactement ce que nous voulons. Quel bon livre!

Voici une brève analyse de l'algorithme de la transformation de Hough :

Avantages:

• facile à programmer
• trouver la grille  même si la forme du Sudoku n'est pas carrée
• trouver la grille même si nous n'avons aucun coin sur la photo

Désavantages:

• mauvaise performance parce qu'il y a trop de calculs et d'itérations

Pour améliorer les performances de l'algorithme, on utilise 3 techniques:

1. cos(θ) et sin(θ) sont mis dans une antémémoire car nous en avons besoin dans de nombreux calculs
2. nous faisons varier θ de 0 à 180 par 4, ce qui est suffisant pour trouver la grille
3. nous prenons (x, y) dans le tableau original à chaque 5 points, ce qui est suffisant pour trouver la grille

Avec le Nexus One roulant Android 2.2, il faut 0,08 seconde pour traiter cette étape 4. Finalement, la performance n'est pas si mal.

  

Afficher

Dans les captures d'écran des mêmes photos, nous voyons les 4 lignes droites en vert et les 4 coins en rouge . . . quand il y a un coin sur la photo :   

Étape 3 : Inonder

Traitement pour trouver la grille et les chiffres

Nous devons trouver la grille dans l'image binaire (image en noir et blanc). Un moyen très simple de le faire est d'utiliser un algorithme pour le marquage de région c'est-à-dire en remplissant une région, ce que nous appelons inonder une région. Il est étonnant de voir comment ça prend peu de lignes de code Java pour trouver la plus grande région de l'image qui est, soit dit en passant, la grille

Vous pouvez voir le code Java à partir du chapitre 11 à la page 199 du merveilleux livre de Burger et Burge. Il existe 3 versions de code Java pur dans le livre :

• Version récursive (recursive version)
• Version en profondeur d'abord (depth-first version) : c'est celle utilisée ici
• Version en largeur d'abord (breadth-first version)

Vous pouvez voir le code Java dans le chapitre 11 ici :
Java code of chapter 11 to find regions in binary images

Vraiment, un grand livre!

Nous exécutons le même algorithme pour trouver les chiffres plus tard.

Vous pouvez voir des exemples du pseudo-code sur le blogue anglais de la page actuelle:

Pseudo-code sur le blogue anglais

Afficher

Voici les captures d'écran des photos que nous obtenons après l'inondation des régions :

Étape 2 : Noir et blanc

Traitement pour trouver la grille et les chiffres

Comme nous n'avons pas besoin de l'information concernant la couleur, nous convertissons l'image en gris avec ce code :
 

Bitmap bmwork = Bitmap.createBitmap(512, 512, Bitmap.Config.RGB_565);

ColorMatrix colorMatrix = new ColorMatrix();

colorMatrix.setSaturation(0);

Paint paint = new Paint();

ColorMatrixColorFilter cmcf = new ColorMatrixColorFilter(colorMatrix);

paint.setColorFilter(cmcf);

Canvas drawingCanvas = new Canvas(bmwork);

drawingCanvas.drawBitmap(bitmap, 0, 0, paint);

Nous devons maintenant convertir le gris en noir et blanc, noir devient l'arrière-plan (0) et le blanc devient la foregound (1). Ce faisant, la grille et les nombres seront convertis à 1. Pour ce faire, nous avons besoin d'un seuil. Beaucoup  d'informations sont données à ce sujet dans les références indiquées dans le deuxième message. Donc, nous ne répéterons pas cette information ici.

Premièrement, pour améliorer la performance, nous convertissons l'image  à un tableau comme ceci :

int imaget [][] = new int [512][512];    

for (i = 0; i < 512; i++)

       bmwork.getPixels(imaget [i], 0, 512, 0, i, 512, 1);  

Nous utilisons un algorithme avec une région de 12x12 pour trouver la grille et les chiffres. Pour chaque région, nous calculons le niveau de gris moyen, et nous utilisons un seuil de 1,08. Donc, pour le seuil, nous avons ce code:

if (imaget[i][j] < 1.08 * somme_pixels / 144)

    image1[i][j] = 1;

else

    image1[i][j] = 0;

Notes :

1. Les trois petits boutons passent du noir au magenta lorsque l'unité de traitement est terminée, ce qui signifie que la grille et les chiffres ont tous été trouvés et sont prêts.
2. Quand une photo est prise, nous enregistrons la photo dans le fichier nommé photo.jpg dans la mémoire auxiliaire du téléphone Android. Vous pouvez appuyer sur le bouton menu pour enregistrer la photo avec un autre nom ou pour ouvrir une ancienne photo. La photo que vous enregistrez ou récupérez est placée dans la mémoire auxiliaire dans le répertoire nommé com.rogerlebo.sudokuvision. Si vous souhaitez récupérer la dernière photo prise, appuyez simplement sur le bouton de retour sur l'écran pour prendre une photo 

Afficher 

Voici les captures d'écran des photos présentées plus tôt :