Aller au contenu
gege2007

Algorithme Et Sudoku

Messages recommandés

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:

 

post-54738-0-39569600-1421878094_thumb.p

 

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.

post-54738-0-39569600-1421878094_thumb.p

post-54738-0-39569600-1421878094_thumb.p

post-54738-0-39569600-1421878094_thumb.p

post-54738-0-39569600-1421878094_thumb.p

post-54738-0-39569600-1421878094_thumb.p

post-54738-0-39569600-1421878094_thumb.p

post-54738-0-39569600-1421878094_thumb.p

post-54738-0-39569600-1421878094_thumb.p

post-54738-0-39569600-1421878094_thumb.p

post-54738-0-39569600-1421878094_thumb.p

post-54738-0-39569600-1421878094_thumb.p

Partager ce message


Lien à poster
Partager sur d’autres sites

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.

Partager ce message


Lien à poster
Partager sur d’autres sites

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. 

Partager ce message


Lien à poster
Partager sur d’autres sites

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.

Partager ce message


Lien à poster
Partager sur d’autres sites

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

clip_image002_1.gif

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.

Partager ce message


Lien à poster
Partager sur d’autres sites

Créer un compte ou se connecter pour commenter

Vous devez être membre afin de pouvoir déposer un commentaire

Créer un compte

Créez un compte sur notre communauté. C’est facile !

Créer un nouveau compte

Se connecter

Vous avez déjà un compte ? Connectez-vous ici.

Connectez-vous maintenant

×