Application Android de Sudoku

L'objectif est de découvrir quelques aspects de la programmation en complétant une application pour Android permettant de jouer au Sudoku.

On rappelle le principe du Sudoku : il faut remplir une grille de 9x9 cases avec les nombres de 1 à 9 de manière à ce qu'aucune ligne, aucune colonne, et aucun groupe de 3x3 cases ne comporte deux fois le même nombre.

Nous allons progresser étape par étape pour compléter cette application. N'hésitez pas à appeler les enseignants si vous êtes bloqués !

Application de Sudoku

Installation

Si vous avez un téléphone sous Android, activez le mode débuggage (dans les paramètres, "options pour les développeurs"), et connectez-le à l'ordinateur. Sinon, nous vous fournissons une tablette : allumez-la et connectez-la à l'ordinateur.
Téléchargez l'application de Sudoku à compléter. Décompressez-la dans le répertoire "Z:".
Lancer Android Studio : une icône doit se trouver sur le bureau. Si ça n'est pas le cas, ouvrir l'explorateur et aller dans "C:Programmes/Android/Studio" et double-cliquer sur "studio64.exe".
Choisir "Open an existing Android Studio project", puis sélectionner le répertoire où vous avez décompressé l'application.
Android Studio va afficher une barre de progression (dans la barre en bas) : il compile l'application, c'est-à-dire qu'il transforme le programme en du code compréhensible par le téléphone ou la tablette.
Une fois qu'il a terminé, on peut installer l'application sur le téléphone ou la tablette : pour cela, cliquer sur le triangle vert ("Run 'app'") et choisir le téléphone ou la tablette dans "Choose a running device". L'application s'installe alors et se lance.

Découverte de l'application

Jouez un peu avec l'application : vous pouvez compléter les cases vides, de manière à remplir la grille de Sudoku qui est donnée en exemple.

Que se passe-t-il lorsqu'on se trompe, c'est-à-dire qu'on met une valeur illicite ? Le but de ce TP va être de vérifier que les valeurs entrées par l'utilisateur sont bien correctes, pour pouvoir le prévenir si ça n'est pas le cas.

Découverte du code source de l'application

Une application Android se programme dans le langage Java. Il s'agit d'un des langages de programmation les plus utilisés.

Revenez sur Android Studio. Dans la colonne de gauche, vous pouvez parcourir le code source de l'application. Les éléments principaux sont donc les programmes Java, qui se trouvent en dépliant le menu "app/java/fr.u_psud.keller.sudoku" : vous pouvez ouvrir les différents fichiers se trouvant à cet endroit pour voir à quoi le code ressemble. C'est normal de ne pas le comprendre !

Le fichier qui va nous intéresser plus particulièrement est le fichier "SudokuCheck", que vous allez devoir compléter.

Principe de l'application

Le fonctionnement de l'application est le suivant. Lorsque l'utilisateur clique sur une des cases initialement vide de la grille de Sudoku, le programme lance l'ouverture de la fenêtre demandant de choisir un nombre, ou de supprimer le nombre présent dans la case. Lorsque l'utilisateur choisit un nombre, le programme vérifie que le nombre choisi est bien possible, vu les contraintes imposées par la grille, puis :

si le nombre est correct, le met dans la case ;
sinon, affiche un message à l'utilisateur pour le prévenir.

C'est le rôle du fichier "SudokuCheck" de gérer la vérification, en définissant le sous-programme appelé check. Pour l'instant, ce sous-programme ne comporte qu'une seule instruction: return true;, ce qui signifie que pour l'instant, il renvoie toujours que l'action de l'utilisateur est correcte, sans faire aucune vérification. Ça va être à vous de compléter ce sous-programme pour faire les vérifications nécessaires, et renvoyer que l'action de l'utilisateur est incorrecte lorsqu'on trouve qu'une des contraintes n'est pas vérifiée.

Représentation des objets

Le sous-programme check prend des arguments : (int i, int j, int v, int[][] values), qui représentent les choix de l'utilisateur et la grille de Sudoku. i, j, v et values sont appelées des variables du sous-programme check.

La variable values contient la grille de Sudoku en partie complétée. La représentation est la suivante : c'est une grille contenant des nombres, dont chaque ligne et chaque colonne est numérotée. Par exemple, la grille de Sudoku qui sert d'exemple est la suivante :

	0	1	2	3	5	6	7	8
0	9			5	1			6
1		7		8	3		2
2			8			7
3			7	9	5	8
4	6							9
5			5	6	8	4
6			1			5
7		4		3	2		7
8	7			4	6			8

Nous dirons par exemple que dans la case sur la ligne 6 et la colonne 2 se trouve la valeur "1".

En Java, la variable values représente donc cette grille de la manière suivante : la case sur la ligne 6 et la colonne 2 est représentée en Java par values[6][2], en indiquant d'abord le numéro de la ligne, puis celui de la colonne. Le code values[6][2] contient donc la valeur "1".

L'action de l'utilisateur est contenue dans les variables i, j et v : v contient un nombre entre 0 et 9, qui est la valeur que l'utilisateur souhaite entrer dans la case sur la ligne i (un nombre entre 0 et 8) et la colonne j (également un nombre entre 0 et 8). Le principe est donc que l'utilisateur souhaite modifier la valeur de values[i][j] pour la remplacer par la nouvelle valeur v.

Programmons...

Une première vérification

Il n'est pas correct de mettre la valeur "9" dans la case sur la ligne 0 et la colonne 6 : il y a déjà un "9" sur cette même ligne.

Nous allons compléter le code pour effectuer cette vérification : si l'utilisateur choisit de mettre "9" à cet endroit, nous voulons dire qu'il y a une erreur en renvoyant la valeur "false".

