Générer une grille aléatoire pour sudoku en c

Bonjour,

Je souhaite élaborer un petit programme me permettant de générer une grille aléatoire en C.

J'ai commencé à écrire ce programme j'arrive à le compiler sans problème mais il ne s'exécute pas.

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

void estValide(int grille_jeu[9][9]) { int nbre=0,i,j;     for(i=0;i<8;i++) { for(j=0;j<8;j++) {       do {   nbre = rand()%9 + 1;   if ((existe_sur_ligne(nbre,grille_jeu,i)==0) && (existe_sur_colonne(nbre,grille_jeu,j)==0) && (existe_dans_region(nbre,grille_jeu,i,j)==0)) { grille_jeu[i][j] = nbre;   }   }while(grille_jeu[i][j]==0);       } } }

---

Les fonctions existe_sur_ligne() etc sont des fonctions qui permettent de vérifier l'existence sur une colonne, une ligne ou dans une région.
Je les ai trouvées sur le net avec la méthode du backtracking* qui fonctionne très bien mais j'aimerais savoir pourquoi mon programme ne s'exécute pas alors qu'il me semble juste.

Bonjour,

Je te conseillerais d'éviter ce genre de tutoriels où l'auteur ne sait même pas faire la différence entre le C et le C++...

Citation:

---

j'ai choisi le langage C99/C++

---

Le code proposé est aussi de piètre qualité avec des chiffres magiques (chiffres écris en dur dans le programme, sortant de nulle part).

Une fonction "estValide" qui modifie le tableau passé en paramètre... cela n'a pas vraiment de sens :?
De plus je ne pense pas que l'utilisation d'une fonction récursive se justifie ici, au contraire, j'ai plutôt l'impression qu'elle gène à la bonne compréhension de l'algorithme.

Pour en revenir à ton code :

Code:

---

for(i=0;i<9;i++)

---

De même pour le second for.

De plus, en C99, tu peux faire :

Code:

---

for(int i=0;i<9;i++)

---

Code:

---

(existe_sur_ligne(nbre,grille_jeu,i)==0)

---

existe_sur_ligne est censée renvoyée soit vrai ( != 0) soit faux (= 0), le == 0 est donc à proscrire dans ce cas, il vaut mieux mettre

Code:

---

! existe_sur_ligne(nbre,grille_jeu,i)

---

pour faciliter à la compréhension de ton code.

Ensuite tu as une erreur d'algorithmie, il est tout à fait possible que lors du remplissage de ta grille, tu te retrouves bloqué car tu ne pourras mettre aucun chiffre dans un espace vide :

Code:

---

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

---

Et pour finir,

Citation:

---

mais il ne s'exécute pas

---

N'est pas une description suffisante de ton problème pour qu'on puisse t'aider.
Essaye d'utiliser un débogueur et de suivre l'exécution pas à pas pour voir ce qui ne va pas.

Citation:

---

existe_sur_ligne est censée renvoyée soit vrai ( != 0) soit faux (= 0), le == 0 est donc à proscrire dans ce cas, il vaut mieux mettre

---

Je dirais plutôt q'on devrait renvoyer un booléen car c'est bien plus clair d'un point de vue sémantique. De plus, tester un booléen avec ! est clair (bien que plus que tester !0 car voilà bien un code purement C).

Citation:

---

Je te conseillerais d'éviter ce genre de tutoriels où l'auteur ne sait même pas faire la différence entre le C et le C++...

---

Moi aussi ça me donne envie de tuer des gens :mouarf:

Merci pour vos réponses, cela m'éclaire un peu sur l'algorithme.

J'aimerais savoir si la seule méthode de génération d'une grille de sudoku est celle du backtracking car on ne trouve que ça sur les tutos.

J'ai effectivement constaté que sans le do{} while() ça me génère un tableau avec des chiffres qui respectent les conditions du sudoku mais il y a aussi des 0. Ce tableau quand on essaie de le résoudre, on se rend compte qu'il n'y a pas de solution. C'est pour cela qu'il tourne indéfiniment quand je l'exécute avec do while.

J'ai un peu saisi la méthode du backtracking mais comme je dois réaliser ce programme dans le cadre d'un devoir je n'ai pas envie de reprendre les programmes tout fait du backtracking. Pensez vous qu'il existe d'autres méthode de génération de grille aléatoire de sudoku. Je pourrai alors baser mon algorithme sur ces méthodes.

Soit 9 carrés :
1 2 3
4 5 6
7 8 9

On sait déjà que trois régions pourront être calculée à partir des autres.

Qu'entre une et trois régions seront "indépendantes" :

• soit on tire aléatoirement un nombre entre 0 et 9! pour calculer la région 1 (C1)
• soit entre 0 et 9!^2 pour les régions 1 et 9 (C2)
• soit entre 0 et 9!^2 pour les régions 1, 5 et 9 (C3)

Il nous restera donc entre 3 et 5 régions à trouver.


Pour les premières régions (0 pour C3, au plus 2 pour C2 et au plus 4 pour C1), c'est assez simple, on a juste les lignes ou les colonnes à prendre en compte et on a :

• 6*5*4 possibilités pour la première ligne/colonne
• entre 6*5*4 et 3*2 pour la second ligne/colonne selon les résultats de la première colonne
• 3*2 possibilités pour la troisième ligne

Le plus simple serait peut être donc de prendre le cas 1 et de calculer les régions 2,4,6 et 8 ce qui reste assez simple.
Après, il nous restera la région 9, là on aura des contraintes de colonnes et de lignes.


Vu le nombre de possibilité, je pense qu'on peut pré-calculer toutes les solutions possibles à partir des contraintes de lignes et de colonnes et choisir un nombre aléatoire compris entre 0 et nbPossMax pour choisir la possibilité qu'on prendra.

Je répond juste en informant que pour résoudre un sudoku , il y a la récursivité qui est plutôt efficace pour ce genre algo , (Mais peut un peu dur pour un débutant).

Resalut Neckara,

J'ai analysé ta réponse et j'ai du mal à suivre ton raisonnement, j'ai du mal à démarrer.

(Je suis débutante en C)

Citation:

---

Envoyé par lady_nine

Merci pour vos réponses, cela m'éclaire un peu sur l'algorithme.

J'aimerais savoir si la seule méthode de génération d'une grille de sudoku est celle du backtracking car on ne trouve que ça sur les tutos.

J'ai un peu saisi la méthode du backtracking mais comme je dois réaliser ce programme dans le cadre d'un devoir je n'ai pas envie de reprendre les programmes tout fait du backtracking. Pensez vous qu'il existe d'autres méthode de génération de grille aléatoire de sudoku. Je pourrai alors baser mon algorithme sur ces méthodes.

---

Tu peux regarder du coté de la méthode "monte carlo". Le principe de base est qu'ajouter du chaos permet de reduire le nombre d'itérations.
http://www.lptmc.jussieu.fr/user/talbot/sudoku.html

Merci pour ton aide Malinaka, c'est intéressant!