C#: Comment faire un tableau de structs ?

C#: Comment faire un tableau de structs ? - C#/.NET managed - Programmation

Marsh Posté le 11-12-2008 à 09:02:05    


Bonjour,
 
Question con a laquelle je ne trouve pas de reponse [:wam]
J'ai un struct tout con qui contient 2 integer, par ex.
 
J'aimerais creer un tableau contenant des ces structs, mais je ne parviens pas a trouver la syntaxe correcte.  

Code :
  1. public struct tableEntry
  2.     {
  3.         public int value;
  4.         public int[] candidates;
  5.     }


 

Code :
  1. tableEntry[] myTable = new tableEntry[];


 
J'oublie quel détail ?
 


---------------
Pier noir la mèr - La chanson par HFR Band - Topic TrueCrypt
Reply

Marsh Posté le 11-12-2008 à 09:02:05   

Reply

Marsh Posté le 11-12-2008 à 09:51:26    

tu es sur que tu ne devrai pas plutôt faire un tableau d'objet ? , avec une classe tableEntry ?


---------------

Reply

Marsh Posté le 11-12-2008 à 09:55:52    

Classe, struct, pareil :o  
par contre sur le net jai trouvé que les tableaux doivent etre typés et que du coup, c'est pas top.
 
Quelle est la meilleure facon (ou la plus simple, disons) d'implementer une matrice a 2 dimensions en C# ? Je vais passer de mon int[,] a un truc qui peut contenir des structs. Un Dictionary, peut etre ? :sweat:


---------------
Pier noir la mèr - La chanson par HFR Band - Topic TrueCrypt
Reply

Marsh Posté le 11-12-2008 à 10:07:08    

Reply

Marsh Posté le 11-12-2008 à 10:16:05    

Donc ca marche avec une classe mais pas un struct [:transparency]
 
Merci :jap:


---------------
Pier noir la mèr - La chanson par HFR Band - Topic TrueCrypt
Reply

Marsh Posté le 11-12-2008 à 13:18:16    

class ou struc ce n'est pas pareil.  
Leur allocation mémoire est totalement différente (pour l'un dans la HEAP, pour l'autre dans la STACK).  
Les struct ne doivent idéalement pas dépasser 16 bytes.

Message cité 1 fois

---------------
quand un homme raisonne mal c'est qu'il n'a pas les données pour raisonner mieux (diderot)
Reply

Marsh Posté le 15-12-2008 à 09:54:11    

c'est pas parceque c'est possible que c'est une bonne pratique


---------------

Reply

Marsh Posté le 15-12-2008 à 11:21:10    

:jap:
 
A la base c'etait pour un programme de resolution de Sudoku en brute force. Ca fonctionne bien, maintenant j'aimerais l'optimiser: pour le sudoku qui est donné en "near worst case" sur wiki, mon prog met 4:52 minutes avec une config moyenne de nos jours (:o).
 
http://upload.wikimedia.org/wikipedia/en/1/17/Sudoku_puzzle_hard_for_brute_force.jpg
 
J'utilise un tableau a 2 dimensions contenant des cell, ma classe:
 

Code :
  1. // Class cell
  2.         private class cell
  3.         {
  4.             public cell(int aRow, int aCol, int aValue)
  5.             {
  6.                 row = aRow;
  7.                 col = aCol;
  8.                 value = aValue;
  10.                 for (int i = 1; i <= 9; i++)
  11.                 {
  12.                     candidates.Add(i);
  13.                 }
  14.             }
  16.             public int value;
  17.             public int row;
  18.             public int col;
  19.             public List<int> candidates = new List<int>();
  20.         }


 
Voici la methode de brute force:
 