On peut programmer cela en ajoutant le code suivant:


  if (i == 0 && j == 6 && v == 9) {

    return false;

  }

qui signifie la phrase suivante : "si i est la ligne 0, et j est la colonne 6, et l'utilisateur veut y mettre la valeur 9, alors on dit que c'est incorrect". "&&" signifie "et", et "==" permet de tester la valeur d'une variable.

Ajouter ce code juste en dessous de la ligne "// À compléter".
Tester : installer de nouveau l'application en cliquant sur le triangle vert, et une fois qu'elle s'est lancée sur le téléphone ou la tablette, essayez de mettre "9" dans la case ligne 0, colonne 6, et regardez ce qui se passe.
De la même manière, compléter le code pour vérifier que l'utilisateur ne met pas "5" dans la case de ligne 4 et colonne 5. Tester.
Ajouter quelques autres vérifications similaires, et testez-les.

Généralisons un peu

Ce que nous venons de faire est très spécifique à cet exemple de grille de Sudoku. Le but de la programmation est de faire quelque chose de plus générique, qui va fonctionner dans toutes les situations.

Nous voulons empêcher de mettre "9" dans la case ligne 0, colonne 6, car cette valeur est déjà présente sur la même ligne, colonne 0. Le problème n'est donc pas tellement que v vaille "9", mais qu'il vaille la même chose que values[0][0]. On va donc plutôt programmer cela ainsi:


  if (i == 0 && j == 6 && v == values[0][0]) {

    return false;

  }

De cette façon, si on remplace le "9" par "8", et que l'utilisateur essaie de mettre "8", on lui affichera également une erreur !

Modifiez votre programme pour utiliser ainsi values au lieu de mettre directement les valeurs. Testez.

Pour l'instant, on compare seulement ce que veut mettre l'utilisateur dans la case ligne 0, colonne 6 avec ce qui est présent dans la case ligne 0, colonne 0. Cependant, on veut interdire à l'utilisateur de mettre n'importe quel nombre présent dans la ligne.

En utilisant plusieurs fois le bloc d'instructions du paragraphe précédent (avec quelques modifications), interdisez, lorsque i vaut 0 et j vaut 6, la valeur v à être l'une des valeurs présentes dans la ligne 0. On ne veut donc pas que v vaille values[0][0], mais pas non plus values[0][1], values[0][2], ... et ainsi de suite jusqu'à values[0][8]. Testez, en essayant non seulement de mettre 9, mais aussi 5, 1, et 6.
Remarquez que cependant, ce n'est pas gênant si v vaut values[0][6] : à ce moment-là, il ne se passe rien (l'utilisateur met la valeur qui était déjà dans la case). N'interdisez donc pas cela, et testez.

Automatisons

Le travail que nous venons de faire est très fastidieux, puisque nous avons dû mettre 7 fois des instructions très similaires pour gérer la ligne 0. Un deuxième but de la programmation est de pouvoir automatiser cela, plutôt que d'écrire plusieurs fois du code proche. Pour cela, nous allons utiliser une boucle: nous allons parcourir toutes les cases de la ligne 0 (sauf la case de la colonne 6), et vérifier qu'elles ne prennent pas la valeur v. Cela peut se programmer de la façon suivante :


  if (i == 0 && j == 6) {

    for (int c = 0; c < 9; c++) {

      if (c != 6 && v == values[0][c]) {

        return false;

      }

    }

  }

Cela signifie que, toujours dans le cas de la modification de la ligne 0, colonne 6 (if (i == 0 && j == 6)), la nouvelle variable c va prendre successivement les valeurs entre 0 (c = 0) et 8 (c < 9), et que à chaque fois, on va dire qu'il y a une erreur si la valeur v est déjà sur la ligne 0 et sur la colonne c (v == values[0][c]). On ne veut pas renvoyer d'erreur dans le cas de la colonne que l'utilisateur est en train de modifier, c'est pourquoi on teste si c et différent de 6 (c != 6 : != signifie "différent").

Remplacez tout ce que vous avez écrit dans les parties précédentes par ce code. Testez.
Pourquoi le code suivant est-il équivalent ?
if (i == 0 && j == 6) { for (int c = 0; c < 9; c++) { if (c != j && v == values[i][c]) { return false; } } } Remplacez et testez.

Généralisons plus

Nous avons traité le cas uniquement de la case ligne 0, colonne 6. Cependant, la boucle donnée dans la question précédente est suffisamment générale pour fonctionner avec n'importe quelle case ligne i, colonne j : il suffit d'enlever le test if (i == 0 && j == 6) !

Enlevez ce test (attention à enlever aussi les accolades ouvrante et fermante correspondantes) et testez, cette fois-ci avec n'importe quelle case.
Testez aussi en vérifiant que l'application fonctionne toujours bien si on met des valeurs correctes : il ne faut pas renvoyer trop d'erreur !

À vous !

Gestion des colonnes

Inspirez-vous de ce qu'on vient de faire pour ajouter au code une vérification qu'on ne met pas une valeur déjà présente sur la colonne j. N'hésitez pas à faire des petits dessins pour bien comprendre ce qui se passe ! Testez.

Gestion des zones 3x3

Enfin, ajoutez la vérification pour les cases d'une même zone de 3x3. Pour cela, un moyen de faire est de regarder dans quelle partie de la zone 3x3 se trouve la case ligne i, colonne j : par exemple, si "i modulo 3 vaut 0" (ce qui se dit en Java i % 3 == 0), alors on est sur la première ligne de la zone ; ou encore, si "j modulo 3 vaut 1" (ce qui se dit en Java j % 3 == 1), alors on est sur la colonne du milieu de la zone.