/* Sudoku - Moteur.cs Moteur de résolution du Sudoku - Methode du BackTracking Version 1.0 - Last Modif : 25/04/2006 22:26 Développé par SeBeuh < sebeuh [arobase] ajsinfo [point].net > (c) 2006 - http://sebeuh.ajsinfo.net */ using System; using System.Collections.Generic; using System.Text; namespace SudokuSolve { class Moteur { // Variables private Grille grille; // Constructeur public Moteur(Grille grInitial) { grille = grInitial; } // Fonction de résolution du Sudoku // Renvoi la grille completée public Grille Resolution() { // Init. des variables int tmp = 0; Pointeur pIndex = new Pointeur(0, -1); debut: // Recuperation de la prochaine case non-modifiable // dans le pointeur pIndex = Suivant(pIndex); //Program.Afficher(test, pIndex); newval: // Si le pointeur est arrivé à [10,10] // c'est gagné, on renvoi la grille if(pIndex.colonne == 10 && pIndex.ligne == 10) return grille; // Incrementation de la valeur de la case du pointeur tmp = grille.contenu[pIndex.ligne, pIndex.colonne].valeur; tmp++; test: // Si la valeur est possible if (estPossible(tmp, pIndex)) { // Inscription dans la case et retour au debut grille.contenu[pIndex.ligne, pIndex.colonne].valeur = tmp; goto debut; } else { // Si la valeur n'est pas possible, on test la valeur suivante tmp++; if (tmp > 9) { // Cas ou la valeur a testé est > à 9 (aucune valeur possible) // On effectue un BackTracking (marche arriere ^^) backtracking: // Mise a zero de la case grille.contenu[pIndex.ligne, pIndex.colonne].valeur = 0; // Pointage sur la case (non-modifiable) precedente pIndex = Precedent(pIndex); // Au cas où le retour arriere est allé un peu trop long // En theorie, cela ne se produit que si la grille de depart // est erroné. if (pIndex.colonne == -1 || pIndex.ligne == -1) throw new Exception("Erreur"); else { // Si on est deja a 9, on repart encore en arriere // sinon on retourne à newval. if (grille.contenu[pIndex.ligne, pIndex.colonne].valeur >= 9) goto backtracking; else goto newval; } } else { // Retour au test goto test; } } } // Fonction retournant un bool si 'valeur' // est possible au pointeur (position) 'index' private bool estPossible(int valeur, Pointeur index) { // Verif dans la ligne for (int a = 0; a < 9; a++) { if (grille.contenu[index.ligne, a].valeur == valeur) return false; } // Verif dans la colonne for (int a = 0; a < 9; a++) { if (grille.contenu[a, index.colonne].valeur == valeur) return false; } // Verif dans la region int dc = 0, dl = 0, fc = 0, fl = 0; // Region (ligne) if (index.ligne >= 0 && index.ligne <= 2) { dl = 0; fl = 3; } else if (index.ligne >= 3 && index.ligne <= 5) { dl = 3; fl = 6; } else if (index.ligne >= 6 && index.ligne <= 8) { dl = 6; fl = 9; } // Region (colonne) if (index.colonne >= 0 && index.colonne <= 2) { dc = 0; fc = 3; } else if (index.colonne >= 3 && index.colonne <= 5) { dc = 3; fc = 6; } else if (index.colonne >= 6 && index.colonne <= 8) { dc = 6; fc = 9; } // Test dans la region for (int a = dl; a < fl; a++) { for (int b = dc; b < fc; b++) { if (grille.contenu[a, b].valeur == valeur) return false; } } // Sinon c'est que c'est vrai (possible) : return true; } // Fonction donnant le pointeur precedent l'index private Pointeur Precedent(Pointeur index) { bool first = true; for (int l = index.ligne; l >= 0; l--) { for (int c = 8; c >= 0; c--) { if (first) { c = --index.colonne; first = false; } if (c < 0) break; if (!grille.contenu[l, c].locked) return new Pointeur(l, c); } } // Erreur dans le programme ! return new Pointeur(-1, -1); } // Fonction donnant le pointeur suivant de l'index private Pointeur Suivant(Pointeur index) { bool first = true; for (int l = index.ligne; l < 9; l++) { for (int c = 0; c < 9; c++) { if (first) { c = ++index.colonne; first = false; } if (c > 8) break; if (!grille.contenu[l, c].locked) return new Pointeur(l, c); } } // Tout est déjà rempli (solution trouvée!) return new Pointeur(10, 10); } } // Struture de la grille (tableau de Case) struct Grille { // Champs private Case[,] _contenu; // Constructeur public Grille(bool init) { _contenu = new Case[9, 9]; if (init) { for (int a = 0; a < 9; a++) { for (int b = 0; b < 9; b++) { _contenu[a, b].valeur = 0; _contenu[a, b].locked = false; } } } } // Accesseurs public Case[,] contenu { get { return _contenu; } set { _contenu = value; } } } // Structure d'une case struct Case { // Champs private int _valeur; private bool _locked; // Constructeur public Case(int valeur,bool locked) { _valeur = valeur; _locked = locked; } // Accesseurs public int valeur { get { return _valeur; } set { _valeur = value; } } public bool locked { get { return _locked; } set { _locked = value; } } } // Struture du pointeur struct Pointeur { // Champs private int _ligne; private int _colonne; // Accesseurs public int colonne { get { return _colonne; } set { _colonne = value; } } public int ligne { get { return _ligne; } set { _ligne = value; } } // Constructeur public Pointeur(int ligne, int colonne) { _ligne = ligne; _colonne = colonne; } // Surcharge de la methode ToString() public override string ToString() { return "[" + _ligne + "," + _colonne + "]"; } } }