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.

 




(81)