Problème générateur de grille de sudoku en C [Résolu]

Dovah 10 Messages postés jeudi 22 décembre 2011Date d'inscription 23 décembre 2011 Dernière intervention - 22 déc. 2011 à 00:51 - Dernière réponse : Renfield 17308 Messages postés mercredi 2 janvier 2002Date d'inscription 22 août 2018 Dernière intervention
- 23 déc. 2011 à 15:51
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 :
#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.
Afficher la suite 

Votre réponse

23 réponses

Meilleure réponse
Renfield 17308 Messages postés mercredi 2 janvier 2002Date d'inscription 22 août 2018 Dernière intervention - 22 déc. 2011 à 09:09
3
Merci
a toi de t'amuser a supprimer les valeurs a faire deviner...


#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

Merci Renfield 3

Avec quelques mots c'est encore mieux Ajouter un commentaire

Codes Sources a aidé 88 internautes ce mois-ci

Commenter la réponse de Renfield
Renfield 17308 Messages postés mercredi 2 janvier 2002Date d'inscription 22 août 2018 Dernière intervention - 22 déc. 2011 à 08:06
0
Merci
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
Commenter la réponse de Renfield
cs_Lucky92 180 Messages postés mercredi 22 décembre 2004Date d'inscription 16 août 2012 Dernière intervention - 22 déc. 2011 à 08:42
0
Merci
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
verif_lineaire(tob);

suffit. De même, le test
if(&board[i]!=&board[j])

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 :
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à :
}while((x!=1)&&(y!=1));

Moi je mettrais plutôt :
}while((x!=1)||(y!=1));

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

@++
Commenter la réponse de cs_Lucky92
cs_Lucky92 180 Messages postés mercredi 22 décembre 2004Date d'inscription 16 août 2012 Dernière intervention - 22 déc. 2011 à 08:47
0
Merci
@Renfield
Désolé pour les doublons, j'ai vu ton post trop tard.
Commenter la réponse de cs_Lucky92
Renfield 17308 Messages postés mercredi 2 janvier 2002Date d'inscription 22 août 2018 Dernière intervention - 22 déc. 2011 à 09:14
0
Merci
@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
Commenter la réponse de Renfield
Dovah 10 Messages postés jeudi 22 décembre 2011Date d'inscription 23 décembre 2011 Dernière intervention - 22 déc. 2011 à 13:28
0
Merci
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 ^^.
Commenter la réponse de Dovah
Renfield 17308 Messages postés mercredi 2 janvier 2002Date d'inscription 22 août 2018 Dernière intervention - 22 déc. 2011 à 13:41
0
Merci
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
Commenter la réponse de Renfield
Dovah 10 Messages postés jeudi 22 décembre 2011Date d'inscription 23 décembre 2011 Dernière intervention - 22 déc. 2011 à 13:49
0
Merci
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à
Commenter la réponse de Dovah
Renfield 17308 Messages postés mercredi 2 janvier 2002Date d'inscription 22 août 2018 Dernière intervention - 22 déc. 2011 à 13:51
0
Merci
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
Commenter la réponse de Renfield
Dovah 10 Messages postés jeudi 22 décembre 2011Date d'inscription 23 décembre 2011 Dernière intervention - 22 déc. 2011 à 14:15
0
Merci
Il est bien, mais c'est pas du tout la même méthode.
Par contre dans ton fillgrid, quel intérêt de rendre nul ligne, colonne et carré ? et aussi pourquoi tu return 1, pour pas faire la suite je suppose, dans ce cas c'est pas mieux un continue ?

Mais je vois pas en quoi ça pourrait m'aider pour mon problème de doublon.
Commenter la réponse de Dovah
Renfield 17308 Messages postés mercredi 2 janvier 2002Date d'inscription 22 août 2018 Dernière intervention - 22 déc. 2011 à 14:28
0
Merci
Je suis parti de ton code.

