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; } bool lds (int ordre); bool trylds (int i, int j, int val, int ordre) { var [i] [j].affecte (val); if (consistant (i, j, val)) if (lds (ordre)) return true; remet (); var [i] [j].desaffecte (); return false; } bool lds (int ordre) { int i, j; DomaineIntervalle *d = choisitVariable (i, j); if (d == NULL) return true; int val [TailleMax], nb_vals = enumereValeurs (i, j, val); if (ordre == 0) { if (trylds (i, j, val [0], ordre)) return true; } else { for (int k = 1; k < nb_vals; k++) { if (trylds (i, j, val [k], ordre - 1)) return true; } if (nb_vals > 0) if (trylds (i, j, val [0], ordre)) return true; } return false; } bool id_lds () { for (int ordre = 0; ordre < taille * taille; ordre++) { if (lds (ordre)) return true; } return false; } 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; } } int main (int argc, char **argv) { init (); if (id_lds ()) afficheSolution (); }