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> #include<stdlib.h> using namespace std; int nombreVariables; DomaineIntervalle *variables; int nbReines = 8; void initReines (); void afficheSolution (); bool backtrack (int numVar = 0); /* une variable par colonne, avec une valeur par case de la colonne */ void initReines () { nombreVariables = nbReines; variables = new DomaineIntervalle [nbReines]; for (int i = 0; i < nombreVariables; i++) variables [i].alloue (nbReines); } bool consistante (int numVar) { int val = variables [numVar].valeur (); for (int i = 0; i < nombreVariables; i++) if (i != numVar) if (variables [i].affectee ()) { int vali = variables [i].valeur (); /* meme ligne */ if (val == vali) return false; /* meme diagonale */ if (val + (i - numVar) == vali) return false; if (val - (i - numVar) == vali) return false; } return true; } void afficheSolution () { for (int i = 0; i < nombreVariables; i++) cout << variables [i].valeur () << " "; cout << endl; } bool backtrack (int numVar) { if (numVar == nombreVariables) return true; else for (int i = 0; i < variables [numVar].taille (); i++) { variables [numVar].affecte (i); if (consistante (numVar)) if (backtrack (numVar + 1)) return true; variables [numVar].desaffecte (); } return false; } int main (int argc, char **argv) { if (argc > 1) nbReines = atoi (argv [1]); initReines (); if (backtrack (0)) afficheSolution (); }