Problème générateur de grille de sudoku en C

Résolu

Dovah Messages postés 10 Date d'inscription jeudi 22 décembre 2011 Statut Membre Dernière intervention 23 décembre 2011 - 22 déc. 2011 à 00:51
Renfield Messages postés 17287 Date d'inscription mercredi 2 janvier 2002 Statut Modérateur Dernière intervention 27 septembre 2021 - 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.

A voir également:

Sudoku.c
Générateur sudoku - Meilleures réponses
Sudoku c - Meilleures réponses
Générateur sudoku ✓ - Forum C / C++ / C++.NET
Générateur de nombre ✓ - Forum PHP
Generateur de nom de jeu ✓ - Forum Flash
Générateur de lettre ✓ - Forum VB.NET
Générateur de pseudo - Forum Visual Basic

23 réponses

Réponse 21 / 23

Renfield Messages postés 17287 Date d'inscription mercredi 2 janvier 2002 Statut Modérateur Dernière intervention 27 septembre 2021 74
23 déc. 2011 à 07:50

Je viens de travailler ton code pour lui faire chasser les doublons.

il m'a généré :

257|891|346
839|645|271
164|273|859
---+---+---
978|56.|432<
34.|129|685<
612|438|.97<
---+---+---
491|.87|563<
725|3.6|914<
..3|914|728<

pas de doublon dans les lignes, colonnes, carré.
6 lignes n'ont pas trouvé de solution de remplissage permettant de ne pas générer de doublon. Pourtant, mon code tente 100 millions de fois chaque ligne en cas de blocage !

Pas de doublon, ok, objectif atteint ?
non, cette grille n'a aucune solution en SUDOKU...

OK, j'ai tenté de généré une grille complète, bla bla bla...
tentons ton exercice, à savoir :
générer une grille sans doublon.
je remet
n = rand()%7;

j'obtiens :

...|...|...
.2.|.49|851
..3|.1.|.62
---+---+---
4.9|.62|...
.7.|...|5.3
.58|...|97.
---+---+---
.6.|...|...
...|...|...
.1.|..8|...

cette grille est bien VALIDE (Rating: Hard)

je tente en fixant un seuil minimum à n:
n = 2 + rand()%6;
au moins deux nombres remplis par ligne, 7 au maximum.

j'obtiens une grille sans solution :

4 |9 |
| 6|7 3
563|27 | 1
---+---+---
62 | 7| 4
1 | 8| 2
7| 5|
---+---+---
31|592| 4
8 |1 4|
9 | 3 |571

J'ai repris la structure de mon code.
tu as juste a modifier fillGrid :

void fillGrid(int tab[9][9], int) {
int n, alea, i, x, y;
unsigned int nTries;

for(y=0; y<9; y++) {
nTries = 0;
n=2+rand()%6;   //nombre de chiffres à mettre
//n = 9; // Normallement, une grille pleine
while (n-- > 0) {
NewTry:
if (nTries++ == 100000000) {
printf("Evite les boucles infinies... Cent millions d'essais c'est beaucoup...\n");
break; // On saute cette ligne
}
alea = rand()%9 + 1;

// Pas de doublon dans la ligne courante
for (i=0; i<9; i++) 
if (tab[y][i] == alea) // la valeur est déjà présente ? on refait un tour de boucle
goto NewTry;

// on fixe la case ciblée. On cherche pour cela une case aléatoire vide sur la ligne y
do
x=rand()%9;    
while (tab[y][x]);

// Pas de doublon dans la colonne de la case ciblée
for (i=0; i<9; i++)
if (tab[i][x] == alea) // la valeur est déjà présente ? on refait un tour de boucle
goto NewTry;

// enfin, on evite les doublons dans les carrés 3x3
for (i=0; i<9; i++)
if (tab[(y/3)*3+(i/3)][(x/3)*3+(i%3)] == alea) // Une case du carré 3x3 a déjà la valeur alea ?
goto NewTry;  // nouvel essai...

nTries = 0; // On a trouvé un chiffre, on remet a 0 le compteur d'essais
            tab[y][x] = alea;
        }
    }
}

Cela génère des Sudoku sans doublon.
valide parfois. pas toujours.

Renfield - Admin CodeS-SourceS - MVP Visual Basic & Spécialiste des RegExp

Réponse 22 / 23

Dovah Messages postés 10 Date d'inscription jeudi 22 décembre 2011 Statut Membre Dernière intervention 23 décembre 2011
23 déc. 2011 à 15:46

Refaire la case plutôt que toute la ligne, moins lourd et plus malin.
Trop hasardeux toute la ligne, surement un problème de limite de conditions pour la boucle.
Merci

Réponse 23 / 23

Renfield Messages postés 17287 Date d'inscription mercredi 2 janvier 2002 Statut Modérateur Dernière intervention 27 septembre 2021 74
23 déc. 2011 à 15:51

Cette approche a l'avantage de ne pas etre recursive (forte consommation mémoire sur la pile)
Elle est cependant imparfaite...

Renfield - Admin CodeS-SourceS - MVP Visual Basic & Spécialiste des RegExp

Discussions similaires

Calculer une checksum sur 8 bits

Structure date c

Inverser une chaîne de caractères langage c+

Extraction d'une sous-chaîne de caractère dans une sous chaîne en C

Suppression d'occurences dans un tableau

projet c:gestion d'une bibliotheque

Votre réponse

Discussions similaires