je n'ai pas réussi a le faire fonctionner en l'etat
j'ai du revoir l'algo, voilà tout. Donc tes problemes de doublon sont plus compliqués que cela...
tu dois voir la grille dans son ensemble, avec les reglesdu sudoku...
toi, tu dis (plus tard les carrés 3x3, ce n'est pas la bonne solution)

Numbers est le tableau des valeurs possibles pour la case étudiée.

on supprime donc de ce tableau les chiffres deja utilises dans la meme ligne, la meme colonne et le meme carré 3x3

ensuite, on tente de completer le reste de la grille.

si on se bloque (aucun nombre valide restant dans Numbers, validCount=0)
on revient en arrière en essayant un autre nombre de Numbers

le Return 1 est pour quitter l'instance de la procédure en cours.

if (fillGrid(tab, position+1))
return 1;

cela permet aussi de valider successivement les differents appel de la fonction (recursive)



Renfield - Admin CodeS-SourceS - MVP Visual Basic & Spécialiste des RegExp
Commenter la réponse de Renfield
Dovah 10 Messages postés jeudi 22 décembre 2011Date d'inscription 23 décembre 2011 Dernière intervention - 22 déc. 2011 à 14:54
0
Merci
Okay.
Mais je ne vois quand même pas comment Numbers[tab[i][x]] = 0; ( par exemple ) peut supprimer les mêmes chiffres d'une même ligne. Admettons que tab[0][0]=5, ça donnerait numbers[5]=0, la 5ème case devient 0, t'as plus de 4 ... et après ?

Tu n'es pas arrivé à enlever les doublons alors :s pourtant ça doit être possible, même si c'est pas une bonne méthode.
Au fait, ton programme remplit une grille sans doublons selon les 3 règles du sudoku, ; mais peut-être c'est ton mal compris ? Moi je n'essayais pas de remplir complètement une grille, juste d'en proposer 1 correcte, sans doublons, que l'utilisateur aurait lui-même solutionner par la suite, manuellement. Si tu as essayé de la remplir complètement directement, c'est sûr qu'il fallait changer d'algo ^^
Commenter la réponse de Dovah
Renfield 17308 Messages postés mercredi 2 janvier 2002Date d'inscription 22 août 2018 Dernière intervention - 22 déc. 2011 à 15:06
0
Merci
la 5ème case devient 0


exactement.

joues en pas a pas, tu verras...

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

concernant les doublons, le soucis est que pour une meme case, tu as plusieurs possibilités.
si tu te contente de prendre la première, tu va te bloquer dans le remplissage des futures cases.

mon soft rempli bien selon les trois regles

la grille générée est valide, complète etc.

il faut ensuite mettre a 0 un certain nombre de cases, de manière a laisser l'utilisateur solutionner.
a toi de plancher sur un algo efficace pour donner une grille de tel ou tel niveau de difficulté, ayant une solution unique, etc.

Renfield - Admin CodeS-SourceS - MVP Visual Basic & Spécialiste des RegExp
Commenter la réponse de Renfield
Dovah 10 Messages postés jeudi 22 décembre 2011Date d'inscription 23 décembre 2011 Dernière intervention - 22 déc. 2011 à 15:29
0
Merci
Donc, selon toi, pour que mon code marche, il faut changer la manière d'attribution d'un chiffre aléatoire dans une colonne aléatoire ?
for(j=0;j<n;j++)
{
     k=rand()%10;
     alea=rand()%10;   
     tab[i][k]=alea;
}

cette partie là en gros ? mais même si je l’empêche de retomber sur une même case/de tirer un 0, je vois pas ce que ça va changer
Commenter la réponse de Dovah
Renfield 17308 Messages postés mercredi 2 janvier 2002Date d'inscription 22 août 2018 Dernière intervention - 22 déc. 2011 à 15:36
0
Merci
ton code, tel qu'il est conçu ne pourra générer de grille e sudoku...

fixe n à 9, tu verras bien !

ca va tourner en boucle, sans succès.

il ne suffit pas de generer une grille en placant quelques chiffres qui colleront avec les regles du sudoku.
les chiffres que tu places induisent des contraintes pour les autres chiffres a placer.

ton code ne tient pas compte de ces contraintes et génère des grilles SANS solution


Renfield - Admin CodeS-SourceS - MVP Visual Basic & Spécialiste des RegExp
Commenter la réponse de Renfield
Dovah 10 Messages postés jeudi 22 décembre 2011Date d'inscription 23 décembre 2011 Dernière intervention - 22 déc. 2011 à 15:45
0
Merci
je l'ai mis à 9, ça marche, sauf que pour le coup il a vraiment remplit beaucoup de cases ^^

Mais en admettant que j'y arrive et que le code ne mette aucun doublon ( qu'il applique correctement les 3 conditions du sudoku ), à partir de ce moment là il sera solutionnable, avec 1 ou plusieurs solution.
Commenter la réponse de Dovah
Renfield 17308 Messages postés mercredi 2 janvier 2002Date d'inscription 22 août 2018 Dernière intervention - 22 déc. 2011 à 15:49
0
Merci
il a vraiment remplit beaucoup de cases ^^


