nDames_qt/forwardchecking.cpp at master · srakotoniary/nDames_qt · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include "forwardchecking.h"
#include <iostream>

ForwardChecking::ForwardChecking(int nb): Algo(nb,0)
{
    initFC();
    execution(0);
    //std::cout << "nombre de Sol" << nbSol.size()<<std::endl;
    //std::cout << "nombre Iter" << nbIter <<std::endl;
}

void ForwardChecking::execution(int x){
     nbIter++;
     QVector<int > tmp;

     /*
     spec ts = { 5000 / 1000, (5000 % 1000) * 1000 * 1000 };
     nanosleep(&ts, NULL);
     */

     if(x < nbReines){
         for(int j = x; j < Echiquier.size() ; j += nbReines){   //ligne suivante
             tmp = Echiquier;            //sauvegarde le domaine actuel

             if(Echiquier[j] == 1){      //si la position est possible
                 supprimeDomaine(j);            //on supprime les domaines qui interfere avec la position
                 execution(x+1);                //colonne suivante
                 Echiquier=tmp;                 //restaure les domaines
             }
         }
     } else {
         //affiche();
         nbSol.push_back(Echiquier);                       //on sauvegarde la solution
         //std::cout << nbSol.size() <<std::endl;
     }
}

void ForwardChecking::initFC(){
    for(int i=0; i<nbReines*nbReines; i++){
        Echiquier[i]=1;
    }
}


void ForwardChecking::supprimeDomaine(int position){

    int ligne = position / nbReines;
    int colonne = position % nbReines;

    //test ligne
    for (int i = ligne*nbReines; i < ligne*nbReines + nbReines; i++){
        if(i != position)
            if(Echiquier[i]==1)
                Echiquier[i]=0;
    }

    //test colonne
    for (int i = colonne; i<nbReines * nbReines; i = i + nbReines ){
        if ( i != position)
            if(Echiquier[i]==1)
                Echiquier[i]=0;
    }

    //std::cout<<"test colonne ok"<<std::endl;

    //Digonale sud-est
    if(colonne+1 != nbReines)
    for (int i = position + (nbReines+1); i < nbReines * nbReines; i = i+ (nbReines+1) ){
        if((i%nbReines) == 0)   //si c'est la premiere colonne on break (cas ou on a depasser la limite du bord a droite)
            break;
        if(Echiquier[i]==1)
            Echiquier[i]=0;
    }

    //Digonale nord-ouest
    if(colonne != 0)
    for (int i = position - (nbReines + 1); i >= 0 ; i = i - (nbReines + 1) ){
        if((i%nbReines)+1 == nbReines)
            break;
        if(Echiquier[i]==1)
            Echiquier[i]=0;
    }

    //Diagonale Nord-est
    if(colonne+1 != nbReines)
    for (int i = position- (nbReines-1); i >= 0 ; i= i - (nbReines - 1) ){

        if(Echiquier[i]==1)
            Echiquier[i]=0;
        if((i%nbReines)+1 == nbReines)
            break;
    }

    //Diagonale Sud-ouest
    if(colonne != 0)
    for (int i = position + (nbReines-1); i < nbReines * nbReines; i = i + (nbReines - 1) ){
        if((i%nbReines)+1 == nbReines)
            break;
        if(Echiquier[i]==1)
            Echiquier[i]=0;
    }

}

//=========================================================================================================

/*
void Algo::fc(int x){
    nbIter++;
    if(x<nbReines)
        for(int j = x; j < Echiquier.size() ; j += nbReines){   //ligne suivante
            if(placementPossible(j)){
                 Echiquier[j]=1;
                 fc(x+1);            //colonne suivante
                 Echiquier[j]=0;              //restaure les domaines

            }
        }
   else {
            affiche();
            nbSol.push_back(Echiquier);
            std::cout << nbSol.size() <<std::endl;

        }


}
*/