Code :
  1. // BruteForce
  2.         private bool bruteForce(cell acell)
  3.         {
  4.             // Call counter
  5.             counter++;
  7.             // Not finished
  8.             if (acell.row <= 8 && acell.col <= 8)
  9.             {
  10.                 // For all candidates
  11.                 for(int i = 0; i <= acell.candidates.Count - 1; i++)
  12.                 {
  13.                     // Candidate shortcurt
  14.                     int aValue = acell.candidates[i];
  16.                     // Check constraints
  17.                     if ((     checkRow(acell.row, aValue) == 0)
  18.                           && (checkColumn(acell.col, aValue) == 0)
  19.                           && (checkSquare(acell.row, acell.col, aValue) == 0))
  20.                     {
  21.                         myTable[acell.row, acell.col].value = aValue;
  22.                         if (bruteForce(nextFreeCell()))
  23.                             return true;
  24.                     }
  25.                 }
  27.                 // Clear the field, wrong value
  28.                 myTable[acell.row, acell.col].value = 0;
  29.             }
  30.             else
  31.             {
  32.                 // End reached
  33.                 return true;
  34.             }
  35.             return false;
  36.         }


 
Sachant que je ne peux pas ameliorer grand chose niveau logique pour la resolution du puzzle, peut-etre que je peux ameliorer qqch niveau programmation, n'etant pas un guru :o Y-a-t-il des astuces / idees pour reduire le temps de calcul en utilisant certaines methodes d'implementation ?
 
:jap:


Message édité par ParadoX le 15-12-2008 à 11:22:58

---------------
Pier noir la mèr - La chanson par HFR Band - Topic TrueCrypt
Reply

Marsh Posté le 17-12-2008 à 11:53:33    

Tu es sur que c'est du "near worst case"?
Parce que j'ai écrit pour voir entre hier et ce matin un petit programme en C# (surtout pour voir si je perd pas la main dans ce langage que je pratique peu), qui ne fait pas de la brute force, mais applique juste les regles logiques de base (et qui ne saura pas resoudre une grille ou il faut faire des essais, comme une grille qui a plus d'une solution).
Or il résoud ta grille quasiment instantanément en 17 passes dans mon algo.
 
step 17:  
 
| 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 |
| 02 | 04 | 06 | 01 | 07 | 03 | 09 | 08 | 05 |
| 03 | 05 | 01 | 09 | 02 | 08 | 07 | 04 | 06 |
| 01 | 02 | 08 | 05 | 03 | 07 | 06 | 09 | 04 |
| 06 | 03 | 04 | 08 | 09 | 02 | 01 | 05 | 07 |
| 07 | 09 | 05 | 04 | 06 | 01 | 08 | 03 | 02 |
| 05 | 01 | 09 | 02 | 08 | 06 | 04 | 07 | 03 |
| 04 | 07 | 02 | 03 | 01 | 09 | 05 | 06 | 08 |
| 08 | 06 | 03 | 07 | 04 | 05 | 02 | 01 | 09 |
 
A+,

Message cité 1 fois
Message édité par gilou le 17-12-2008 à 12:00:58

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 17-12-2008 à 12:27:38    


 
On peut aussi passer par une liste:
 

Code :
  1. List<tableEntry> myListe = new List<tableEntry>();
  2. myListe.Add(new tableEntry());
  3. myListe.Add(new tableEntry());
  4. myListe.Add(new tableEntry());
  5. tableEntry[] myTable = myListe.ToArray();


 
Après, l'idéal étant de n'utiliser que la liste si besoin, sans passer par le Array :D


---------------
VA APPRENDRE ET REVIENS QUAND TU SAIS, SINON ABSTIENT TOI C'EST UN GRAND CONSEIL QUE JE TE DONNE... TU ES INCOMPÉTENT ET C'EST UNE RÉALITÉ, TU N'AS RIEN A FAIRE ICI FAUT S'Y CONNAITRE ... -Jojo1998 - RIP - http://tinyurl.com/qc47ftk
Reply

Marsh Posté le 17-12-2008 à 12:27:38   

Reply

Marsh Posté le 17-12-2008 à 14:31:41    

gilou a écrit :

