Bonjour, à tous je viens de commencer à suivre des cours sur java à la Teluq et j'aimerai
avoir vos conseils sur différents points.

Le projet consiste à créer une application sudoku ayant ces caractéristiques:

1-Les joueurs de l’application SUDOKU doivent pouvoir remplir la grille en cliquant sur une case et en entrant un chiffre (de 1 à 9) au clavier. Si les joueurs font une erreur, ils peuvent revenir la corriger.

2-Les joueurs ne peuvent pas modifier les chiffres générés dans la grille de départ. Par contre, ils peuvent vider toute la grille en sélectionnant dans le menu Fichier la fonction qui permet de vider la grille.

3-Dans le menu Fichier, à l'exception de la fonction qui permet de vider la grille, les joueurs doivent pouvoir, entre autres, enregistrer, corriger, résoudre une grille et quitter l’application.

4-Dans le menu Gestion de la grille, les joueurs doivent pouvoir choisir une grille selon le niveau désiré : débutant, intermédiaire et avancé.

5-Dans le menu Fonctions avancées, les joueurs peuvent copier la grille dans le presse-papier ainsi qu'imprimer à la fois la grille et sa solution. L’impression de la grille permet à d’autres joueurs de résoudre le SUDOKU sur papier.

6-Dans le menu Aide, les joueurs peuvent à tout moment afficher les règles du jeu ainsi que les informations concernant l’application SUDOKU.

Bon pour l'instant comme je vous l'ai dit je suis au début de mon apprentissage, donc je suis en train de créer des algorithmes pour les différents niveaux de jeux.

Les techniques de résolution par ordre croissant de difficulté (débutant, intermédiaire, expert) d'un SUDOKU sont les suivantes.

Techniques de résolution du niveau débutant

Sur une ligne : lorsqu'une ligne ne comporte plus qu'une seule case vide, celle-ci doit forcément contenir le seul chiffre non présent dans la ligne.

Sur une colonne : lorsqu'une colonne ne comporte plus qu'une seule case vide, celle-ci doit forcément contenir le seul chiffre non présent dans la colonne.

Dans un carré : lorsqu'un carré ne comporte plus qu'une seule case vide, celle-ci doit forcément contenir le seul chiffre non présent dans le carré.

Techniques de résolution du niveau intermédiaire

Sur un ensemble de trois : pour chaque ensemble de trois carrés alignés horizontalement ou verticalement, chaque chiffre ne doit apparaître qu'une seule fois par carré et par ligne, ou par carré et par colonne; pour chaque chiffre, cette technique doit être appliquée pour chaque ensemble horizontal de trois carrés puis pour chaque ensemble vertical de trois carrés.

Sur un ensemble de trois carrés horizontaux : dans un ensemble de trois carrés alignés horizontalement, lorsque la partie d'une ligne à l'intérieur d'un carré est remplie de chiffres différents du chiffre considéré, un des deux autres carrés horizontaux contient forcément le chiffre considéré.

Sur un ensemble de trois carrés verticaux : dans un ensemble de trois carrés alignés verticalement, lorsque la portion d'une colonne à l'intérieur d'un carré est remplie de chiffres différents du chiffre considéré, un des deux autres carrés verticaux contient forcément le chiffre considéré.

Techniques de résolution du niveau expert

L'intersection : chaque case est à l'intersection d'une ligne et d'une colonne, par conséquent, chaque case vide ne peut contenir qu'un chiffre non présent dans sa ligne et dans sa colonne; cette technique doit être appliquée à chaque case vide.

La paire exclusive : lorsque deux cases vides d'une même ligne, d'une même colonne ou d'un même carré ne peuvent contenir que deux mêmes chiffres, alors les autres cases vides de cette ligne, de cette colonne ou de ce carré ne peuvent pas contenir ces deux chiffres.

Je sais qu'il y a quelques années vous aviez deja aidé plusieurs élèves qui suivaient ce cours, mais sur un autre TP que celui-ci.

Bon pour en venir au vif du sujet, on me demande ça

"Pour pouvoir programmer le projet de Jeanne en Java, vous devez :

