Archives par mot-clé : sudoku

Sudoku: determiner les chiffres candidats en c#

 

sudoku : determiner les chiffres candidats en C# -2

par Ettougourti Mohamed Ali

Deux fonctions ont été nécessaires pour remplir une case sudoku de candidats possibles.

Nous listons ci-dessous la fonction controlvalid2 et la fonction getregion. (voir article précédent du même auteur)

Vous remarquerez que dans l’écriture des trois fonctions (setcandidates, controlvalid2 et getregion) la programmation est restée très basique puisque nous avons abusé de « for » et « next » et autres boucles while alors que comme nous allons le découvrir le c sharp offre bien d’autres possibilités de programmation beaucoup plus puissantes et performantes.

private int Controlvalid2(int i, char c)

{

int j = i;

while (j % 9 != 0) j–;

int k = j + 9;

for (; j < k; j++)

if (cells[j].c == c) {   return -1; }

j = i;

while (j >= 0) j -= 9;

j += 9;

k = j + 73;

for (; j < k; j += 9)

{

if (cells[j].c == c) {   return -1; }

}

int r = getregion(i); // chercher le centre du  petit carré

for (j = 0; j < 9; j++)

{

if (cells[r – 10].c == c ||

cells[r – 9].c == c ||

cells[r – 8].c == c ||

cells[r – 1].c == c ||

cells[r – 0].c == c ||

cells[r + 1].c == c ||

 

cells[r + 8].c == c ||

cells[r + 9].c == c ||

cells[r + 10].c == c)

{

return -1; }

}

return 1;

}

Rappelons que controlvalid2 collecte les chiffres dans chaque ligne et dans chaque colonne ou se trouve la case à remplir de candidats potentiels, elle fait aussi appel à getregion pour collecter les chiffres du petit carré, une fois tous les chiffres rassemblés elle peut accepter ou rejeter le chiffre proposé passé en paramètre c.

En montant à un niveau plus difficile on peut reprendre la fonction controlvalid pour en faire une fonction plus performante et plus concise.

Il s’agit de faire appel aux fonctions lambda introduites dans c# qui facilitent énormément le maniement des tableaux.

Pour chercher toutes les cases comportant un chiffre introduit par le joueur ou posé comme contrainte se trouvant sur la même ligne et sur la même colonne que notre case à remplir on utilise une seule instruction.

L’array  ou le tableau cells de 81 élements (9*9) est utilisé comme une liste qu’on peut interroger à l’aide de l’instruction « where ». le resultat de la recherche est stocké dans une liste de caractères ch grâce à l’instruction select,  pour effacer les doublons on utilise l’instruction distinct à la fin de l’expression lambda.

List<char> ch = cells.Where((b, index) => (index / 9 == l || index % 9 == col)   &&  cells[index].c != (char)’X’).Select(b => b.c).Distinct().ToList();

À la structure cell nous ajoutons deux fonctions qui nous donnent la colonne et la ligne de la case i. une autre fonction nous retourne le centre du petit carré auquel appartient la case à remplir de chiffres candidats.

La nouvelle structure a désormais la forme suivante :

public struct cell

{

public Point p;

public int width;

public int height;

public int val;

 

public char c;

public bool iscontrainte;

public char[]candidates;

public int nbcandidates;

public int getline (int i)

{

return i / 9;

}

public int getcol(int i)

{

return i % 9;

}

 

public int getcenterregion (int i)

{

int col= i % 9;

int l= i / 9;

switch (col)

{

case 1:

case 4:

case 7:

if (l == 1 || l == 4 || l == 7) return i;

break;

 

}

if (col >= 6) col = 7;

else if (col >= 3) col = 4;

else col = 1;

if (l >= 6) l = 7;

else if (l >= 3) l = 4;

else l = 1;

return (l * 9) + col;

 

}

}

La nouvelle fonction controlvalid4 réécrite est listée ci-dessous

private char[] controlvalid4 (int i)

