Accueil > Forum > > > > Problème générateur de grille de sudoku en C
Problème générateur de grille de sudoku en C
jeudi 22 décembre 2011 à 00:51:07 |
Problème générateur de grille de sudoku en C

Dovah
|
Bonjour,
je suis débutant en programmation, et pour m'entraîner j'ai décidé de créer un programme qui génère aléatoirement une grille de sudoku en C sur console. Pas très original je sais mais bon
Mon programme génère un nombre de chiffres aléatoires, et chaque chiffre lui même est aléatoire ( enfin modulo 10 ).
Jusque là ça va très, bien, c'est tout facile, mais comme vous la savez y a 3 conditions dans une grille de sudoku : il ne faut pas plusieurs fois le même nombre dans une même ligne, colonne, et dans un carré de 3x3.
J'ai donc décidé de mettre le tout dans une boucle, qui regénérera chaque ligne et colonne ( carré pas encore fait ) jusqu'à ce que ça soit bon.
Voici mon code :
Code C# :
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
int verif_lineaire (int *tob)
{
int i, j, n=0;
int board[9];
for(i=0;i<9;i++)
{
board[i]=tob[i];
}
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(board[i]==board[j])
{
if(board[i]!=0)
{
if(&board[i]!=&board[j])
{
n++; printf("n : %d\n", n);
}
}
}
}
}
printf("\t n final : %d\n", n);
if (n==0) return 1;
else return 0;
}
int main()
{
int i, j, n, k, alea, x, y;
int tab[9][9], tob[9], col[9];
srand(time(NULL));
for(i=0;i<9;i++) //rend nul chaque case
{
tob[i]=0; col[i]=0;
for(j=0;j<9;j++)
{
tab[i][j]=0;
}
}
for(i=0;i<9;i++) //met un nombre de chiffres aléatoires sur chaque ligne
{
n=rand()%7; //nombre de chiffres à mettre
do {
for(j=0;j<n;j++)
{
k=rand()%10; alea=rand()%10;
//k=case aléatoire, alea=nombre à mettre dans la case
tab[i][k]=alea;
}
for(j=0;j<9;j++)
{
tob[j]=tab[i][j];
col[j]=tab[j][i];
}
x=verif_lineaire(&tob); y=verif_lineaire(&col);
}while((x!=1)&&(y!=1));
}
for(i=0;i<9;i++) //affichage
{
for(j=0;j<9;j++)
{
if(j==3) printf("|");
if(j==6) printf("|");
if(tab[i][j]==0) printf(" ");
else if(tab[i][j]!=0) printf("%d", tab[i][j]);
}
printf("\n");
if((i-2)==0) printf("-----------\n");
if((i-5)==0) printf("-----------\n");
}
Sleep(5000);
return 0;
}
Sauf que ça marche pas ^^
Il génère une ligne tant que ma fonction verif n'a pas renvoyé 1.
Or c'est supposé renvoyer 1 quand il n'y a pas plusieurs fois le même chiffre, que ce n'est pas un 0 ( comme j'ai mis des 0 partout, ça correspond aux "espaces" ), et que le chiffre qui est identique n'est pas dans la même case ( avec les adresses, & ).
J'ai essayé de plusieurs manières, là je trouve ça assez hideux 3 if imbriqués, mais le résultat étaient le même de toute façon.
Il génère bien plusieurs fois, mais il s'arrête alors qu'il y a plusieurs fois le même chiffre dans la ligne ou colonne, et ça j'arrive pas à comprendre pourquoi.
Si vous pouviez m'éclaircir sur ce point, merci d'avance.
Ça m'intéresse plus que d'arriver la vérification en elle même.
|
|
jeudi 22 décembre 2011 à 08:06:48 |
Re : Problème générateur de grille de sudoku en C

Renfield
|
if(&board[i]!=&board[j])
equivaut à
if j!=i
if(tab[i][j]==0) printf(" ");
else if(tab[i][j]!=0) printf("%d", tab[i][j]);
le else se suffit a lui même, inutile donc de coder la condition contraire a celle du premier if :
if(tab[i][j]==0) printf(" ");
else printf("%d", tab[i][j]);
if((i-2)==0) printf("-----------\n");
... pourquoi ne pas tester i==2 ?
if (n==0) return 1;
else return 0;
equivaut à
return (n==0);
dans verif_lineaire ; pourquoi recopier ton tableau dans board ?
pourquoi ne pas manipuler le tableau tob dont l'adresse est passée en paramètre ?
k=rand()%10; alea=rand()%10;
pas utile (moins lisible) de mettre deux commandes a la suite sur une même ligne.
Faire:
k=rand()%10;
alea=rand()%10;
sinon, le plus simple est d'écouter ton compilateur...
te permettra de corriger :
x=verif_lineaire(&tob);
y=verif_lineaire(&col);
en
x=verif_lineaire(tob);
y=verif_lineaire(col);
Renfield - Admin CodeS-SourceS - MVP Visual Basic & Spécialiste des RegExp
|
|
jeudi 22 décembre 2011 à 08:42:57 |
Re : Problème générateur de grille de sudoku en C