N'est-il pas censé remplir toute ta grille ?

prend un solveur de sudoku en ligne, par exemple:
www.sudoku-solutions.com/

tu constatera certainement que ta grille n'a pas de solution


partant d'une grille remplie et valide, comme le génère mon code, il s'agit de supprimer un certain nombre de chiffres, de manière a obtenir la grille jouable, étant sur qu'une solution existe.
Je n'ai pas trop réfléchit au sujet, je me suis concentré sur la génération d'une grille complète, étape qui me semble indispensable pour concevoir une grille jouable.


Renfield - Admin CodeS-SourceS - MVP Visual Basic & Spécialiste des RegExp
Commenter la réponse de Renfield
Dovah 10 Messages postés jeudi 22 décembre 2011Date d'inscription 23 décembre 2011 Dernière intervention - 22 déc. 2011 à 15:57
0
Merci
un exemple de ce qu'il m'a fait :


Dans l'état actuellement, oui, ça n'a aucune solution comme y a des doublons.
Pour moi nos méthodes de résolution sont opposés mais doivent arriver au même résultat.
Toi tu trouves une grille complète et valide puis tu enlèves des nombres. Tu pars de la fin en gros. Et au final avec tes 0 en plus, tu n'as aucun doublons.

Moi je pars du début, une grille sans rien où j'essaye de mettre des nombres aléatoires, tout en évitant les doublons dans la ligne, colonne,carré.
Au final ça revient au même que toi, une grille sans doublons avec des trous
Commenter la réponse de Dovah
Dovah 10 Messages postés jeudi 22 décembre 2011Date d'inscription 23 décembre 2011 Dernière intervention - 22 déc. 2011 à 15:59
0
Merci
le lien marche pas bien, déso
voici un lien
Commenter la réponse de Dovah
Renfield 17308 Messages postés mercredi 2 janvier 2002Date d'inscription 22 août 2018 Dernière intervention - 23 déc. 2011 à 06:53
0
Merci
Ce n'est pas qu'une histoire de doublons !

avec n à 9 ta grille devrait etre pleine.
le fait qu'elle ne le soit pas montre la limite de ton systeme.

Je ne suis pas en train de te dire que le tiens n'est pas bon, que mon code l'est.

J'ai bien, je le repete, tenté de faire fonctionner ton code.
Mais mettre un nombre sans avoir de doublon n'est pas une fin en soit.
une grille peut très bien ne pas avoir de solution.

hier, j'ai mis en place une boucle.
En cas d'echec a trouver une grille valide, je recommencais "au petit bonheur la chance", comme tu fais, finalement avec ta boucle :
{
}while((x!=1)&&(y!=1));

Je vais repartir de ton code, générer une grille sans doublon dans les lignes et les colonnes, ni les carrés 3x3

ca te sort des Sudoku sans solution

Renfield - Admin CodeS-SourceS - MVP Visual Basic & Spécialiste des RegExp
Commenter la réponse de Renfield

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.