1-décrire et documenter les techniques de résolution de niveau moyen. (Qu'est ce qu'ils veulent dire par décrire et documenter, selon vous?)

2-élaborer les 3 algorithmes nécessaires à la programmation de la résolution du Sudoku niveau moyen."

Pour l'instant je n'ai pas encore les solutions aux questions puisque je suis en train d'y répondre, par contre je peux déjà poster le travail corrigé sur l'algorithme créé pour le niveau expert.

Comme ça vous avez un exemple de ce que l'on me demande.

PS: je poste la suite pour le niveau intermédiaire demain



Les techniques de résolution de niveau expert


L’intersection :

Description : Chaque case est à l'intersection d'une ligne et d'une colonne, par conséquent, chaque case vide ne peut contenir qu'un chiffre non présent dans sa ligne et dans sa colonne; cette technique doit être appliquée à chaque case vide.


Algorithme :

1 – Pour chaque case vide du tableau (81).
2 – Le chiffre doit être différent de ceux présent dans la colonne et la ligne à l’intersection de cette case vide.


compteur3 = 0         // Permet d’extraire le chiffre du tableau Tempo[9]
case[9][9] // Grille de sudoku 9x9
Test = 0 // Nombre de cases vides
Tempo[9] // Valeurs possibles par case

// Recherche les valeurs existantes de la ligne et de la colonne

Pour ligne de 1 jusqu’à 9
Pour colonne de 1 jusqu’à 9
Si case[ligne, colonne] est vide alors
Pour compteur1 de 1 à 9
// Copie les valeurs existantes de la ligne à l’intersection de la case
Si case[ligne, compteur1] n’est pas vide alors
// La valeur 1 indique que la valeur est présente. Le chiffre sera
// récupéré à l’aide de l’indice du tableau
Tempo[ case[ligne, compteur1] ] = 1
Fin Si
// Copie les valeurs existantes de la colonne à l’intersection de la case
Si case[compteur1, colonne] n’est pas vide alors
// La valeur 1 indique que la valeur est présente. Le chiffre sera
// récupéré à l’aide de l’indice du tableau
Tempo[ case[compteur1, colonne] ] = 1
Fin Si
Fin Pour
// Vérifie que le tableau contient qu’un seul chiffre
Pour compteur2 de 1 à 9
Si Tempo[compteur2] est vide alors
Test = Test + 1
Fin Si
Fin Pour
// Extrait le chiffre unique du tableau
Si Test = 1 alors
Faire
compteur3 = compteur3 +1
Si Tempo[compteur3] est vide alors
// Écrit le chiffre dans la grille sudoku
Ecrire case[ligne, colonne] = compteur3
Fin Si
Tant que Tempo[compteur3] = 1
Fin Si
Fin Si
Fin Pour
Fin Pour


La paire exclusive :

Description : Lorsque deux cases vides d'une même ligne, d'une même colonne ou d'un même carré ne peuvent contenir que deux mêmes chiffres, alors les autres cases vides de cette ligne, de cette colonne ou de ce carré ne peuvent pas contenir ces deux chiffres.

Algorithme :

1 – Choisir une ligne, une colonne ou un carré.
2 – Pour chaque case de la forme sélectionnée, si elles existent, trouver les paires exclusives.
2.1 – Rechercher les valeurs absentes, qui correspondent aux valeurs possibles, sur la ligne, sur la colonne et sur carré à l’intersection de cette case.
2.2 – Dans cette forme, sélectionner deux case ayant deux valeurs possibles seulement.
2.3 – Si les valeurs possibles sont identiques
Alors il s’agit d’une paire exclusive
3 – Enlever ces deux valeurs possibles des autres cases ayant des valeurs possibles, à l’exception des cases contenant ces paires exclusives.



