Micro-exercice de programmation 3 : analyse fonctionnelle et algorithme

Micro-exercice de programmation 3 : analyse fonctionnelle et algorithme

Projet de Jeanne

Les techniques de résolution de niveau débutant

Sur une ligne :

Description : Lorsqu'une ligne ne comporte plus qu'une seule case vide, cette case doit forcément contenir le seul chiffre non présent dans la ligne.

Algorithme :

1 - Choisir une ligne.

2 - Vérifier si les cases de la ligne contiennent une seule case vide.

3 - Si une seule case est vide,

Alors le chiffre manquant est celui non présent de 1 à 9.

Sur une colonne :

Description : Lorsqu'une colonne ne comporte plus qu'une seule case vide, cette case doit forcément contenir le seul chiffre non présent dans la colonne.

Algorithme :

1 - Choisir une colonne.

2 - Vérifier si les cases de la colonne contiennent une seule case vide.

3 - Si une seule case est vide,

Alors le chiffre manquant est celui non présent de 1 à 9.

Dans un carré :

Description : Lorsqu'un carré ne comporte plus qu'une seule case vide, cette case doit forcément contenir le seul chiffre non présent dans le carré.

Algorithme :

1 - Choisir un carré.

2 - Vérifier si les cases d’un carré contiennent une seule case vide.

3 - Si une seule case est vide,

Alors le chiffre manquant est celui non présent de 1 à 9.

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

...