Discussion :

[theblubberin]

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() ;
	}
}

[Alkhan]

bonjour,

Le problème que tu as viens du fait que la méthode prochaineCaseVide(...) fini par te renvoyé ligne = 8 et colonne = 8.
mais la méthode resoudSudoku(...) ne sais pas quand elle doit stopper le traitement.

Il faut juste que tu stop le traitement de résolution lorsque tu a traiter la dernière case = à 0.

[theblubberin]

bonjour,
Il faut juste que tu stop le traitement de résolution lorsque tu a traiter la dernière case = à 0.

Oui je comprends ce que tu veux dire...

prochaineCaseVide retournera toujours :

caseVide[0] = 8 ; // ligne
caseVide[1] = 8 ; // colonne

ce qui représente donc la dernière case de ma matrice.

Mais je ne sais pas comment m'y prendre pour appliquer ta solution.

[Alkhan]

bonjour,

C'est vrai le problème n'est pas simple, mais je pense qu'il faut que tu trouve le moyen de comptabilisé le nombre de case = à 0.
Et lorsque ce nombre = 0 alors tu sors.

[NutellaPiou]

Essaie une méthode (ex : estRemplie) qui retourne un boolean.

Elle parcourt tout ton tableau et dès qu'elle trouve un 0 elle return false.

Comme dans ta méthode resoudSudoku() tant que !estRemplie() tu fais tes traitements.

C'est peut être un peu "lourd", vous en dites quoi les autres?

[Alkhan]

c'est une solution qui est effectivement la plus facile a mettre en place, mais qui est très très lourde car pour chaque case traitée il faut parcourir l'ensemble des cases.
C'est pour cela que je ne l'ai pas envisagé.

je pense vraiment que le moyen de s'en sortir sans trop de mal est de gérer le nombre de case = à 0 au cours du traitement.