Probleme avec un Sudoku

**kev484** · 03/03/2008, 17h40

Bonjour,
Voila j'ai un sudoku a creer et dès le début je bloque. Mes connaissances en C sont moyennes dira t-on... Donc voila j'ai reussi a créer mon tableau de 9 cases sur 9 et mon probleme arrive des que je dois remplir aléatoirement mon tableau. Donc voila ce que j'ai fait :

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
#include <stdio.h>
#define N 9
#define OUI 1
#define NON 0
 
void afficherGrille(int S[N][N]);
int main(){
    int grille[N][N];
    afficherGrille(grille);
}
 
void afficherGrille(int S[N][N]){
    int indiceColonne;
    int indiceLigne;
    int entier;
    entier = (srand()%N);
    printf("-------------");
    for(indiceLigne = 0 ; indiceLigne < N ; indiceLigne++){
        if((indiceLigne) == 3 ){
            printf("\n --- --- --- ",S[indiceLigne][indiceColonne]);
        }else if((indiceLigne) == 6){
            printf("\n --- --- --- ",S[indiceLigne][indiceColonne]);
        }
        printf("\n");
        for(indiceColonne = 0 ; indiceColonne < N ; indiceColonne++){
            if((indiceColonne%3) == 0){
                printf("|%d",entier,S[indiceLigne][indiceColonne]);
            }else if((indiceColonne) == 8){
                printf("%d|",entier,S[indiceLigne][indiceColonne]);
            }else{
                printf("%d",entier,S[indiceLigne][indiceColonne]);
            }
 
        }
    }
}

Cependant mon entier retourné est toujours le meme. Donc je ne sais pas si il faut creer une fonction a part pour remplir mes cases ou s'il faut faire comme je fais?
Merci

**diogene** · 03/03/2008, 18h08

Code :

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

    entier = (srand()%N);

Le générateur de nombres aléatoires ne fonctionne pas comme ça
srand() initialise le générateur : à utiliser une seule fois au début du programme
utiliser ensuite rand() pour obtenir les nombres aléatoires à chaque fois qu'on en veut un nouveau

**kev484** · 03/03/2008, 18h10

Donc comment faire? Desolé mais je ne comprends pas trop. Enfin j'ai compris qu'il faut utiliser rand() apres avoir initialiser grace a srand() mais je ne vois pas quel parametre prendre.

**diogene** · 03/03/2008, 18h16

typiquement

Code :

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

