[Sources] Solveur de sudoku

**smartties** · 27/08/2013, 11h08

Salut, voici un solveur de sudoku qui utilise les nodes.
Le code n'est pas optimisé, je l'ai commenté un minimum pour qu'il soit compréhensible,
désolé pour le franglais. Si vous avez des conseils d'optimisation, ou sur la structure
du code, je suis preneur .

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
#include <iostream>   
#include <string>   
#include <vector>   
#include <stdio.h>   
#include <stdlib.h>   
#include "math.h"   
 
using namespace std;   
 
std::string tab;   
 
void draw()   
{   
    int i, j;   
 
    system("cls");   
    for(i = 0; i < 9; i++)   
    {   
        for(j = 0; j < 9; j++)   
        {   
            cout << tab[i*9+j] << " ";   
        }   
        cout << endl;   
    }   
}   
 
class node   
{   
    public :   
    node()   
    {   
        x = 0;   
        y = 0;   
    }   
 
    int x;   
    int y;   
};   
 
class Solver   
{   
    public :   
    Solver()   
    {   
        nb_open = 0;   
        ptr = NULL;   
        w = 0;   
        h = 0;   
    }   
 
    bool fonction(int _w, int _h, const char *_ptr)   
    {   
        int i;   
        int x, y;   
        bool notfound = false;   
 
        w = _w;   
        h = _h;   
        if(ptr == NULL || w == 0 || h == 0)   
        return false;   
 
        while(!issolved())   
        {   
            draw(); // je redessine l'ecran   
 
            node *current = NULL;   
 
            if(iscompleted() || notfound) // si le sudoku est complet ou si un node n'est pas correct   
            {   
                notfound = false;   
                current = get_last(); // je demande le node le plus récent   
 
                if(current != NULL)   
                {   
                    if(get_nombre(current->x, current->y) == 9 || get_increment(current->x, current->y) == -1) // si le node n'est pas incrementable   
                    {   
                        verify_increment(); // je supprime tous les nodes qui ne sont pas incrémentale   
                        current = get_last();// je demande le nodes le plus récent   
 
                        if(current != NULL)   
                        {   
                            int nombre = get_increment(current->x, current->y);   
                            if(nombre != -1)   
                            set_nombre(current->x, current->y, nombre); //j’incrémente le node   
                        }   
                    }   
                    else   
                    {   
                        int nombre = get_increment(current->x, current->y);   
                        if(nombre != -1)   
                        set_nombre(current->x, current->y, nombre);//j’incrémente le node   
                    }   
                }   
            }   
            else   
            {   
                if(get_next(&x, &y) == 1) // je cherche la prochaine '.' qui correspond à une case vide   
                {   
                    int nombre = get_default(x, y); //   
 
                    if(nombre != -1)// si il existe un nombre que l'on peut mettre dans la case(x, y) tout en respectant les règles   
                    {   
                        add_node(x, y, nombre); // ajout du node   
                    }   
                    else // sinon on revient en arrière afin de changer un node précédent   
                    notfound = true;   
                }   
            }   
        }   
 
        return true;   
    }   
    bool get_next(int *x, int *y)   //donne au variable x, y les coordonné de la prochaine case vide
    {   
        int i, j;   
 
        for(i = 0; i < h; i++)   
        {   
            for(j = 0; j < w; j++)   
            {   
                if(iscompleted(j, i) == false)   
                {   
 
    x = j;
    y = i;
 
 
                    return true;   
                }   
            }   
        }   
        return false;   
    }   
    int get_default(int x, int y)   //trouver le chiffre le plus proche de 0, que l'on peut mettre dans la case
    {   
        int i;   
 
        for(i = 0; i <= 9; i++)   
        {   
            if(isright(x, y, i))   
            {   
                return i;   
            }   
        }   
 
        return -1;   
    }   
    int get_increment(int x, int y)   //renvoi la valeur incrementé, ou -1 si ce n'est pas possible
    {   
        int i;   
 
        int nombre = get_nombre(x, y);   
 
        for(i = nombre+1; i <= 9; i++)   
        {   
            if(isright(x, y, i))   
            {   
                return i;   
            }   
        }   
 
        return -1;   
    }   
    int get_nombre(int x, int y)   
    {   
        if(ptr[y*w+x] == '.')   
        return -1;   
 
        return ptr[y*w+x] - 48;   
    }   
    void set_nombre(int x, int y, int var)   
    {   
        if(var == -1)   
        ptr[y*w+x] = '.';   
        else   
        ptr[y*w+x] = var + 48;   
    }   
 
