Algorithme Et Sudoku

[gege2007]

Bonsoir à tous, je viens de commencer un cours par correspondance sur Java à la fac et je dois avouer que je galère un peu, les cours manquent de précision sur certains détails et les tuteurs mettent beaucoup de temps à répondre.

 

on me donne ça:

 

 

Et on me demande de :

 

-Concevoir un algorithme qui permet de saisir et valider des informations 

-Concevoir l’algorithme de l’intersection 

-Concevoir l’algorithme de la paire exclusive 

 

Concernant les différents niveaux  de technique de résolution on a:

 

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.

 

Pour vous donner un exemple, on m'a demander de décrire et d'élaborer un algorithme pour chacun des trois niveau intermédiaire.

Le corrigé:

 

Les techniques de résolution de niveau moyen

 

Sur un ensemble de trois : 

 

Description : 

 

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.

 

Algorithme :

 

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.

6 – Si une case est vide,

Alors, les valeurs possibles de cette case correspondent aux chiffres non présents sur la colonne et sur le carré à l’intersection de cette case.

 

 

Sur un ensemble de trois carrés horizontaux : 

 

Description : 

 

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

 

Algorithme :

 

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.

 

Sur un ensemble de trois carrés verticaux : 

 

Description : 

 

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 :

 

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.

 

Auriez-vous des conseils avant que je me lance ?

Je posterai ce que j'aurais commencé à faire demain.

 

Bonne soirée à tout le monde.

[gege2007]

Bon voilà pour les algorithmes 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.

 

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.

 

 

Dites moi si cela selon vous répond à ce que l'on me demande.

[gege2007]

et pour l'autre algorithme

Algorithme 

1-Nom joueur 

      1.1-Afficher "Votre nom:" 

      1.2-Permettre l'écriture d'une chaîne de caractères entre 3 et 25 nommée name1. 

      1.3-Si chaîne de caractère ne correspond pas retour et afficher à 1.1 

      1.4-Sinon extraire name1 

      1.6-Enregistrer name1 

           2-Prénom joueur 

                     2.1-Afficher "Votre prénom:" 

                     2.2-Permettre l'écriture d'une chaîne de caractères entre 3 et 25 nommée name2. 

                     2.3-Si chaîne de caractère ne correspond pas retour et afficher à 2.1 

                     2.4-Sinon extraire name2 

                     2.5-enregistrer name2 

                     

3- Choix du niveau de jeu 

      3.1-Afficher "Veuillez choisir votre niveau de jeu parmi les suivants" 

      3.2-Afficher "Tapez 1 pour Sudoku débutant, tapez 2 pour Sudoku intermédiaire, tapez 3 pour Sudoku avancé" 

      3.3-Permettre seulement l'écriture d'un chiffre, soit 1, soit 2, soit 3 

      3.4-Si chiffre ne correspond pas retour à 3.2 

      3.5-Sinon extraire le chiffre entré par le joueur. 

      3.6-Enregistrer ce chiffre 

      3.7-Suivant le chiffre enregistré 1,2 ou 3 afficher la grille correspondant a ce chiffre. 

[gege2007]

Personne n'a d'idées?

[Étienne9]

Bonjour,

 

Encore d'actualité ?

 

Cordialement.

[codeman]

Bonjour

Moi aussi j'ai commencé le même cours, et c'est vrai que c'est plein d’ambiguïté

Ça s'est bien passé? 

[JAVA23]

Bonjour, 

 

Je suis inscrite à ce cours et je ne comprends rien... Si vous pourriez m'aider ça serait vraiment gentil !!

[Étienne9]

Hello,

Encore d'actualités depuis le temps ?
Car je pense que j'ai compris pour la résolution d'intersection.
L'autre résolution je n'ai pas encore regardé.
Je t'envoie mon Skype personnel si tu veux, et si tu as besoin d'aide je suis là.

Cordialement.

[Javar25]

Bonjour, 

Je suis entrain de faire le même problème et je suis confus au niveau de la descprition. Est-ce que quelqu'un a compris le problème. Faut-il écrire le programme au complet ou seulement les algorithmes? Merci pour votre aide, j'apprécie. 

Au plaisir, 

PS Voici la descprition du problème. 

1. Problématique

Vous êtes mandaté par la directrice de l’école Saint-Pruneau à concevoir des algorithmes dont celui de la technique de résolution de Sudoku niveau expert.

1. Concevoir un algorithme qui permet de saisir et valider des informations

                L’algorithme permet de saisir au clavier les informations suivantes et de les valider suivant les règles définies:

1. Informations du joueur.
   1. Nom: Une chaine de caractère dont la longueur est comprise entre 3 et 25 caractères.
   2. Prénom: Une chaine de caractère dont la longueur est comprise entre 3 et 25 caractères.
   3. Mon choix: 1 pour Sudoku débutant, 2 pour Sudoku intermédiaire et 3 pour Sudoku avancé. Dépendamment du nombre entré par le joueur, vous devez afficher  soit  Sudoku débutant, Sudoku intermédiaire ou Sudoku avancé.
2. Concevoir les deux algorithmes des techniques de résolution de niveau expert

Voici un exemple d'une grille partiellement remplie avec sa solution

Le jeu consiste à fournir une grille d'un sudoku valide partiellement remplie et le but est de compléter cette grille en un sudoku valide. Généralement, ces grilles partielles sont constituées de telle manière que la solution minimale soit unique. On appelle grille de sudoku minimale, une telle grille se complétant en un unique sudoku qui est telle qu'on ne puisse lui enlever un seul nombre sans perdre l'unicité de la solution.
Les techniques de résolution de niveau expert
Dans cette technique, on retrouve l’intersection et la paire exclusive.
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.
Concevoir les algorithmes de l’intersection et de la paire exclusive.