Discussion :

[HqSeO]

Bonjour,
Je voudrais vous expliquer mon problème rencontré depuis quelques mois sur un programme finis.
Mon programme est un resolveur de sudoku en bactracking c++.
Sauf que j'ai un problème de boucle infinie dans ma méthode de résolution.
Je vous présente ma méthode:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
-une grille 9x9 dont il faut trouver les solutions.
-j'ai les chiffres 123456789.
-Je boucle de 1 a 9  (indice i)
      -je présente i (présente me renvoie le tableau possible pour
       poser ce nombre)
      -tant que le tableau des position n'est pas fini:
            -je pose le chiffre.
            -je rappelle resoudre ( si vrai alors return true)
            -je retire la piece.
            -j'incremente mon tableau de position.
-return false.

Biensur j'ai une condition qui test si le sudoku est resolu .... mais j'ai mit le coeur de la methode

Vous l'aurez compris ceci est une méthode de brute force pure et simple je test toutes les positions possible d'un chiffre.
on pourrait assimiler à un arbre ...
Si vous ne comprenez ma méthode de résolution je peut vous fournir une image l'expliquant.

La question: Existe t-il a cause de ma methode des cas de boucles infinies liée au sudoku? si oui ma programmation tiens la route si non ba je sais pas ou ca bug et je posterai dans le forum C++... xD

Merci de vous penchez sur mon problème si vous voulez le code ou autre demandez mais j'ai tester toutes mes sous méthodes cela voudrait dire que c'est mon résoudre qui plante :s merci de votre aide
HqSeO

[ToTo13]

Bonjour,

mmm... c'est assez curieux comme Backtracking. En général on avance plutôt case par case et pour chacune met tous les nombres possibles. Puis lorsque l'on est à la fin (dernière case) on lance une procédure de vérification.

Surtout que renvoyer un tableau, ce doit être assez lourd au niveau allocation/libération. C'est d'ailleurs peut être pas une boucle infinie, mais plutôt un temps de calcul exorbitant.

Petite question : tu n'as pas de case remplie au préalable ?
En regardant ton code, on dirait que tu souhaites trouver toutes les grilles possible de sudoku. Ce serait alors plutôt un générateur de grille qu'un solveur.

[pseudocode]

La question: Existe t-il a cause de ma methode des cas de boucles infinies liée au sudoku? si oui ma programmation tiens la route si non ba je sais pas ou ca bug et je posterai dans le forum C++... xD

Le méthode en elle meme est bonne, mais je ne comprend pas trop pourquoi il y a à la fois une "BOUCLE" et un "TANT QUE".

La boucle seule est suffisante.

En général on avance plutôt case par case et pour chacune met tous les nombres possibles. Puis lorsque l'on est à la fin (dernière case) on lance une procédure de vérification.

Heu... Là tu fais une exploration totale. Il est plus performant d'arrêter l'exploration au plus tôt, par exemple en utilisant une recherche taboo (verrouillage des valeurs déja utilisées, et donc non utilisables).

Code java :

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
public boolean solverec(int position) {
 
	// exit condition : finished !
	if (position==N*N) return true;
 
	int row = position/N;
	int col = position%N;
 
	// this is a fixed cell -> next one
	if (solution[row][col]!=0)
		return solverec(position+1);
 
	// test all possible values for the current cell
	for(int val=1;val<=N;val++) {
		// value already used
		if (islocked(row,col,val)) continue;
 
		// set value
		solution[row][col]=val;
		setlock(row,col,val, true); 
 
		// try to solve the remaining cells. Exit if success.
		if (solverec(position+1)) return true;
 
		// unset value
		setlock(row,col,val, false); 
		solution[row][col]=0;
	}
 
	// no valid value for the current cell.
	return false;
}

[HqSeO]

Pour répondre aux disverses questions à la base ma méthode résoudre doit s'éxporter pour un résolveur de puzzle à réaliser plus tard.

La première boucle permet de prendre les chiffres de 1 à 9 (for)
la deuxième boucle permet de parcourir les positions de l'indice du for(while)

Oui je résoud des grilles déjà remplies expert medium enfin nombre de case déjà remplie.
Mais pour un exemple :
J'ai une grille de 27 chiffre a trouver ca dure 10 sec. mais sur cette même grille j'enleve un autre chiffre et boum ....
Après c'est ce que je me douter le temps de résolutions mais sachant que c'est assez rapide poser retirer etc...
m'enfin je vous post resoudre:

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
 