    bool issolved()   //renvoie vrai si la grille est complète et vrai
    {   
        if(iscompleted())   
        {   
            int i, j;   
 
            for(i = 0; i < h; i++)   
            for(j = 0; j < w; j++)   
            {   
                if(isright(j, i, get_nombre(j, i)) == 0)   
                return false;   
            }   
            return true;   
        }   
        return false;   
    }   
    bool isright(int x, int y, int var)   // Renvoie vrai si le chiffre n'est pas répété sur horizontalement ou verticalement
    {   
        int i, j;   
        bool cond = true;   
 
        for(i = 0; i < h && cond; i++)   
        {   
            for(j = 0; j < w && cond; j++)   
            {   
                if( (j == x || i == y) &&   
                    !(j == x && i == y))   
                {   
                    if(get_nombre(j, i) == var)   
                    return false;   
                }   
            }   
        }   
 
        return true;   
    }   
 
    bool iscompleted()    // renvoie vrai si toutes les cases sont complétées
    {   
        int i, j;   
 
        for(i = 0; i < h; i++)   
        {   
            for(j = 0; j < w; j++)   
            {   
                if(!iscompleted(j, i))   
                return false;   
            }   
        }   
        return true;   
    }   
    bool iscompleted(int x, int y)   //renvoie vrai la case est completée
    {   
        if(get_nombre(x, y) == -1)   
        return false;   
 
        return true;   
    }   
 
    void add_node(int x, int y, int var)   
    {   
        node *foo = new node;   
        foo->x = x;   
        foo->y = y;   
        set_nombre(x, y, var);   
        open_list.push_back(foo);   
        nb_open++;   
    }   
    node *get_last()   //donne un pointeur sur le node le plus récent
    {   
        if(nb_open > 0)   
        {   
            return open_list[nb_open-1];   
        }   
 
        return NULL;   
    }   
    void verify_increment()   //fonction qui supprime tous les noeux qui ne sont plus incrémentale 
    {   
        if(nb_open > 0)   
        {   
            if(get_nombre(open_list[nb_open-1]->x, open_list[nb_open-1]->y) == 9 ||   
               get_increment(open_list[nb_open-1]->x, open_list[nb_open-1]->y) == -1)   
            {   
                pop();   
                verify_increment();   
            }   
        }   
    }   
    bool pop()   //enleve le node le plus récent
    {   
        if(nb_open > 0)   
        {   
 
            set_nombre(open_list[nb_open-1]->x, open_list[nb_open-1]->y, -1);   
            delete open_list[nb_open-1];   
            nb_open--;   
            open_list.pop_back();   
 
            return true;   
        }   
        return false;   
    }   
 
    void erase_data()   
    {   
        open_list.erase(open_list.begin(), open_list.end());   
        ptr = NULL;   
        w = 0;   
        h = 0;   
        nb_open = 0;   
    }   
 
    vector <node*> open_list;   
    int w;   
    int h;   
    char *ptr;   
    int nb_open;   
};   
 
int main()   
{   
    Solver sudoku;   
 
    tab+= ".3...1...";   
    tab+= "..6....5.";   
    tab+= "5.....983";   
    tab+= ".8...63.2";   
    tab+= "....5....";   
    tab+= "9.38...6.";   
    tab+= "714.....9";   
    tab+= "32....8..";   
    tab+= "...4...3.";   
 
    sudoku.fonction(9, 9, tab.c_str());   
    sudoku.erase_data();   
 
    draw();   
 
    return 0;   
}