Tu es sur que c'est du "near worst case"?
Parce que j'ai écrit pour voir entre hier et ce matin un petit programme en C# (surtout pour voir si je perd pas la main dans ce langage que je pratique peu), qui ne fait pas de la brute force, mais applique juste les regles logiques de base (et qui ne saura pas resoudre une grille ou il faut faire des essais, comme une grille qui a plus d'une solution).
Or il résoud ta grille quasiment instantanément en 17 passes dans mon algo.
 
step 17:  
 
| 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 |
| 02 | 04 | 06 | 01 | 07 | 03 | 09 | 08 | 05 |
| 03 | 05 | 01 | 09 | 02 | 08 | 07 | 04 | 06 |
| 01 | 02 | 08 | 05 | 03 | 07 | 06 | 09 | 04 |
| 06 | 03 | 04 | 08 | 09 | 02 | 01 | 05 | 07 |
| 07 | 09 | 05 | 04 | 06 | 01 | 08 | 03 | 02 |
| 05 | 01 | 09 | 02 | 08 | 06 | 04 | 07 | 03 |
| 04 | 07 | 02 | 03 | 01 | 09 | 05 | 06 | 08 |
| 08 | 06 | 03 | 07 | 04 | 05 | 02 | 01 | 09 |
 
A+,


 
Je peux voir ton algo ?
Sinon c'est un worst case justement pour un algo de bruteforce, sinon le terme de worstcase n'a pas de sens :jap:


---------------
Pier noir la mèr - La chanson par HFR Band - Topic TrueCrypt
Reply

Marsh Posté le 17-12-2008 à 16:17:53    

Typiquement, mon algo ne marche que s'il existe une resolution directe.
Cette grille de départ (Télé Loisir Force 3 de cette semains :D ) le bloque au bout de 3 itérations (et résolution pour 11 cases)
 

| 01 |    |    |    |    |    |    | 05 |    |
|    |    |    | 01 | 05 |    | 04 |    |    |
|    |    |    |    |    | 04 | 06 |    |    |
| 06 |    |    |    |    | 09 |    | 07 |    |
| 04 | 02 | 09 |    |    |    |    |    |    |
|    | 03 |    |    | 04 |    |    | 09 |    |
| 02 | 05 |    | 09 | 06 |    |    | 04 | 08 |
|    |    |    | 03 |    |    |    |    | 05 |
| 07 |    | 08 |    |    | 05 |    | 03 | 09 |


 
A+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 17-12-2008 à 17:02:03    

L'algo marche ainsi:
Une classe pour definir ce qu'est une case:

