En passant

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)

dessiner une grille sudoku

Ecrire un programme de jeu Sudoku : dessiner la grille

par Ettougourti Mohamed Ali

Le jeu sudoku connait un engouement sans précédent.                     Plusieurs programmes informatiques ont été écrits pour le jeu.          Les plus intéressants sont ceux qui fournissent une aide au joueur pour trouver la solution de la grille proposée.                                           C’est ce qu’on appelle un « solver ».

D’autres programmes génèrent des grilles de jeu. Il faut remarquer à cet égard que toutes les grilles ne sont pas solubles  certaines n’ont pas de solutions.

Dans notre exercice de programmation en c sharp nous avons essayé de mettre au point un programme en c# qui permet au joueur de jouer sur écran, de remplir les cases vides par des chiffres candidats potentiels d’entrer une grille copiée sur un journal ou sur un livre de jeu..et en définitive de résoudre la grille au cas où elle accepterait une solution.

Le premier problème à résoudre fut  celui de dessiner la grille sudoku de 9 cases sur 9 ou de toutes autres dimensions.
Un problème de type graphique.

La fonction responsable de dessiner la grille est drawgrill.
Nous profitons de l’ Evènement paint de la forme windows pour generer la grille.

voici la forme de l’événement paint repris à notre compte.

private void Form1_Paint(object sender, PaintEventArgs e)

{

draw_grill(sender, e);

}

 

Comme vous le voyez la fonction draw_grill reprend les deux paramètres  l’object  sender et le PaintEventArgs e pour son propre compte.

Elle  définit deux crayons P1 et P2 ,  qu’elle utilise en deux couleurs le bleu et le rouge, la fonction graphics dessine pour nous les lignes et les rectangles.

Les variables : cote, step, x, et y sont définies en tant que variables publiques.

private void draw_grill(object sender, PaintEventArgs e)

{

Pen p = new Pen(Color.Red);

Pen p2 = new Pen(Color.Blue);

Point a = new Point(x, y);

Point b = new Point(x+cote, y);

for (int i = x; i < x+cote+step; i+=step)

{

a.Y = i;

b.Y = i;

e.Graphics.DrawLine(p2, a, b);

}

a = new Point(x, y);

b = new Point(x, y + cote);

for (int i = x; i < x + cote+step; i +=step)

{

a.X = i;

a.Y = y;

b.X = i;

b.Y = y+cote;

e.Graphics.DrawLine(p2, a, b);

}

int r = step * 3;

int r2 = cote / 3;

p.Width = 2;

e.Graphics.DrawRectangle(p, new Rectangle(this.x, this.y, cote, cote));

for (int i = 0; i < r * 3; i += r)

{

e.Graphics.DrawRectangle(p, new Rectangle(this.x, this.y+i, r2, r2));

e.Graphics.DrawRectangle(p, new Rectangle(this.x + r, this.y+i, cote / 3, cote / 3));

e.Graphics.DrawRectangle(p, new Rectangle(this.x + r * 2, this.y+i, cote / 3, cote / 3));

}

}

Une fois exécutée la fonction dessine chaque fois que la forme est affichée une grille de 9 cases sur 9 , la variable cote = 540, la variable step = 60, soit 60*9(cases)=540. Les deux points de départ X=40,    Y= 40.

pour télécharge le programme de jeu sudoku

sudoku3




(174)