Discussion :

[theprogrammeur]

Bonjour,


Je viens de créer un petit code tout simple pour générer un grille du sudoku (remplie). Malheureusement, lorsque je lance mon programme, il tourne indéfiniment en utilisant 50% du processeur.

Je crois qu'il doit y avoir une boucle infinie mais je ne vois pas où.

Voici mon 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
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
 
using namespace std;
 
int main(){
int grille[9][9];//déclaration de la grille + mise à zéro
 
for(int t=0;t<9;t++){
    for(int w=0;w<9;w++){
        grille[t][w] = 0;
    }
}
 
//Pour la génération des nombres aléatoires
srand((unsigned int)time(NULL));
 
//Les limites pour le tirage au sort
int max = 9;
int min = 1;
bool nombre_ok;
 
//Pour la sélection du nombre de la grille
 
for(int i=0; i<9; i++){
	for(int j=0; j<9; j++){
	    //Début de vérification du nombre pour la ligne
		do{
			nombre_ok = true;
			grille[i][j] = (rand() % (max - min + 1)) + min;
			for(int k=0; k<9; k++){
				if (k!=j){
					if(grille[i][k] == grille[i][j]){
						nombre_ok = false;
					}
				}
			}
 
			//Début de vérification de nombre pour la colonne
 
			if(nombre_ok){//Si nombre_ok vaut true, on va sortir de la boucle parce que tout est juste
			    //Boucle pour lister les différentes propriétés
			    for(int k=0; k<9; k++){
			        if(k!=i){
			            if(grille[k][j] == grille[i][j]){
			                nombre_ok = false;
			            }
			        }
			    }
			}
 
			//Fin de vérification de nombre pour la colonne
		}while (!nombre_ok);
		//Fin de vérification de nombre pour la ligne!
 
	}
}
 
for(int v=0; v<9;v++){
	for(int h=0; h<9; h++){
		cout << grille[v][h];
		cout << " ";
	}
	cout << "\n";
}
 
}

En fait le problème se situe aux lignes

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
if(nombre_ok){//Si nombre_ok vaut true, on va sortir de la boucle parce que tout est juste
			    //Boucle pour lister les différentes propriétés
			    for(int k=0; k<9; k++){
			        if(k!=i){
			            if(grille[k][j] == grille[i][j]){
			                nombre_ok = false;
			            }
			        }
			    }
			}
 
			//Fin de vérification de nombre pour la colonne

Si on les mets en commentaires, le programme fonctionne et toutes les lignes du sudoku sont correctements remplies, mais pas les collones.

J'ai relu plusieurs fois cette partie de code mais je ne vois pas pourquoi il fait bugger le programme.

Merci d'avance pour votre aide.

[CedricMocquillon]

Tu devrais poster sur le forum algorithmes. Tu devrais restreindre au fur et mesure le domaine des possibles (par exemple, si dans une ligne tu as déjà 1, 2 et 7, tu ne devrais tirer le prochain nombre que dans l'ensemble {3,4,5,6,8,9}). Fais des recherches, c'est pas dit que ce soit polynomial de générer une grille aléatoire. Si c'est pas polynomial, renseigne toi du coté de la programmation par contraintes qui te permettra également de résoudre une grille. En tout cas, ton approche n'est pas la bonne, dans le principe, imagine une grille 100000*100000, sur une ligne, lorsque toutes les cases ont un nombre excepté la dernière, la probabilité que tu tires le bon nombre est de 1/100000, c'est normal que ton processeur soit occupé à 50%.

[JolyLoic]

A mon avis, un processeur occupé à 50% signifie juste que tu as un coeur occupé à 100%, sur une machine multicoeur (ici 2 coeurs).

[Lucien63]

Je viens de regarder ton code et j'ai compris pourquoi tu rentre dans une boucle sans fin.
Imagine toi que tu ai remplis la premiere ligne comme cela et la deuxieme comme cela

1 2 3 4 5 6 7 8 9
8 7 6 5 4 3 2 1 _

Quand tu va tirer le dernier numero de la deuxieme ligne et que tu va faire le test.
Et bien tu ne peux mettre aucun numero et ton test n'ai jamais vrai.
Et tu rentre dans une boucle sans fin.
Il faut donc revoir ton algo.