Lucky92
|
Bonjour,
J'ai quelques petits conseils pour toi :
1/Effectivement, le sudoku c'est pas très original, mais pour apprendre à programmer c'est une très bonne idée  En revanche, générer un sudoku (valide), ce n'est pas si simple que ça. Peut-être devrais tu commencer par programmer un solveur de soduku.
2/Concernant ton algorithme, tu utilises la force brute ; mais cette approche ne sera pas très efficace ici, car le temps nécessaire pour générer une solution va devenir très très grand.
3/Fais attention à la manipulation des tableaux. Le nom d'un tableau est un pointeur sur le tableau, donc
Code C/C++ :
suffit. De même, le test
Code C/C++ :
est très suspect.
4/Pour ta fonction verif_lineaire, tu n'as pas besoin de recopier le tableau d'entrée, tu peux opérer tes tests directement sur celui-ci.
5/De plus, toujours dans verif_lineaire, le nombre de tests peut facilement être divisé par deux en évitant de faire des tests inutiles. Tu peux également utiliser le "pruning", c'est-à-dire, que si tu as trouvé un doublon, il est inutile d'effectuer d'autres tests. Voici une version corrigée de ta fonction :
Code C/C++ : int verif_lineaire (const int *tob)
{
int i, j ;
for(i=0;i<9;++i)
{
for(j=i+1;j<9;++j)
{
if(tob[i]!=0 && tob[i]==tob[j])
{
return 0 ;
}
}
}
return 1 ;
}
6/Outre la fonction précédente qui avait peu de chance de fonctionner dans sa version initiale, tu as également un problème de logique là :
Code C/C++ :
Moi je mettrais plutôt :
Code C/C++ :
A méditer
7/Après avoir mis en oeuvre les corrections ci-dessus, tu risques d'être frustré, car ton programme ne va pas te fournir de solution d'ici plusieurs années, comme je l'ai déjà suggéré. Mon conseil : ne te décourage, c'est maintenant que les défis commencent.
8/Si tu cherches des défis pour apprendre et progresser, je t'invite à découvrir le site suivant : Project Euler
@++
|
|
jeudi 22 décembre 2011 à 08:47:31 |
Re : Problème générateur de grille de sudoku en C

Lucky92
|
@Renfield
Désolé pour les doublons, j'ai vu ton post trop tard.
|
|
jeudi 22 décembre 2011 à 09:09:58 |
Re : Problème générateur de grille de sudoku en C

