Bonjour les gens....

Je suis en train d'écrire un petit programme en java (sur eclipse) permettant de résoudre n'importe quel sudoku.

Mon problème est que j'ai un souci avec ma méthode resoudSudoku() car du moment où elle a trouvé la solution, elle continue de s'exécuter et tourne donc a l'infini... Cette méthode est recursive. La clause de finitude m'a donc l'air correcte. Bref... Je ne trouve pas LE truc. Est-ce que quelqu'un peut m'aider ?

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
package Backtracking;
 
public class Sudoku {
 
	private int [][] M ;
	private int [] caseVide ;
 
	public Sudoku(int [][] M) {
		this.M = M ;
		caseVide = new int[2] ;
	}
 
	public void resoudSudoku() {
		resoudSudoku(0, 0) ;
	}
 
	private void resoudSudoku(int ligne, int colonne) {
		if (ligne == M.length)
			return ;
 
		for (int nombre = 1; nombre < 10; nombre++) {
			if (estPossible(ligne, colonne, nombre)) {
				M[ligne][colonne] = nombre ;
				System.out.println();
				afficheMatrice() ;
				prochaineCaseVide(ligne, colonne) ;
				resoudSudoku(caseVide[0], caseVide[1]) ;
			}
			M[ligne][colonne] = 0 ;
		}
	}
 
	private void prochaineCaseVide(int ligne, int colonne) {
		if (ligne == M.length)
			return ;
 
		for (int j = colonne; j < M[0].length; j++) {
			if (M[ligne][j] == 0) {
				caseVide[0] = ligne ;
				caseVide[1] = j ;
				return ;
			}
		}
 
		prochaineCaseVide(ligne + 1, 0) ;
	}
 
	private boolean estPossible(int ligne, int colonne, int nombre) {	
		// Test si le nombre existe dans la ligne
		for (int j = 0; j < M[0].length; j++) {
			if (M[ligne][j] == nombre)
				return false ;
		}
 
		// Test si le nombre existe dans la colonne
		for (int i = 0; i < M.length; i++) {
			if (M[i][colonne] == nombre)
				return false ;
		}
 
		// Test si le nombre existe dans le carré
		int indCarreColonneMin = getIndCarre(colonne) ;
		int indCarreLigneMin = getIndCarre(ligne) ;
 
		for (int i = indCarreLigneMin; i < indCarreLigneMin + 3; i++) {
			for (int j = indCarreColonneMin; j < indCarreColonneMin + 3; j++) {
				if (M[i][j] == nombre)
					return false ;
			}
		}
 
		return true ;
	}
 
	private int getIndCarre(int i) {
		int ind = 0 ;
 
		switch (i) {
			case 0 : ind = 0 ; break ;
			case 1 : ind = 0 ; break ;
			case 2 : ind = 0 ; break ;
			case 3 : ind = 3 ; break ;
			case 4 : ind = 3 ; break ;
			case 5 : ind = 3 ; break ;
			case 6 : ind = 6 ; break ;
			case 7 : ind = 6 ; break ;
			case 8 : ind = 6 ; break ;
		}
 
		return ind ;
	}
 
 
	public void afficheMatrice() {
		for (int i = 0; i < M.length; i++) {
			for (int j = 0; j < M[0].length; j++) {
				System.out.print(M[i][j] + "  ");
			}
			System.out.println();
		}
	}
 
	public static void main(String [] args) {
		int [][] M = 	{{0,0,4,0,0,0,5,0,0},
				{0,0,3,2,0,6,9,0,0},
				{6,0,0,0,5,0,0,0,3},
				{0,4,1,7,0,9,3,5,0},
				{0,0,0,0,0,0,0,0,0},
				{0,5,6,3,0,2,8,7,0},
				{8,0,0,0,3,0,0,0,7},
				{0,0,2,9,0,7,1,0,0},
				{0,0,7,0,0,0,6,0,0}} ;
 
		Sudoku sudoku = new Sudoku(M) ;
		sudoku.afficheMatrice() ;
		sudoku.resoudSudoku() ;
	}
}