1
2
3
4
5
6
int main(void)
{
...
   srand((unsigned) time(NULL))
...
  i = rand(); // donne un nombre aléatoire entre 0 et RAND_MAX

**Thierry Chappuis** · 03/03/2008, 18h20

Envoyé par kev484

Donc comment faire? Desolé mais je ne comprends pas trop. Enfin j'ai compris qu'il faut utiliser rand() apres avoir initialiser grace a srand() mais je ne vois pas quel parametre prendre.

Pour générer un nombre pseudo-aléatoire entre 0 et un entier N, tu dois:

Initialiser ton générateur en appelant srand() au début de ton programme (généralement, on appelle cette fonction une fois au début de la fonction main()).
Utiliser une des solutions proposées dans la FAQ C: http://c.developpez.com/faq/?page=no..._random_bornes

Et le tour est joué! Bonne chance

Thierry

**kev484** · 03/03/2008, 18h33

Ok donc a chaque fois que je lance mon programme j'ai bien un nombre aléatoire créé mais maintenant je souhaiterai que dans chaque case , il soit différent. Voila mes modifs :

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
#include <stdio.h>
#define N 9
#define OUI 1
#define NON 0
 
void afficherGrille(int S[N][N]);
int main(){
    int grille[N][N];
    srand((int)time(NULL));
    afficherGrille(grille);
}
 
void afficherGrille(int S[N][N]){
    int indiceColonne;
    int indiceLigne;
    int entier;
    entier = rand()%N+1;
    printf("-------------");
    for(indiceLigne = 0 ; indiceLigne < N ; indiceLigne++){
        if((indiceLigne) == 3 ){
            printf("\n --- --- --- ",S[indiceLigne][indiceColonne]);
        }else if((indiceLigne) == 6){
            printf("\n --- --- --- ",S[indiceLigne][indiceColonne]);
        }
        printf("\n");
        for(indiceColonne = 0 ; indiceColonne < N ; indiceColonne++){
            if((indiceColonne%3) == 0){
                printf("|%d",entier,S[indiceLigne][indiceColonne]);
            }else if((indiceColonne) == 8){
                printf("%d|",entier,S[indiceLigne][indiceColonne]);
            }else{
                printf("%d",entier,S[indiceLigne][indiceColonne]);
            }
 
        }
    }
}

Dois-je creer une procédure qui permet de mettre un chiffre aléatoire dans chaque case ou puis-je le faire directement dans ma fonction permettant d'afficher ma grille?

**Thierry Chappuis** · 03/03/2008, 20h06

Pour tirer aléatoirement n nombres parmi N, sans répétition, la méthode que j'utilise est de prendre un tableau de taille N contenant les nombres en question, de le mélanger (shuffle), puis de prendre les n premiers nombres du tableau mélangé.

Voici un exemple:

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
70
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define ARRAY_SIZE(arr) ( sizeof (arr) / sizeof *(arr) )
 
/* -tc- Voir: http://c.developpez.com/faq/?page=nombres#NOMBRES_random_bornes */
int alea(int n)
{
   int partSize   = (n == RAND_MAX) ? 1 : 1 + (RAND_MAX - n)/(n+1);
   int maxUsefull = partSize * n + (partSize-1);
   int draw;
 
   do
   {
      draw = rand();
   } while (draw > maxUsefull);
   return draw/partSize;
}
 
/* -tc- Utilise l'algorithme de Fisher & Yates */
int shuffle(int *a, size_t size_a)
{
    int err = 0;
 
    if (a != NULL && size_a > 1)
    {
        size_t n = size_a;
 
        while (--n > 0)
        {
            /* -tc- k est un entier aleatoire entre 0 et n */
            size_t k = alea(n);
 
            if (k != n)
            {
                /* -tc- On echange le k-eme et le n-eme element */
                int tmp = a[n];
                a[n] = a[k];
                a[k] = tmp;
            }
        }
    }
    else
    {
        /* Erreur: argument invalide */
        err = 1;
    }
    return err;
}
 
/* -tc- Dans ce programme, on desire afficher aleatoirement 5 nombres parmi
   l'ensemble {0,1,2,3,4,5,6,7,8,9} sans repetition */
int main(void)
{
    int nombres[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    size_t n = 5;
    size_t i;
 
    srand(time(NULL));
    shuffle(nombres, ARRAY_SIZE(nombres));
 
    for (i = 0; i < ARRAY_SIZE(nombres) && i < n; i++)
    {
        printf("%d ", nombres[i]);
    }
    printf("\n");
 
    return 0;
}

Thierry

**kev484** · 04/03/2008, 15h33

Merci pour votre code mais, on doit utiliser que les trucs vus en cours et nous n'avons pas vu les pointeurs et toutes les fonctions tel que suffle.
Donc j'ai reussi a faire cela :

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
#include <stdio.h>
#define N 9
#define OUI 1
#define NON 0
 
void remplirGrille(int S[N][N]);
void afficherGrille(int S[N][N]);
int main(){
    int grille[N][N];
    srand((int)time(NULL));
    remplirGrille(grille);
    afficherGrille(grille);
    return 0;
}
 
void afficherGrille(int S[N][N]){
    int indiceColonne;
    int indiceLigne;
    printf("-------------");
    for(indiceLigne = 0 ; indiceLigne < N ; indiceLigne++){
        if((indiceLigne) == 3 ){
            printf("\n --- --- --- ",S[indiceLigne][indiceColonne]);
        }else if((indiceLigne) == 6){
            printf("\n --- --- --- ",S[indiceLigne][indiceColonne]);
        }
        printf("\n");
        for(indiceColonne = 0 ; indiceColonne < N ; indiceColonne++){
            if((indiceColonne%3) == 0){
                printf("|%d",S[indiceLigne][indiceColonne]);
            }else if((indiceColonne) == 8){
                printf("%d|",S[indiceLigne][indiceColonne]);
            }else{
                printf("%d",S[indiceLigne][indiceColonne]);
            }
 
        }
    }
}
 
void remplirGrille(int S[N][N]){
    int indiceLigne;
    int indiceColonne;
    for(indiceLigne = 0; indiceLigne < N ; indiceLigne = indiceLigne + 1){
        for(indiceColonne = 0 ; indiceColonne < N ; indiceColonne = indiceColonne + 1){
        S[indiceLigne][indiceColonne] = rand() % 10;
        }
    }
}

Mais maintenant, il nous demande :

Proposez une fonction renvoyant VRAI si un entier entre 1 et N est deja present sur une ligne i et FAUX sinon. VRAI et FAUX sont deux constantes entieres a definir.

Donc pour cela j'ai declaré au debut les booléens mais je voulais savoir si vaut mieux creer une aurte fonction pour verifier si le nombre est deja pesent ou vaut mieux que je le fasse directement dans ma fonction : remplirGrille?
Merci de la réponse.

**Thierry Chappuis** · 04/03/2008, 15h54

Et le paramètre S de tes fonctions remplirGrille() et afficherGrille(), c'est pas un pointeur? Si tu préfères, le prototye de ma fonction shuffle() peut s'écrire de manière strictement équivalente:

Code :

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

int shuffle(int *a, size_t size_a);

ou

Code :

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

int shuffle(int a[], size_t size_a);

Thierry

**kev484** · 04/03/2008, 15h58

A desolé je ne savais pas que c'etait un pointeur le prof nous avait dit de le mettre tout le temps sans prendre le temps de nous expliquer ce que c'etait.
Mais sinon ce que j'ai fait marche donc je peux le garder non? Car le prof souhaite que l'on creer des fonctions pour chaque application a faire.
Et j'ai une autre petite question : sachant que je met :

Code :

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

srand((int)time(NULL));

. Je suis obliger de mettre un :

Code :

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

#include <time.h>

?

**Arnaud F.** · 04/03/2008, 16h14

Bonjour,

La commande suivante (sous une console Linux)

Code :

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

$ man 2 time

Renvoi la chose suivante :

NOM
time - Lire l’heure

SYNOPSIS
#include <time.h>

time_t time(time_t *t);

Donc oui, tu dois l'inclure car la fonction time est déclarée dans time.h

++

**kev484** · 04/03/2008, 16h21

Ok merci. Et je suis sous windows.
Je vais essayer de résumer ce que j'ai compris pour la fonction demandée par le prof. Il souhaite que je creer une fonction me permettant de verifier si un chiffre est deja sur ma ligne. De plus si celui si est présent alors je renvoie VRAI sinon je renvoie FAUX. Donc si c'est vrai je n'insere pas ce chiffre dans mon tableau et si c'est faux je l'insere. Donc je devrais faire appel a cette fonction dans ma fonction pour remplirGrille() non?
Desolé mais j'ai un peu de soucis de compréhension.

**Thierry Chappuis** · 04/03/2008, 16h51

Envoyé par kev484

Ok merci. Et je suis sous windows.
Mais le soucis que j'ai c'est que, en cours on a vu comment verifier si un nombre etait deja present mais dans un tableau a une dimension. Comment faire avec deux dimensions? Dois-je considerer que mes lignes au debut vu la fonction demandée par le prof?

Il suffit de parcourir le tableau dans les deux dimensions:

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
#include <stdio.h>
 
#define N_LIGS 3
#define N_COLS 4
#define CIBLE 77
 
int contient_cible(int matrice[][N_COLS], size_t n_ligs, int cible)
{
    int ret = 0;
 
    if (matrice != NULL && n_ligs > 0)
    {
        int i, j;
 
        for (i = 0; ret == 0 && i < n_ligs; i++)
        {
            for (j = 0; ret == 0 && j < N_COLS; j++)
            {
                if (matrice[i][j] == cible)
                {
                    ret = 1;
                }
            }
        }
    }
 
    return ret;
}
 
int main(void)
{
    int matrice[N_LIGS][N_COLS] = {{0}};
 
    matrice[2][3] = CIBLE;
 
    if (contient_cible(matrice, N_LIGS, CIBLE) == 1)
    {
        printf("matrice contient le nombre %d\n", CIBLE);
    }
    else
    {
        printf("matrice ne contient PAS le nombre %d\n", CIBLE);
    }
 
    return 0;
}

Thierry

**kev484** · 04/03/2008, 17h34

Donc apres plusieurs essaies de différentes manieres, j'ai essayer cela mais ça ne marche toujours pas et je ne comprends pas :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
int verifLigne(int S[N][N]){
    int i;
    int j;
    for(i = 1; i <= N ; i = i+1 ){
        for(j = 1; j <= N ; j = j+1){
            if(S[i][j] == S[i+1][j]){
                return 1;
            }
        }
    }
    return 0;
}

Et donc dans ma fonction remplirGrille() :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
void remplirGrille(int S[N][N]){
    int indiceLigne;
    int indiceColonne;
    int entier;
    for(indiceLigne = 0 ; indiceLigne < N ; indiceLigne = indiceLigne + 1){
        for(indiceColonne = 0 ; indiceColonne < N ; indiceColonne = indiceColonne + 1){
        S[indiceLigne][indiceColonne] = verifLigne(S[N][N]);
        S[indiceLigne][indiceColonne] = (rand() % 9)+1;
 
        }
    }
}

Peut etre que cela vient de sa : S[indiceLigne][indiceColonne] = verifLigne(S[N][N]);
J'explique ce que j'ai voulu faire. Je voulais parcourir mon tableau et que, si le chiffre dans une case etait present dans une case alors je retourne vrai et je ne le renote pas.
Merci encore de l'aide.

**snake264** · 04/03/2008, 18h04

Ta fonction verifLigne() ne vérifie pas si un nombre est bien dans une ligne mais plutot si il y a une occurence dans ton tableau d'une façon bizarre d'ailleurs à tu vérifier si elle faisait ce que tu voulais ?
Ensuite dans ta fonction remplirGrille() tu ne regarde même pas si ta fonction
verifLigne() te renvoi 0 ou 1 et ta vérification est mauvaise essai verifLigne(S) et l'affectation S[indiceLigne][indiceColonne] = verifLigne(S[N][N]); ce qui signifi que tu lui donne la valeur renvoyer par ta fonction verifLigne(), soit 0 ou 1, je ne pense pas que sa soit ce que tu veuille.

**diogene** · 04/03/2008, 18h08

Peut etre que cela vient de sa :

Code :

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

 S[indiceLigne][indiceColonne] = verifLigne(S[N][N]);

Cette ligne est effectivement erronée.
En écrivant cela, tu passe, non pas le tableau, mais l'élément d'indices N,N qui en plus n'appartient pas au tableau, les indices commençant à 0 et s'arrêtant à N-1. A ce sujet, tu as une erreur sur les bornes des for dans la fonction verifLigne :

Code :

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

1
2
    for(i = 0; i <N ; i = i+1 ){
        for(j = 0; j <N ; j = j+1)

Le compilateur a du te mettre un warning parce que tu appelais une fonction qui attend un pointeur avec un int comme paramètre.
Si tu passes outre au warning, tu vas planter à l'exécution (il prendra le contenu S[N][N], qui est n'importe quoi, comme l'adresse du tableau qu'il attend)

Passe donc l'adresse du début du tableau :

Code :

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

S[indiceLigne][indiceColonne] = verifLigne(S);

**kev484** · 04/03/2008, 18h08

Comment faire alors pour voir si un chiffre est deja dans ma ligne car le prof nous avais dit de faire comme cela. Ca fait une heure que je cherche et je suis bloqué...

**diogene** · 04/03/2008, 18h21

Proposez une fonction renvoyant VRAI si un entier entre 1 et N est deja present sur une ligne i et FAUX sinon. VRAI et FAUX sont deux constantes entieres a definir.

il faut spécifier
- Le tableau concerné
- la ligne à explorer
- l'entier à chercher

Code :

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

1
2
3
4
5
6
7
int verifLigne(int S[][N], int ligne, int entier)
{
  int i;
  for(i=0; i<N;i++)
    if(S[ligne][i] == entier) return VRAI;
  return FAUX;
}

A moins (l'énoncé est un peu ambigu) qu'on cherche si un entier quelconque entre 1 et 9 est sur la ligne (mais pour ce problème, je ne pense pas que ce soit le cas)

Code :

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

1
2
3
4
5
6
7
int verifLigne(int S[][N], int ligne)
{
  int i;
  for(i=0; i<N;i++)
    if(S[ligne][i] >=1 &&  S[ligne][i]<=9) return VRAI;
  return FAUX;
}

C'est bizarre qu'il ne te pose pas aussi la même question pour les colonnes

**kev484** · 04/03/2008, 18h26

Merci pour cette fonction je pense qu'elle ira. Et si la question d'apres est la meme mais sur les colonnes... Donc je pense qu'il faudra utiliser le meme principe non? Et donc par rapport a votre fonction, ensuite dans remplirGrille() je dois mettre si c'est vrai alors je ne fais rien et si c'est faut alors je met mon chiffre c'est ça?

**diogene** · 04/03/2008, 18h33

Je tire au hasard un nombre entre 1 et 9. Je vérifie qu'il n'est pas déjà sur la ligne ni sur la colonne (ni dans le même bloc de 3x3, fonction de test à écrire). Si c'est le cas je peux le mettre dans la case.

Probleme avec un Sudoku

C

Discussions similaires

Partager

Partager