{

if (cells[i].iscontrainte == true || cells[i].c != ‘X’)

return null;

//definir les cases de la région par rapport au centre 

int[] v = new int [9] { -10, -9, -8, -1, 0,1,8,9,10 };

//definir les chiffres legaux

char[] cc = new char[9] { ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ };

     //trouver la ligne

int l = cells[i].getline(i);

//trouver la colonne

int col = cells[i].getcol(i);

  //trouver les chiffres enregistrés dans toutes les cases de la //même ligne et de la même colonne

            // qui ne sont pas libres ne comportant pas un ‘X’ en guise de //chiffre tout en évitant les doublures

            //le tout enregistré dans une nouvelle liste   ch

       List<char> ch = cells.Where((b, index) => (index / 9 == l || index % 9 == col)

&& cells[index].c != (char)’X’).Select(b => b.c).Distinct().ToList();

//retourner null si aucune occurrence n’a été trouvée

if (!ch.Any()) return null;

   //aprés avoir calculé le centre du petit carré j

            // nous ajoutons toutes les valeurs de la région

            // à la liste ch 

int j = cells[i].getcenterregion(i);

for (int k = 0; k < 9; k++)

{

if(cells[j+ v[k]].c != (char)’X’)

ch.Add(cells[j + v[k]].c);

}

// nous disposons désormais d’une liste (ch) de tous

            //les chiffres illégaux pour notre case

            // et d’une autre (cc) de tous les chiffres légaux

ch = ch.Distinct().ToList(); // éviter de reproduire les chiffres //plus qu’une fois

//soustraire les chiffres illégaux de la liste des chiffres légaux

cc = cc.Except(ch.ToList()).ToArray();

return cc;

}

Vous remarquez que la nouvelle fonction prend désormais un seul paramètre i qui est l’index de la case.

 




(100)

Sudoku: determiner les chiffres candidats

 

Ecrire programme Sudoku : déterminer les candidats

Par  Ettougourti Mohamed Ali

Chaque case de la grille sudoku est traitée comme une structure.  Les informations relatives à chaque cellule sont sauvegardées sous la forme suivante :

public struct cell

{

public Point p;

public int width;

public int height;

public char c;

public bool iscontrainte;

public char[]candidates;

public int nbcandidates;

}

Un élément de la structure nous intéresse particulièrement il s’agit de ‘iscontrainte ‘. S’il est mis à false ou faux c’est que la case est libre et n’est pas fixée par la grille dès le départ comme étant une contrainte du jeu.

C’est une case qu’on peut remplir par des chiffres candidats potentiels.

Mais une case peut aussi comporter un chiffre unique que le joueur a saisi. Elle n’est pas donc libre et nous devons éviter de la remplir des chiffres candidats au risque d’écraser le chiffre introduit par le joueur. C’est ainsi que nous prenons le soin dès le départ de remplir toutes les cases libres qui ne comportent aucun chiffre saisi par le joueur et qui ne sont pas des contraintes du jeu par la lettre « X » pour inconnu.

Pour chaque case nous devons vérifier s’il s’agirait d’une contrainte ou pas et si une éventuelle saisie du joueur a rempli la case par un chiffre déterminé.

Ces deux précautions prises nous cherchons les candidats possibles pour chaque case libre en faisant appel à une fonction baptisée controlvalid2.

Controlvalid2 doit chercher dans chaque ligne ainsi que dans chaque colonne et dans chaque région ou petit carré ou la case se trouve  si le chiffre proposé comme candidat est déjà utilisé auquel cas elle renvoie un -1 dans le cas contraire elle renvoie un chiffre positif 1.

Une fois l’ok donné par la routine controlvalid2 la fonction SetCandidates affiche le chiffre en tant que chiffre candidat potentiel.

Voici la fonction SetCandidates qui remplit les cellules de chiffres candidats potentiels.

Pour la fonction du contrôle de la validité elle sera expliquée dans un prochain article . la fonction getregion nous permet de déterminer la région (ou petit carré à l’intérieur de la grille) ou se trouve la case à remplir de chiffres candidats. Elle fera elle aussi l’objet du prochain article.

private void SetCandidates()

{

for (int i = 0; i < 81; i++) // 81 case 9*9

{

if (cells[i].iscontrainte == false  && cells[i].c==’X’)

{

effacer(cells[i].p);

cells[i].candidates = new char[9]; // creer le tableau

int j = 0;

cells[i].nbcandidates = 0;

for (char k = ‘1’; k < (char)58; k++) // char(58) = ‘9’ +1

{

                        if (Controlvalid2(i, k) == 1)

{

cells[i].candidates[j++] = k;

cells[i].nbcandidates = j;

}

}

}

}

afficheCandidates();       // appel à une fonction affichant les                                                                               //chiffres candidats pour la case

}




(88)