Code :
  1. public class Square {
  2.     static int[] digits = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  3.     public int? digit { get; set; }
  4.     List<int> possible_digits;
  6.      public Square() {
  7.       digit = null;
  8.       possible_digits = new List<int>(digits);
  9.     }
  10. .................................


Une classe pour définir une grille

Code :
  1. public class BoardSquare : Square {
  2.     public Square square;
  3.     public int row { get; set; }
  4.     public int col { get; set; }
  6.     public BoardSquare (int i, int j)  {
  7.       row = i;
  8.       col = j;
  9.     }
  10. ..................................


Une classe pour définir une partie:

Code :
  1. public class Game {
  2.     BoardSquare[,] board = new BoardSquare[9,9];
  3.     public List<BoardSquare> todo = new List<BoardSquare> ();
  5.     public Game() {
  6.       for (int i = 0; i < 9; i++) {
  7.         for (int j = 0; j < 9; j++) {
  8.           board[i,j] = new BoardSquare(i,j);         
  9.         }
  10.       } 
  11.     }
  12. ..........................................


todo est la liste des cases dont les valeurs viennent d'être connues et qu'on va traiter.
 
On initialise la grille avec les valeurs d'une grille initiale, et on met chaque case de la grille initiale dans la liste todo.

Code :
  1. public Game(int[,] iniset) : this() {
  2.       BoardSquare carre;
  3.       for (int i = 0; i < iniset.GetLength(0); i++) {
  4.         carre =  board[iniset[i,0],iniset[i,1]];
  5.         carre.InitSquare(iniset[i,2]);
  6.         if (!todo.Contains(carre))
  7.           todo.Add(carre);
  8.       }
  9.     }


InitSquare(n) va mettre a n son champ digit et réduire a {n} sa liste possible_digits.
ou ta grille exemple est:

Code :
  1. int[,] initial_set = {
  2.           {1,5,3}, {1,7,8}, {1,8,5},
  3.           {2,2,1}, {2,4,2},
  4.           {3,3,5}, {3,5,7},
  5.           {4,2,4}, {4,6,1},
  6.           {5,1,9},
  7.           {6,0,5}, {6,7,7}, {6,8,3},
  8.           {7,2,2}, {7,4,1},
  9.           {8,4,4}, {8,8,9}
  10.         };


 
Ensuite pour chaque element de la liste todo on va virer sa valeur des possible_digits des cases dans la même ligne, colonne et carré interne:

Code :
  1. public void Reduce(BoardSquare carre) {
  2.       int val = (int) carre.digit;
  3.       int row = carre.row;
  4.       int col = carre.col;
  5.       for(int i = 0; i < 9; i++) {
  6.         board[row,i].RemoveDigit(val);
  7.         board[i,col].RemoveDigit(val);
  8.       }
  9.       for(int i = 0; i < 3; i++) {
  10.         for(int j = 0; j < 3; j++) {
  11.           board[((row/3)*3)+i,((col/3)*3)+j].RemoveDigit(val);
  12.         }
  13.       } 
  14.     }


RemoveDigit fait gaffe a pas le virer sur la case de todo en cours elle même.
 
C'est appellé dans cet fonction, qui fait la resolution de la grille:

Code :
  1. public void BasicReduce() {
  2.       foreach (BoardSquare carre in todo) {
  3.         Reduce(carre);
  4.       }
  5.       todo.Clear();
  6.       for(int n = 1; n <= 9; n++) {
  7.         FindUniqueInRow(n);
  8.         FindUniqueInCol(n);
  9.         FindUniqueInSqr(n);
  10.       }
  11.       for(int i = 0; i < 9; i++) {
  12.         for(int j = 0; j < 9; j++) {
  13.           if (board[i,j].Solved()) {
  14.             if (!todo.Contains(board[i,j])) {
  15.               todo.Add(board[i,j]);
  16.             }
  17.           }
  18.         }
  19.       }
  20.     }


Donc apres avoir traité la liste todo, on la vide, et on regarde si notre traitement n'a pas créé de nouvelles cases qu'on va pouvoir resoudre (et donc mettre dans la liste todo):
Pour chaque chiffre, on regarde si il n'est pas présent qu'une seule fois dans les possible_digits dans  une ligne, une colonne ou un carré interne, si oui, pour la seule case portant cette valeur, si elle n'a pas déja sa valeur dans digit (ie deja traitée), on met la valeur, et on reduit possible_digits a cette valeur. Si la case n'est pas déja dans la todo list, on la met.

Code :
  1. public void FindUniqueInCol(int num) {
  2.       int count;
  3.       for(int i = 0; i < 9; i++) {
  4.         count = 0;
  5.         for(int j = 0; j < 9; j++) {
  6.           if (board[j,i].HasDigit(num)) {
  7.             count++;
  8.           }
  9.         }
  10.         if (count == 1) {
  11.           for(int j = 0; j < 9; j++) {
  12.             if (board[j,i].HasUnsetDigit(num)) {
  14.               board[j,i].SetDigit(num);
  15.               if (!todo.Contains(board[j,i])) {
  16.                 todo.Add(board[j,i]);
  17.               }
  18.             }
  19.           }
  20.         }
  21.       }
  22.     }


FindUniqueInSqr est du même tonneau, mais plus coton a établir comme formule, il faut utiliser des modulo et la division entiere.
 
Enfin l'algo verifie qu'il n'y a pas des cases qui ont possible_digit a une seule valeur et digit pas positionné, sinon, on positionne digit et on ajoute la case dans la todo list.
 
On a une nouvelle liste todo, on réitere l'algo:

Code :
  1. int k = 1;
  2. while (game.todo.Count != 0 && k < 99) {
  3.     game.BasicReduce();
  4.     System.Console.WriteLine( "step {0}: ", k);
  5.     game.Print();
  6.     k++;
  7. }


j'ai mis une valeur  maximale a 99 tours, mais en fait, ca ne devrait pas dépasser 9*9=81 (ou 81+1) tours.
 
L'algo consiste pour une case connue, a réduire les possibilités dans sa ligne, colonne, carré interne, puis a regarder:
- si pour une valeur donnée, il n'y a pas qu'une seule possibilité par ligne, colonne ou carré interne
- si il n'y a pas des cases qui n'ont qu'une seule possibilité
 
Il y a peut être des améliorations a apporter a cet algo, mais il faut que j'aille lire du coté des techniques de résolution des grilles de Sudoku pour voir s'il y a d'autres techniques directes (ie ne faisant pas a un moment donné une hypothése "si la valeur en cette case est... alors, et voir si on arrive a une contradiction" ).
 
Il y a en particulier la technique de la hidden pair qu'il faudrait que je rajoute.
A+,


Message édité par gilou le 17-12-2008 à 17:22:08

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 17-12-2008 à 18:50:23    

:jap:
 
J'ai un truc similaire, avant de commencer le brute force je diminue le nombre de candidats pour chaque cellule. Par contre ta methode ne marche que pour les sudokus solvables par un humain, avec de la logique.  
 
Quelques idees de methodes a implementer: http://www.mots-croises.ch/Manuels [...] hnique.htm (bonne chance pour certaines [:ddr555] )
 
Le brute force, lui, garantit de trouver une solution ('sil en existe une). Ce que j'ai fait, c'est une sorte de preprocessing avant le brute force qui permet d'optimiser (donc reduire) l'arbre de possibilités histoire de minimiser le temps du backtracking.
 
J'arrive a 4 minutes 52 pour la grille "near worst case" de brute force (69 175 317 appels recursifs !), et 2183 milisecondes en appliquant une astuce qui simplifie le tout (518 275 appels).
 
Il serait d'ailleurs interessant de trouver LA grille worst case, si c'est possible.  
 
Ca devient tres vite tres mathematique, ces trucs :jap:


Message édité par ParadoX le 17-12-2008 à 18:53:41

---------------
Pier noir la mèr - La chanson par HFR Band - Topic TrueCrypt
Reply

Marsh Posté le 17-12-2008 à 21:13:17    

Citation :

J'ai un truc similaire, avant de commencer le brute force je diminue le nombre de candidats pour chaque cellule. Par contre ta methode ne marche que pour les sudokus solvables par un humain, avec de la logique.  

Je fais rarement des sudokus pour le plaisir, alors je ne connais pas les techniques logiques utilisées pour résoudre les grilles, je ne m'attendais pas a un truc parfait, c'etait juste pour voir si la logique simple permettait d'aller plus vite que la force brute.
A+,

Message cité 1 fois

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 18-12-2008 à 14:08:18    

gilou a écrit :

Citation :

J'ai un truc similaire, avant de commencer le brute force je diminue le nombre de candidats pour chaque cellule. Par contre ta methode ne marche que pour les sudokus solvables par un humain, avec de la logique.  

Je fais rarement des sudokus pour le plaisir, alors je ne connais pas les techniques logiques utilisées pour résoudre les grilles, je ne m'attendais pas a un truc parfait, c'etait juste pour voir si la logique simple permettait d'aller plus vite que la force brute.
A+,


Oui.
De ce que je me souviens, les meilleurs solveur de sudoku utilisent avant tout toutes les regles logiques avant de sortir le brute force en dernier recours.


---------------
| AMD Ryzen 7 7700X 8C/16T @ 4.5-5.4GHz - 64GB DDR5-6000 30-40-40 1T - AMD Radeon RX 7900 XTX 24GB @ 2680MHz/20Gbps |
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed