Discussion :

[maximus95380]

Bonjour tout le monde.

Voilà mon problème. Je suis en train de programmer en JAVA un programme permettant de générer des grilles de Sudoku. Le programme est fonctionnel car il me génère des grilles. Malheureusement, il ne me génère pas tout le temps la grille, et toutes les x lancements de la compilation du code (le x varie entre 3 à 32 en moyenne), j'ai un beau message d'erreur : java.lang.StackOverflowError.

Est ce que quelqu'un pourrait m’expliquer le fait que la plupart du temps le programme marche sauf les fois ou il me met ce message d'erreur?

Merci d'avance !

Voici le code :

Code :

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
public class Grille {
 
    private int[][] sudoku;
 
    public Grille() {
        sudoku = new int[9][9];
        genGrille(0, 0);
    }
 
    public int[][] getGrille() {
        return sudoku;
    }
 
    private void genGrille(int x, int y) {
        if (x < 9) {
            if (x == -1) {
                System.out.println("Erreur !!!!");
            }
            int precvaleur = sudoku[x][y];
            sudoku[x][y] = 10;
            int[] possible = new int[9];
            int compteur = 0;
            for (int i = 1; i <= 9; i++) {
 
                if (verif(x, y, i)) {
                    possible[compteur] = i;
                    compteur++;
                }
            }
            int nbalea = (int) (Math.random() * compteur);
            sudoku[x][y] = possible[nbalea];
            //System.out.println("Le nombre aléatoire est "+nbalea+" qui ajoute le nombre "+sudoku[x][y]);
            if (possible[nbalea] == 0) {
                if (y > 0) {
                    if (x == 0 && y == 0) {
                        genGrille(x, y);
                    } else if (y == 0) {
                        genGrille(x, y - 1);
                    } else {
                        genGrille(x - 1, 8);
                    }
                }
            }
            if (y == 8) {
                //System.out.println(sudoku[x][y]);
                genGrille(x + 1, 0);
            } else {
                //System.out.print(sudoku[x][y] + " ");
                genGrille(x, y + 1);
            }
        }
    }
 
    private boolean verifligne(int x, int nombre) {
        int i = 0;
        while (i < 8 && sudoku[x][i] != nombre) {
            i++;
        }
        if (sudoku[x][i] == nombre) {
            return false;
        }
        return true;
    }
 
    private boolean verifcolonne(int y, int nombre) {
        int i = 0;
        while (i < 8 && sudoku[i][y] != nombre) {
            i++;
        }
        if (sudoku[i][y] == nombre) {
            return false;
        }
        return true;
    }
 
    private boolean verifcarre(int x, int y, int nombre) {
        if (y < 3 && x < 3) {
            return carre(0, 0, nombre);
        } else if (y < 6 && x < 3) {
            return carre(0, 3, nombre);
        } else if (y < 9 && x < 3) {
            return carre(0, 6, nombre);
        } else if (y < 3 && x < 6) {
            return carre(3, 0, nombre);
        } else if (y < 6 && x < 6) {
            return carre(3, 3, nombre);
        } else if (y < 9 && x < 6) {
            return carre(3, 6, nombre);
        } else if (y < 3 && x < 9) {
            return carre(6, 0, nombre);
        } else if (y < 6 && x < 9) {
            return carre(6, 3, nombre);
        } else if (y < 9 && x < 9) {
            return carre(6, 6, nombre);
        }
        return false;
    }
 
    private boolean carre(int x, int y, int nombre) {
        for (int i = x; i <= x + 2; i++) {
            for (int j = y; j <= y + 2; j++) {
                if (sudoku[i][j] == nombre) {
                    return false;
                }
            }
        }
        return true;
    }
 
    private boolean verif(int x, int y, int nombre) {
        if (!verifligne(x, nombre)) {
            return false;
        }
        if (!verifcolonne(y, nombre)) {
            return false;
        }
        if (!verifcarre(x, y, nombre)) {
            return false;
        }
        return true;
    }
}

Dans mon main je fais juste un appel pour créer une nouvelle grille.

Voici le message d'erreur :

Code :

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
Exception in thread "main" java.lang.StackOverflowError
	at gsudoku2.Grille.genGrille(Grille.java:35)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
	at gsudoku2.Grille.genGrille(Grille.java:56)
	at gsudoku2.Grille.genGrille(Grille.java:50)
	at gsudoku2.Grille.genGrille(Grille.java:59)
        [...]

Voici enfin le résultat quand tout ce passe normalement :
(l'affichage est gérer dans le main)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
run:
--------------------------
| 7 6 8  | 1 9 4  | 3 2 5 |
| 5 9 2  | 7 8 3  | 4 1 6 |
| 1 3 4  | 5 2 6  | 7 8 9 |
--------------------------
| 8 7 1  | 4 6 9  | 5 3 2 |
| 9 5 3  | 2 1 8  | 6 4 7 |
| 4 2 6  | 3 5 7  | 1 9 8 |
--------------------------
| 6 1 7  | 9 3 2  | 8 5 4 |
| 3 8 9  | 6 4 5  | 2 7 1 |
| 2 4 5  | 8 7 1  | 9 6 3 |
BUILD SUCCESSFUL (total time: 0 seconds)

[thelvin]

Parce que ton système ne garantit pas qu'il avance à chaque itération, et il peut certainement se retrouver souvent dans une boucle infinie ou irréalistement longue.

[djanggawul]

Une erreur stackOverFlowError intervient quand le programme a une pile d'appel trop importante. Dans ton cas, c'est la récursivité qui pose problème. Et comme à écrit thelvin, il faut vérifier que ton algo puisse dans tout les cas se terminer.

D'une manière générale, il y a deux options pour gérer les stackOverFlowError :
- Tu augmentes la taille de ta stack avec le paramètre de la JVM -Xss (par ex: -Xss1m), mais ça va juste te permettre de repousser un peu le problème
- Tu modifies l'algo pour qu'il ne soit plus récursif

[andry.aime]

Bonsoir,

Tu as des codes morts ici:

Code :

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

1
2
3
4
5
6
7
8
9
if (y > 0) {
    if (x == 0 && y == 0) {
        genGrille(x, y);
    } else if (y == 0) {
        genGrille(x, y - 1);
    } else {
        genGrille(x - 1, 8);
    }
}

A+.

[maximus95380]

Bonsoir,

Tu as des codes morts ici:

Code :

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

1
2
3
4
5
6
7
8
9
if (y > 0) {
    if (x == 0 && y == 0) {
        genGrille(x, y);
    } else if (y == 0) {
        genGrille(x, y - 1);
    } else {
        genGrille(x - 1, 8);
    }
}

A+.

Merci j'ai modifier cette partie de code. Voilà ce que donne la nouvelle partie de code :

Code :

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

1
2
3
4
5
6
7
8
9
if (possible[nbalea] == 0) {
                if (y > 0) {
                    genGrille(x, y - 1);
                } else if (x > 0) {
                    genGrille(x - 1, 8);
                } else {
                    genGrille(x, y);
                }
            }

Maintenant j'ai l'erreur... tout le temps...

[andry.aime]

Re,

L'erreur vient de la fonction récursive genGrille qui fait une boucle infinie.

A+.