Renfield
|
a toi de t'amuser a supprimer les valeurs a faire deviner...
Code C/C++ : #include <stdio.h>
#include <time.h>
#include <windows.h>
int fillGrid(int tab[9][9], int position) {
int i, x, y, validCount;
int Numbers[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // Tableau des valeurs possibles
if (position==81) // Grille remplie completement
return 1;
x = position/9;
y = position%9;
for(i=0; i<9; i++) {
Numbers[tab[i][x]] = 0; // On supprime les chiffres de la meme colonne
Numbers[tab[y][i]] = 0; // Et de la meme ligne
Numbers[tab[(y/3)*3+(i/3)][(x/3)*3+(i%3)]] = 0; // Idem pour les carres 3x3
}
// On compte le nombre de résultats restants
validCount = 0;
for(i=1; i<=9; i++)
if (Numbers[i])
validCount++;
while(validCount) {
i = 1+(rand()%9); // Nombre aleatoire...
if (Numbers[i] != 0) { // ...parmis les chiffres valides restant
tab[y][x] = i;
if (fillGrid(tab, position+1)) // Solution validee ? on remonte l'information
return 1;
Numbers[i] = 0; // Le nombre teste n'est pas une valeur possible
validCount--;
tab[y][x] = 0; // On reinitialise la valeur de cette cellule du tableau
}
}
return 0; // Solution non valide
}
void clearGrid (int tab[9][9]) {
for(int y=0; y<9; y++)
for (int x=0; x<9; x++)
tab[y][x] = 0;
}
void displayGrid (int tab[9][9]) {
for(int y=0; y<9; y++) { //affichage
for(int x=0; x<9; x++) {
if(x==3 || x==6)
printf("|");
if(tab[y][x]==0)
printf(" ");
else
printf("%d", tab[y][x]);
}
printf("\n");
if(y==2 || y==5)
printf("---+---+---\n");
}
}
int main() {
int tab[9][9];
srand((unsigned int)time(NULL)); // Initialisation du moteur de generation de nombres aleatoires
clearGrid(tab);
fillGrid(tab, 0);
displayGrid(tab);
getchar(); // Permet un affichage permanant, attendant la pression de [ENTER]
return 0;
}
Renfield - Admin CodeS-SourceS - MVP Visual Basic & Spécialiste des RegExp
|
|
jeudi 22 décembre 2011 à 09:14:34 |
Re : Problème générateur de grille de sudoku en C

Renfield
|
@Renfield
Désolé pour les doublons, j'ai vu ton post trop tard.
Pas de souci, le cache joue souvent des tours...
là, mon code rend la génération quasi instantanée.
Comme je l'ai dit, il reste a supprimer les valeurs a faire deviner. C'est là qu'est le reel défit pour rendre la resolution plus ou moins dure et/ou interessante.
Renfield - Admin CodeS-SourceS - MVP Visual Basic & Spécialiste des RegExp
|
|
jeudi 22 décembre 2011 à 13:28:54 |
Re : Problème générateur de grille de sudoku en C

Dovah
|
Merci de vos réponses.
Pour les différents trucs genre le else if, le board dans la fonction verif, je sais qu'écrit comme ça c'est inutile, c'était juste des traces d'anciennes méthodes que j'avais testé et laissé ^^ mais merci de l'avoir précisé.
if(&board[i]!=&board[j])
equivaut à
if j!=i
effectivement, bien plus clair  mais bon, ça revient un peu au même ^^ tester l'adresse ou le "numéro" correspond à la case
J'ai corrigé, et effectivement c'était l'appel de la fonction qui merdait
Pour moi ne pas mettre &, ça revenait à le sous entendre étend donné qu'on récup avec un pointeur. Donc je voyais pas de différence.
Concernant ton 6) Lucky92, mettre ou à la place de et reviendrait au fait qu'il peut y avoir un doublon dans une même ligne ou colonne, étant donné qu'il suffit qu'il n'y ait pas de doublon dans un des deux.
J'ai laissé mon et, là ça marche bien, aucun doublon, je vais faire des tests pour voir si c'était un coup de bol ou pas.
@Renfield : merci pour ton code, je le regarderai plus tard.
@Lucky92 : merci également pour le site, je le regarderai aussi plus tard ^^.
|
|
jeudi 22 décembre 2011 à 13:41:54 |
Re : Problème générateur de grille de sudoku en C

Renfield
|
NB.
le nom d'un tableau est l'adresse de la première case de ce tableau
Renfield - Admin CodeS-SourceS - MVP Visual Basic & Spécialiste des RegExp
|
|
jeudi 22 décembre 2011 à 13:49:29 |
Re : Problème générateur de grille de sudoku en C

Dovah
|
vivi ^^
Sinon, j'ai mis le OU pour voir, comme prévu j'ai pas mal de doublons sur les colonnes.
Mais avec le && j'en ai aussi, et un peu partout, je comprends pas là 
|
|
jeudi 22 décembre 2011 à 13:51:27 |
Re : Problème générateur de grille de sudoku en C