#include "Sudoku.h"
 
 
bool Sudoku::resoudre(){
 
	if(nok()) throw 1.0;
 
	if(m_nNbPiecesPosees==m_nNbPieces)	return true;
 
	triangle** position;
	int j=0;
		//Premiere boucle pour les pieces
		//
		for ( int i = 1 ; i<10; i++){
 
		position=presenter(i);	
 
		j=0;
			//Deuxieme boucle pour balayer le tableau de position
			//
			while (position[j]!=NULL){
 
				poser(i,position[j]);
 
 
				//Appel recursif
				//
				if(resoudre()){ int p=0;
								while(position[p]!=NULL){
								delete position[p++];
								}
								p=0;
								delete[] position;
								return true;}
 
				retirer(0,position[j]);
 
				j++;  
			}
 
		int p=0;
		while(position[p]!=NULL){
			delete position[p++];
		}
		p=0;
		delete[] position;
	}
	return false;
 
}

Merci de vos réponses mais je désirerai ne pas toucher à la méthode.
Je sais que c'est brutale mais alors cela viendrai tout simplement du nombre élévé de cas à tester qui pourrait prendre des jours ?
J'ai déjà laissé tourné cette methode pendant une nuit...

ha oui pour que vous comprennez les types :

Code :

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

1
2
3
4
 
#define triangle  int
#define Pieces    int
#define Polygone  Matrice

[pseudocode]

Pour répondre aux disverses questions à la base ma méthode résoudre doit s'éxporter pour un résolveur de puzzle à réaliser plus tard.

La première boucle permet de prendre les chiffres de 1 à 9 (for)
la deuxième boucle permet de parcourir les positions de l'indice du for(while)

Tu n'a pas besoin de la 2eme boucle. Il te suffit de passer la position en paramètre de ta fonction récursive, comme je l'ai fait dans mon exemple Java.

J'ai une grille de 27 chiffre a trouver ca dure 10 sec. mais sur cette même grille j'enleve un autre chiffre et boum ....

(...)

Merci de vos réponses mais je désirerai ne pas toucher à la méthode.
Je sais que c'est brutale mais alors cela viendrai tout simplement du nombre élévé de cas à tester qui pourrait prendre des jours ?

Hum... sur un PC moderne, la résolution ne devrait jamais prendre 10 secondes. Au pire 2 a 3 secondes pour les grilles nécessitant beaucoup de backtracking. Mais jamais des "jours".

[HqSeO]

Merci pour l'erreur sur la deuxième boucle mais je ne la changerai ( pas obstiné ) mais je respecte le cahier des charges pour le puzzle
donc on est bien d'accord ma fonction provoque des boucles infinies ...
Hum il me reste plus qu'a comprendre où, dans quelle cas je boucle ...
merci de vos réponses ...

[acx01b]

salut

je ne suis pas d'accord avec toi pseudocode, la résolution peut prendre pas mal de temps (2 minutes si mes souvenirs sont bons)

je te conseille de ne pas traiter les cases dans l'ordre (1,1) , (1,2), ... (1,9), (2,1) .... (9,9)
mais de traiter en premier la case où le nombre de possible (nombre de chiffres possibles) est le plus petit, ça permet de ne pas faire de cas spécial pour les cases où il n'y a qu'un seul chiffre possible, et 0 chiffre possible = return false et backtracker

cette heuristique est très efficace (résolution 200 fois plus rapide ?), même si je ne crois pas qu'il y ait de démonstration prouvant qu'elle 'est dans tous les cas, ni dans quelle mesure

[pseudocode]

salut

je ne suis pas d'accord avec toi pseudocode, la résolution peut prendre pas mal de temps (2 minutes si mes souvenirs sont bons)

Tu as un exemple de grille dont la résolution prend 2 minutes ? Ca m'interresse assez.

je te conseille de ne pas traiter les cases dans l'ordre (1,1) , (1,2), ... (1,9), (2,1) .... (9,9)
mais de traiter en premier la case où le nombre de possible (nombre de chiffres possibles) est le plus petit, ça permet de ne pas faire de cas spécial pour les cases où il n'y a qu'un seul chiffre possible, et 0 chiffre possible = return false et backtracker

Oui, c'est une très bonne heuristique et qui est assez simple à mettre en place.