compteur1 = 0         // Place les chiffres dans Tempo[9][9]. Pas influencé par la forme.
compteur11 = 1         // Permet de remplir resultat[9]
case[9][9] // Grille de sudoku 9x9
Test1[9] // Nombre de valeurs possibles par case
Test2 = 0 // Si Test2 = 9, il s’agit d’une paire exclusive
Tempo[9][9] // Valeurs possibles par case
resultat[9] // Valeurs à exclure pour la case sélectionnée
Choix // Choix à faire : Ligne, Colonne ou Carré
PositionLigne         // Numéro de la ligne de la cellule sélectionnée de 1 à 9
PositionColonne         // Numéro de la ligne de la cellule sélectionnée de 1 à 9
Forme     // Ligne, colonne ou carré

// Information entrée par le joueur

Entrée PositionLigne
Entrée PositionColonne
Entrée Forme

// Détermine les paramètres en fonction du choix de la forme

Choisir Cas Choix
Cas Ligne
DebutLigne = PositionLigne
DebutColonne = 1
FinLigne = PositionLigne
FinColonne = 9
Cas Colonne
DebutLigne = 1
DebutColonne = PositionColonne
FinLigne = 9
FinColonne = PositionColonne
Cas Carré
DebutLigne = (PositionLigne -1 \ 3) *3 +1
DebutColonne = (PositionColonne -1 \ 3) * 3 +1
FinLigne = DebutLigne +2
FinColonne = DebutColonne + 2
Fin Choisir

// Recherche les valeurs existantes de la ligne, de la colonne et du carré à l’intersection

Pour ligne de DebutLigne jusqu’à FinLigne
Pour colonne de DebutColonne jusqu’à FinColonne
compteur1 = compteur1 +1
Si case[ligne, colonne] est vide alors
Pour compteur2 de 1 à 9
// Copie les valeurs existantes de la ligne à l’intersection de la case
Si case[ligne, compteur2] n’est pas vide alors
// La valeur 1 indique que la valeur est présente. Le chiffre sera récupéré
// à l’aide de l’indice du tableau
Tempo[ compteur1, case [ligne, compteur2] ] = 1
Fin Si
// Copie les valeurs existantes de la colonne à l’intersection de la case
Si case [compteur2, colonne] n’est pas vide alors
// La valeur 1 indique que la valeur est présente. Le chiffre sera récupéré
// à l’aide de l’indice du tableau
Tempo[ compteur1, case [compteur2, colonne] ] = 1
Fin Si
Fin Pour
// Copie les valeurs existantes du carré à l’intersection de la case
Pour compteur3 de 0 à 2
Pour compteur4 de 0 à 2
Si case[DebutLigne + compteur3, DebutColonne + compteur4]
n’est pas vide alors
// La valeur 1 indique que la valeur est présente. Le chiffre sera
// récupéré à l’aide de l’indice du tableau
Tempo[ compteur1, case [DebutLigne + compteur3,
DebutColonne + compteur4] ] = 1
Fin SI
Fin Pour
Fin Pour
Fin Si
Fin Pour
Fin Pour

// Compte le nombre de valeurs existantes par cellules

Pour compteur5 de 1 à 9
Pour compteur6 de 1 à 9
Si Tempo[compteur5, compteur6] =1 alors
Test1[compteur5] = Test1[compteur5] + 1
Fin Si
Fin Pour
Fin Pour

Pour compteur7 de 1 à 9
Pour compteur8 de (compteur7 + 1) à 9
// Vérifie que la case contienne uniquement deux valeurs possibles
Si Test1[compteur7] = 7 et Test1[compteur8] = 7 alors
// Recherche une paire exclusive
Pour compteur9 de 1 à 9
// Vérifie que les valeurs sont identiques
Si Tempo[compteur7, compteur9] = Tempo[compteur8, compteur9] alors
Test2 = Test2 +1
Fin Si
Fin Pour
// Copie les chiffres de la paire exclusive dans le tableau résultat
Si Test2 = 9 alors
Pour compteur10 de 1 à 9
Si Tempo[compteur7, compteur10] est vide alors
resultat[compteur11] = compteur10
compteur11 = compteur11 + 1
Fin SI
Fin Pour
Fin SI
Fin SI
Fin Pour
Fin Pour

// Retourne les valeurs à exclure pour la case sélectionnée
retourner resultat