Sudoku boucle infinie

Version imprimable

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:

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

21/01/2009, 17h58
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.
21/01/2009, 19h33
theblubberin

Citation:

Envoyé par Alkhan

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.
22/01/2009, 09h32
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.
22/01/2009, 09h54
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?
22/01/2009, 10h42
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.
22/01/2009, 11h34
NutellaPiou

Initialiser une variable globale avec le nombre de cases à 0
Et la décrémenter à chaque fois qu'on en rempli une.

Pourquoi pas?

Alors tout d'abord un grand merci pour tout votre aide!!! Je suis nouveau ici mais je pense que je reviendrai plus souvent ;-)

Alors j'ai opté pour la solution avec la variable du nombre de cases remplies. J'ai modifié un peu mon code (nom des méthodes en anglais et méthodes statiques).

Il faut que je sache combien de case il y a à remplir. Ceci est donc possible grâce à ma méthode cellsToFill() qui retourne un entier qui va être affecter à ma variable cellsToFill. (Dans le cas testé dans le main, il y a 51 cases à remplir)

Dans ma méthode solve(), j'ai rajouter donc un test :

Code:

1
2
3
 
if (filledCells >= cellsToFill)
	return M ;

filledCells s'incrémente à chaque fois que la méthode trouve un nombre pouvant être placé dans la case courante et se décrémente lors du backtracking. Si le nombre de cases à remplir est atteint, plus nécessaire de faire du backtracking (revenir en arrière) - donc retour de la matrice contenant le résultat.

Voilà la classe un petit main au fond qui test l'application :

Code:

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
package Backtracking;
 
public class Sudoku {
 
	private static int [] emptyCell = new int [2] ;
	private static int cellsToFill = 0 ;
	private static int filledCells = 0 ;
 
	public static int [][] solve(int [][] M) {
		cellsToFill = cellsToFill(M) ;
		return solve(M, 0, 0) ;
	}
 
	private static int [][] solve(int [][] M, int raw, int column) {
		if (raw == M.length)
			return M ;
 
		for (int n = 1; n < 10; n++) {
			if (isValid(M, raw, column, n)) {
				M[raw][column] = n ;
				emptyCell(M, raw, column) ;
				filledCells++ ;
				solve(M, emptyCell[0], emptyCell[1]) ;
			}
			if (filledCells >= cellsToFill)
				return M ;
			M[raw][column] = 0 ;
		}
		filledCells-- ;
 
		return M ;
	}
 
	private static int cellsToFill(int [][] M) {
		int nbCellsToFill = 0 ;
 
		for (int i = 0; i < M.length; i++)
			for (int j = 0; j < M[0].length; j++)
				if (M[i][j] == 0)
					nbCellsToFill++ ;
 
		return nbCellsToFill ;
	}
 
	private static void emptyCell(int [][] M, int raw, int column) {
		if (raw == M.length)
			return ;
 
		for (int j = column; j < M[0].length; j++) {
			if (M[raw][j] == 0) {
				emptyCell[0] = raw ;
				emptyCell[1] = j ;
				return ;
			}
		}
 
		emptyCell(M, raw + 1, 0) ;
	}
 
	private static boolean isValid(int [][] M, int raw, int column, int n) {	
		// Check if n exists in raw
		for (int j = 0; j < M[0].length; j++)
			if (M[raw][j] == n)
				return false ;
 
		// Check if n exists in column
		for (int i = 0; i < M.length; i++)
			if (M[i][column] == n)
				return false ;
 
		// Check if n exists in square
		int minColumnIndInSquare = getSquareInd(column) ;
		int minRawIndInSquare = getSquareInd(raw) ;
 
		for (int i = minRawIndInSquare; i < minRawIndInSquare + 3; i++) {
			for (int j = minColumnIndInSquare; j < minColumnIndInSquare + 3; j++) {
				if (M[i][j] == n)
					return false ;
			}
		}
 
		return true ;
	}
 
	private static int getSquareInd(int i) {
		switch (i) {
			case 0 : return 0 ;
			case 1 : return 0 ;
			case 2 : return 0 ;
			case 3 : return 3 ;
			case 4 : return 3 ;
			case 5 : return 3 ;
 
			default : return 6 ;
		}
	}
 
	public static void showMatrix(int [][] M) {
		for (int  i= 0; i < M.length; i++) {
			for (int j = 0; j < M.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}} ;
 
 
		System.out.println("Input : ");
		Sudoku.showMatrix(M) ;
		System.out.println();
		System.out.println("Output : ");
		Sudoku.showMatrix(Sudoku.solve(M)) ;
	}
}

Encore un grand merci pour votre aide!

Ouhala ! Ta conception est vraiment très compliquée :roll:
La récursivité peut très bien se débrouiller sans problème. Regarde ton code modifié (et au passage, regarde aussi la simplification à une seule ligne de la méthode "getSquareInd" :

Code:

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
public class Sudoku
{
	private int[][]	M;
 
	public Sudoku( int[][] M )
	{
		this.M = M;
	}
 
	public boolean resoudSudoku()
	{
		return resoudSudoku( 0, 0 );
	}
 
	private boolean resoudSudoku( int ligne, int colonne )
	{
		while( ligne < M.length && colonne < M[ ligne ].length && M[ ligne ][ colonne ] != 0 )
		{
			++colonne;
			if( colonne >= M[ ligne ].length )
			{
				colonne = 0;
				++ligne;
			}
		}
 
		if( ligne >= M.length || colonne >= M[ ligne ].length )
		{
			return true;
		}
		else
		{
			for( int nombre = 1 ; nombre <= 9 ; ++nombre )
			{
				if( estPossible( ligne, colonne, nombre ) )
				{
					M[ ligne ][ colonne ] = nombre;
					int nextCol = colonne + 1;
					int nextlig = ligne;
 
					if( nextCol >= M[ ligne ].length )
					{
						nextCol = 0;
						nextlig = ligne + 1;
 
						if( nextlig >= M.length )
						{
							return true;
						}
					}
 
					if( ! resoudSudoku( nextlig, nextCol ) )
					{
						M[ ligne ][ colonne ] = 0;
					}
				}
			}
 
			return M[ ligne ][ colonne ] != 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 )
	{
		return ( i / 3 ) * 3;
	}
 
	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 solver = new Sudoku( M );
		solver.resoudSudoku();
		solver.afficheMatrice();
	}
}