**smartties** · 28/08/2013, 08h52

Un 2/5, mon code est il si nul que ça ?
Si c'est le cas veuillez m'indiquer quels sont les problèmes

Merci

**nono_31** · 28/08/2013, 11h18

Bonjour,

J'ai jeté un coup d'oeil rapidement :

Pourquoi la classe Node ne prend aussi pas la valeur de la case ?
Quel est l'algorithme de résolution ?

**smartties** · 28/08/2013, 12h22

Salut
Pour résoudre ce sudoku j'utilise le concept du backtracking.
c'est à dire que j’essaie tout les solutions possible et lorsque je bloque
je reviens en arrière, ceci tant que le sudoku n'est pas résolu.

la classe Node ne prend pas la valeur de la case, parce que
je modifie directement le tableau. Ce n'est pas donc nécessaire de stocker
la valeur dans le node.
Si tu veux accéder à la valeur du node tu peux utiliser la méthode get_nombre(node.x, node.y);

Invité · 06/09/2013, 04h08

Bonjour,

Envoyé par smartties

Un 2/5, mon code est il si nul que ça ?
Si c'est le cas veuillez m'indiquer quels sont les problèmes

Heu... déjà il compile pas ?

>> g++ -Wall -Wextra main.cpp -c
main.cpp: In member function 'bool Solver::fonction(int, int, const char*)':
main.cpp:53:13: warning: unused variable 'i' [-Wunused-variable]
         int i;
             ^
main.cpp: At global scope:
main.cpp:51:10: warning: unused parameter '_ptr' [-Wunused-parameter]
     bool fonction(int _w, int _h, const char *_ptr)
          ^
main.cpp: In member function 'bool Solver::get_next(int*, int*)':
main.cpp:124:7: error: invalid conversion from 'int' to 'int*' [-fpermissive]
     x = j;
       ^
main.cpp:125:7: error: invalid conversion from 'int' to 'int*' [-fpermissive]
     y = i;
       ^

Ton code est un savant mélange de C/C++
Utilisation de variable globale tab.
Pourquoi #include "math.h" et non #include <math.h> (ou plutôt #include <cmath> en C++) ? Et qui sert à quoi ici ?
Tu ne te sers pas du paramètre _ptr rentré dans la méthode fonction, tu ne connais donc jamais ta grille, et utilises un pointeur NULL tout le long
Et même si tu t'en servais, std::string::c_str() renvoie une chaine temporaire non-modifiable.

Code c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool get_next(int *x, int *y)   //donne au variable x, y les coordonné de la prochaine case vide
    {   
        int i, j;   
 
        for(i = 0; i < h; i++)   
        {   
            for(j = 0; j < w; j++)   
            {   
                if(iscompleted(j, i) == false)   
                {   
 
    x = j;
    y = i;
 
 
                    return true;   
                }   
            }   
        }   
        return false;   
    }

Outre l'indentation à revoir, comme la plupart de tes if, tu rentres des pointeurs et leur assignes des entiers ! La syntaxe correcte est :

Code c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
*x = i;
*y = j;

Tu as une fuite de mémoire à cette ligne :
Code c++ : Sélectionner tout - Visualiser dans une fenêtre à part
```
open_list.erase(open_list.begin(), open_list.end());
```
il te faut faire un delete sur chaque élément avant.
Autant utiliser des node direct plutôt que des pointeurs selon moi.
system("cls"); n'est pas portable.

Code c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
    Solver()   
    {   
        nb_open = 0;   
        ptr = NULL;   
        w = 0;   
        h = 0;   
    }

préfère utiliser une liste d'initialisation.

Code c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
node *foo = new node;   
foo->x = x;   
foo->y = y;

autant faire un constructeur node(int, int)

Je trouve l'utilité de la fonction bool iscompleted(int x, int y) très limitée

**smartties** · 06/09/2013, 23h08

Merci

[Sources] Solveur de sudoku

Contribuez

Discussions similaires

Partager

Partager