Renfield
|
regarde mon code, qui propage les erreurs de chiffre en cas d'insolvabilité de la chose
Renfield - Admin CodeS-SourceS - MVP Visual Basic & Spécialiste des RegExp
|
|
Cette discussion est classée dans : int, printf, tab, for, if
Répondre à ce message
Sujets en rapport avec ce message
Problem Affichage de mon Tableau [ par Orezza ]
salut à tous, j'ai un blem à l'affichage du tableau. l'utilisateur parametre son tableau, c lui qui l'initilize mais j'arrive pas à afficher apres le
help une fonction qui a besoin de vous [ par natacha86 ]
Re bonjour a tout le monde, voila j'ai mis tout le prog si vous voulez tester, en fait le pb viens de la fonctino tri_shell(), je ne sais pas pkoi ell
pb en c urgenttttttttttttttttt [ par natacha86 ]
bonjour, j'ai un probleme avec mon programme, il ne veut pas sortir, j'ai fais un menu et apparement ya un bug mais je ne comprend rien.le code est as
compilation mai au lancement "erreur la memoire ne peu pas pas etre read" [ par touny23 ]
je maitrise pas tro le C.mai comme j ai un projet a faire dessus pour la rentré , je sui obligé de m y mettre .j arrive a compiler sous dev-cpp mai lo
tableau [ par ngabou98 ]
bonjour à tous c'est encore moi svp j'ai besoin de votre aide je travaille sur la méthode de simplification d'une fonction booléene par la méthode de
Probleme : Sudoku en C [ par seth59222 ]
Bonsoir, voila je suis actuellement en première année d'info, donc assez novice et je viens de créer ce petit bout de programme en C qui consiste a ré
rectification dune code C et/ou aide sur l'algorithme [ par negets ]
bonjour, besoin d'aide; j'aimerai dégager l'algorithme de ce code afin de le programmer sous matlab je connais plus rien en C et C++(je commence à lir
appel de fonction [ par ibnjabal ]
Bonjour j'essaie de faire une fonction qui calcule la somme de deux matrice et ça fonctionne bien mais seulement c'est quand j'essaie de le faire dans
jeux mode console en c [ par fifiprog ]
Bonsoir a tous je dois creer un jeux sur un damier 10x10 ou tout d'abord deux joueurs pourrons s'affronter c'est le jeux des loups et agneau le but es
probleme d'allocation d'une matrice [ par emomar ]
salut à tous voila j'ai un probleme avec la fonction remplir voila le code si quelqu'un peut m'aider merci code : [code=cpp]#include #include int n
Livres en rapport
|
Derniers Blogs
POUR RAPPEL ! LES SPéCIFICATIONS DES PROTOCOLES OFFICE ET SHAREPOINT SONT DISPONIBLES SUR MSDNPOUR RAPPEL ! LES SPéCIFICATIONS DES PROTOCOLES OFFICE ET SHAREPOINT SONT DISPONIBLES SUR MSDN par neodante
Quelle est le point commun entre : Microsoft il y a 10 ans et Apple aujourd'hui ? Réponse: avoir une politique de protocoles propriétaires et fermés :) Car pour rappel (si si je vous assure c'est important de le rappeler), la majorité des spécifications e...
Cliquez pour lire la suite de l'article par neodante JOYEUX ANNIVERSAIRE NIXJOYEUX ANNIVERSAIRE NIX par ebartsoft
Souhaitons un bon et joyeux anniversaire à notre hôte à tous, Nix.
Je ne le répéterais jamais assez mais sans lui rien ne serait possible. Il défit en permanence les lois de la gravité et comme il le dit si bien, si tu lui fais confiance ça devra...
Cliquez pour lire la suite de l'article par ebartsoft IMAGINE CUP 2012, MAKE A SIGN EN FINALEIMAGINE CUP 2012, MAKE A SIGN EN FINALE par junarnoalg
Voilà qui est fait, la nouvelle est officielle ! L'équipe belge "Make a Sign" va au pays des kangourous défendre son projet dans la catégorie Software Design. http://www.imaginecup.com/CompetitionsContent/Competition/WorldwideFinalists.aspx V...
Cliquez pour lire la suite de l'article par junarnoalg KINECT 1.5 IS OUT !KINECT 1.5 IS OUT ! par Vko
La version 1.5 du Kinect For Microsoft vient tout juste de sortir ! Plein de nouveautés: Tracking de squelette en Near Mode Détection en position assise Détection faciale avec un SDK dédié Documentation et des guideline (enfin) Un out...
Cliquez pour lire la suite de l'article par Vko LES ACTUALITéS DE LA SEMAINE SUR C2I.FR (14 MAI - 20 MAI) LES ACTUALITéS DE LA SEMAINE SUR C2I.FR (14 MAI - 20 MAI) par richardc
Mise à jour des Web API du 14 Mai
Réservez dès maintenant votre journée du 20 juin pour le Windows Azure Dev Camp 2012 à Paris
Mise à jour de Team Foundation Service
MechCommander 2 sur Windows 8
Entity Framework 5 Release Candidate e...
Cliquez pour lire la suite de l'article par richardc
Forum
RGB2GRAYRGB2GRAY par musa18
Cliquez pour lire la suite par musa18
Logiciels
sDEVIS-FACTURES vlPRO (8.1.0.3)SDEVIS-FACTURES VLPRO (8.1.0.3)sDEVIS-FACTURES vlPRO a été mis au point pour les particuliers, créateurs, entrepreneurs, artisa... Cliquez pour télécharger sDEVIS-FACTURES vlPRO 974 Application Server (12.2.4.6)974 APPLICATION SERVER (12.2.4.6)Développez de puissantes applications dans un environnement de 'cloud computing', clusterisé, séc... Cliquez pour télécharger 974 Application Server vPicture (1.4.2.1)VPICTURE (1.4.2.1)Avec vPicture, hébergez vos images facilement et rapidement.
vPicture est un utilitaire simple, ... Cliquez pour télécharger vPicture Easy-Planning (2.2.1.6)EASY-PLANNING (2.2.1.6)Easy-Planning permet de créer des plannings sous la représentation de diagrammes et est adapté au... Cliquez pour télécharger Easy-Planning COM-BACKUP (2.0)COM-BACKUP (2.0)
COM-BACKUP est un logiciel de sauvegarde qui permet de planifier les sauvegardes de vos dossiers ...
Cliquez pour télécharger COM-BACKUP
|