Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Sudoku en java

Posté par
Riley
20-01-15 à 19:07

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



Posté par
Revelli
re : Sudoku en java 20-01-15 à 19:59

Bonsoir,

Il n'est nulle part question de niveau moyen: Est-ce plutôt intermédiaire? Où est-ce un quatrième niveau à inventer?

Posté par
Riley
re : Sudoku en java 20-01-15 à 20:05

heu oui, niveau intermédiaire excuse-moi

Posté par
Riley
re : Sudoku en java 21-01-15 à 11:44

je dois avouer que je bloque complètement je ne vois pas par où commencer.

Algorithme :

1 - Pour chaque ensemble de trois carrés alignés horizontalement ou verticalement (3).
2 - Le chiffre doit être différent de ceux présent dans le carré et la colonne ou le carré et la ligne.

// cette initialisation je peux la garder, par contre je suppose qu'il faut que j'ajoute des éléments concernant les ensemble de trois carrés.

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

Posté par
Riley
re : Sudoku en java 21-01-15 à 12:19

en fait je me disait puisque la première technique de niveau intermédiaire est

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.

Donc ce qu'il faut que je fasse c'est de traiter séparément chaque ensemble de trois carrés horizontalement et verticalement.

J'ai du mal à comprendre la fonction compteur1 elle s'occupe de compter de la ligne/colonne 1 à 9 ou de compter dans chaque case de 1 à 9?

Posté par
Riley
re : Sudoku en java 21-01-15 à 12:25

Autre petite question, désolé j'en ai beaucoup je sais

Cette partie de l'algorithme qu'est ce qu'elle fait?
// 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

Posté par
Riley
re : Sudoku en java 21-01-15 à 18:07

Bon finalement j'ai tout repris à zéro.

Algorithme  de résolution du sudoku niveau moyen :
1-Recherche des cases vides dans chaque ligne et colonne d'un ensemble de trois carrés (3*3 cases) alignés horizontalement ou verticalement.
2-Si un carré possède une ligne ou une colonne remplie de chiffres différents recherche d'une case vide dans la ligne ou colonne  des deux autres carrés.
3-Si case vide trouvée recherche du chiffre qui n'est pas sur la même ligne ou colonne et qui est présent dans d'autres carrés.
4- Si chiffre trouvé sortie de l'algorithme et l'afficher, sinon répétition de la boucle.

Posté par
speudo37
re : Sudoku en java 30-03-16 à 17:40

Sudoku de programmation java
J'ai le même problème de compréhension que Riley. Alors je ne sais pas si c'est encore d'actualité. Mais j'aimerais beaucoup avoir l'explication à ces deux questions.
Je vous fait parvenir ce que j'ai fait.

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?)

Description :
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.
Description :
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é.
Description :
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é.

Algorithme  de résolution du sudoku niveau moyen :

1-Recherche des cases vides dans chaque ligne et colonne d'un ensemble de trois carrés (3 X 3 cases) alignés horizontalement ou verticalement.
2-Si un carré possède une ligne ou une colonne remplie de chiffres différents recherche d'une case vide dans la ligne ou colonne  des deux autres carrés.
3-Si case vide trouvée recherche du chiffre qui n'est pas sur la même ligne ou colonne et qui est présent dans d'autres carrés.
4- Si chiffre trouvé sortie de l'algorithme et l'afficher, sinon répétition de la boucle.


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

Algorithme Sur un ensemble de trois  :
1 - Choisir un ensemble de trois carrés horizontaux.
2 - Vérifier si les cases d'une ligne contiennent une case vide.
3 - Si une case est vide,
Alors, les valeurs possibles de cette case correspondent aux chiffres non présents sur la ligne et sur le carré à l'intersection de cette case.
4 - Choisir un ensemble de trois carrés verticaux.
5 - Vérifier si les cases d'une ligne contiennent une case vide.

Algorithme Sur un ensemble de trois carrés horizontaux :
1 - Choisir trois carrés horizontaux.
2 - Si le chiffre A
Lorsque la partie d'une ligne à l'intérieur d'un carré est remplie de chiffres différents de A.
Alors A doit  être mis dans un des autres carrés.

Algorithme Sur un ensemble de trois carrés verticaux  :
1 - Choisir trois carrés verticaux.
2 - Si le chiffre A
Lorsque la partie d'une ligne à l'intérieur d'un carré est remplie de chiffres différents de A.
Alors A doit  être mis dans un des autres carrés.

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !