class DomaineIntervalle { int _taille; int _nb_valeurs; bool *_presente; bool _affectee; int _valeur; public: void alloue (int t) { _taille = t; _presente = new bool [_taille]; init (); } void init () { for (int i = 0; i < _taille; i++) { _presente [i] = true; } _nb_valeurs = _taille; _affectee = false; } int taille () { return _taille; } int nb_valeurs () { return _nb_valeurs; } bool affectee () { return _affectee; } int valeur () { return _valeur; } bool presente (int v) { return _presente [v]; } bool ote (int v) { if (_presente [v]) { _presente [v] = false; _nb_valeurs--; return true; } return false; } void remet (int v) { _presente [v] = true; _nb_valeurs++; } void affecte (int v) { _affectee = true; _valeur = v; } void desaffecte () { _affectee = false; } }; #include<iostream> using namespace std; const int TailleMax = 25; int tailleCarre = 5, taille = tailleCarre * tailleCarre; DomaineIntervalle var [TailleMax] [TailleMax]; void init () { for (int i = 0; i < taille; i++) { for (int j = 0; j < taille; j++) var [i] [j].alloue (taille); } } #include<stack> stack<int> pile; void ote (int i, int j, int val) { if (var [i] [j].ote (val)) { pile.push (i); pile.push (j); pile.push (val); } } void remet () { while (pile.top () != -1) { int val = pile.top (); pile.pop (); int j = pile.top (); pile.pop (); int i = pile.top (); pile.pop (); var [i] [j].remet (val); } pile.pop (); } bool consistant (int i, int j, int val) { pile.push (-1); /* une seule fois la meme valeur par ligne */ for (int ii = 0; ii < taille; ii++) if (ii != i) if (!var [ii] [j].affectee ()) { ote (ii, j, val); if (var [ii] [j].nb_valeurs () == 0) return false; } /* une seule fois la meme valeur par colonne */ for (int jj = 0; jj < taille; jj++) if (jj != j) if (!var [i] [jj].affectee ()) { ote (i, jj, val); if (var [i] [jj].nb_valeurs () == 0) return false; } /* une seule fois la meme valeur par carre */ int starti = tailleCarre * (i / tailleCarre), startj = tailleCarre * (j / tailleCarre); for (int ii = starti; ii < starti + tailleCarre; ii++) for (int jj = startj; jj < startj + tailleCarre; jj++) if ((jj != j) && (ii != i)) if (!var [ii] [jj].affectee ()) { ote (ii, jj, val); if (var [ii] [jj].nb_valeurs () == 0) return false; } return true; } DomaineIntervalle * choisitVariable (int & i, int & j) { DomaineIntervalle *v = NULL; int min = taille + 1, memi, memj; for (int ibis = 0; ibis < taille; ibis++) for (int jbis = 0; jbis < taille; jbis++) if (!var [ibis] [jbis].affectee ()) if (var [ibis] [jbis].nb_valeurs () < min) { min = var [ibis] [jbis].nb_valeurs (); i = ibis; j = jbis; v = &var [i] [j]; } return v; } int enumereValeurs (int i, int j, int *val) { int nb = 0; for (int k = 0; k < taille; k++) if (var [i] [j].presente (k)) { val [nb] = k; nb++; } return nb; } void afficheSolution () { for (int i = 0; i < taille; i++) { for (int j = 0; j < taille; j++) if (var [i] [j].affectee ()) cout << var [i] [j].valeur () << " "; else cout << " "; cout << endl; } } #include<stdlib.h> class Move { public : int _i, _j, _value; Move (int i = 0, int j = 0, int value = 0) { _i = i; _j = j; _value = value; } }; Move variation [1000]; int sample (int depth) { int i, j, maxd = depth; DomaineIntervalle *d = choisitVariable (i, j); if (d == NULL) return depth; int val [TailleMax], nb_vals = enumereValeurs (i, j, val); if (nb_vals == 0) return depth; int indice = rand () % nb_vals; Move m (i, j, val [indice]); variation [depth] = m; var [i] [j].affecte (val [indice]); if (consistant (i, j, val [indice])) maxd = sample (depth + 1); if (maxd == taille * taille) return maxd; remet (); var [i] [j].desaffecte (); return maxd; } int nbBestRollout [4]; Move bestRollout [4] [1000]; int nested (int nbPrefix, Move prefix [1000], int n) { int nbPrefixStart = nbPrefix; nbBestRollout [n] = 0; while (true) { int i, j; DomaineIntervalle *d = choisitVariable (i, j); if (d == NULL) return nbPrefix; int val [TailleMax], nb_vals = enumereValeurs (i, j, val); Move bestMove = bestRollout [n] [nbPrefix]; int best = nbBestRollout [n]; for (int k = 0; k < nb_vals; k++) { Move m (i, j, val [k]); var [i] [j].affecte (val [k]); if (consistant (i, j, val [k])) { if (n == 1) { int lengthPlayout = sample (nbPrefix + 1); if (lengthPlayout > best) { best = lengthPlayout; bestMove = m; nbBestRollout [n] = best; bestRollout [n] [nbPrefix] = m; for (int l = nbPrefix + 1; l < lengthPlayout; l++) bestRollout [n] [l] = variation [l]; } } else { int lengthPlayout = nested (nbPrefix + 1, prefix, n - 1); if (lengthPlayout > best) { best = lengthPlayout; bestMove = m; nbBestRollout [n] = best; bestRollout [n] [nbPrefix] = m; for (int l = nbPrefix + 1; l < lengthPlayout; l++) bestRollout [n] [l] = bestRollout [n - 1] [l]; } } } if (best == taille * taille) return best; remet (); var [i] [j].desaffecte (); } var [bestMove._i] [bestMove._j].affecte (bestMove._value); if (consistant (bestMove._i, bestMove._j, bestMove._value)) { prefix [nbPrefix] = bestMove; nbPrefix++; } else break; } if (nbPrefix == taille * taille) return nbPrefix; for (int n = nbPrefix - 1; n >= nbPrefixStart; n--) { remet (); var [prefix [n]._i] [prefix [n]._j].desaffecte (); } return nbPrefix; } int main (int argc, char **argv) { init (); while (true) { Move prefix [1000]; int nb = nested (0, prefix, 1); cout << nb << " "; if (nb == taille * taille) break; } cout << endl; afficheSolution (); }