IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Java Discussion :

Sudoku boucle infinie


Sujet :

Java

  1. #1
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2009
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : Suisse

    Informations forums :
    Inscription : Janvier 2009
    Messages : 3
    Par défaut Sudoku boucle infinie
    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() ;
    	}
    }

  2. #2
    Modérateur
    Avatar de Alkhan
    Homme Profil pro
    ingénieur full stack
    Inscrit en
    Octobre 2006
    Messages
    1 232
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : ingénieur full stack

    Informations forums :
    Inscription : Octobre 2006
    Messages : 1 232
    Par défaut
    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.
    Il n'y a pas de problème, il n'y a que des solutions.
    Cependant, comme le disaient les shadoks, s'il n'y a pas de solution, c'est qu'il n'y a pas de problème.
    Si toutefois le problème persiste, la seule solution restante est de changer le périphérique qui se trouve entre la chaise et l'écran

    Mes Articles : Mon premier article est sur le language D
    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java

  3. #3
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2009
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : Suisse

    Informations forums :
    Inscription : Janvier 2009
    Messages : 3
    Par défaut
    Citation Envoyé par Alkhan Voir le message
    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.

  4. #4
    Modérateur
    Avatar de Alkhan
    Homme Profil pro
    ingénieur full stack
    Inscrit en
    Octobre 2006
    Messages
    1 232
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : ingénieur full stack

    Informations forums :
    Inscription : Octobre 2006
    Messages : 1 232
    Par défaut
    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.
    Il n'y a pas de problème, il n'y a que des solutions.
    Cependant, comme le disaient les shadoks, s'il n'y a pas de solution, c'est qu'il n'y a pas de problème.
    Si toutefois le problème persiste, la seule solution restante est de changer le périphérique qui se trouve entre la chaise et l'écran

    Mes Articles : Mon premier article est sur le language D
    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java

  5. #5
    Membre confirmé Avatar de NutellaPiou
    Profil pro
    Inscrit en
    Octobre 2008
    Messages
    107
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2008
    Messages : 107
    Par défaut
    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?

  6. #6
    Modérateur
    Avatar de Alkhan
    Homme Profil pro
    ingénieur full stack
    Inscrit en
    Octobre 2006
    Messages
    1 232
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : ingénieur full stack

    Informations forums :
    Inscription : Octobre 2006
    Messages : 1 232
    Par défaut
    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.
    Il n'y a pas de problème, il n'y a que des solutions.
    Cependant, comme le disaient les shadoks, s'il n'y a pas de solution, c'est qu'il n'y a pas de problème.
    Si toutefois le problème persiste, la seule solution restante est de changer le périphérique qui se trouve entre la chaise et l'écran

    Mes Articles : Mon premier article est sur le language D
    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java

  7. #7
    Membre confirmé Avatar de NutellaPiou
    Profil pro
    Inscrit en
    Octobre 2008
    Messages
    107
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2008
    Messages : 107
    Par défaut
    Initialiser une variable globale avec le nombre de cases à 0
    Et la décrémenter à chaque fois qu'on en rempli une.

    Pourquoi pas?

  8. #8
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2009
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : Suisse

    Informations forums :
    Inscription : Janvier 2009
    Messages : 3
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : 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
    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!

  9. #9
    Modérateur
    Avatar de dinobogan
    Homme Profil pro
    ingénieur
    Inscrit en
    Juin 2007
    Messages
    4 073
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France

    Informations professionnelles :
    Activité : ingénieur
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 4 073
    Par défaut
    Ouhala ! Ta conception est vraiment très compliquée
    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 : 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
    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();
    	}
    }
    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java
    Que la force de la puissance soit avec le courage de ta sagesse.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Boucle Infinie dans le Sudoku
    Par HqSeO dans le forum Mathématiques
    Réponses: 7
    Dernier message: 12/02/2009, 13h42
  2. Réponses: 29
    Dernier message: 17/06/2006, 13h04
  3. Réponses: 15
    Dernier message: 24/05/2005, 08h34
  4. [Socket] Pb de boucle infinie
    Par Myogtha dans le forum Entrée/Sortie
    Réponses: 12
    Dernier message: 10/06/2004, 14h10
  5. [C#] Comment eviter les boucles infinies ?
    Par Thomas Lebrun dans le forum C#
    Réponses: 12
    Dernier message: 09/06/2004, 00h04

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo