Case "voisine" Sudoku, parcours du tableau... en C

Solutionneur de sudoku, projet DUT

Le problème exposé dans ce sujet a été résolu.

Salut,

J’ai pour projet en C pour ma première année de DUT de créer un solutionneur de Sudoku pendant les vacances. Je vous envoie le sujet pour savoir en détail ce que je dois faire si ça vous intéresse…

https://www.mediafire.com/file/ma8k8zzl5ta088a/C_A1_sudoku_18_19.pdf/file

Puis tout mon code actuel avant de passer à ma demande :

Main.c (programme principal qui s’occupe d’exécuter chaque fonctions)

#include <stdio.h>
#include <stdlib.h>
#include "sudoku.h"

int main(void) {
  int G[9][9] = {{0},{0}}; // Tableau contenant la grille
  Cand C[9][9]; // Tableau contenant les candidats de chaque case de la grille
  int NBO;
  Case O[81];

  lireGrille(G, "grille.txt");
  ecrireGrille(G);
  // initJeu(G, C, O, NBO);
  estCand(G);

  return 0;
}

sudoFunct.c (qui contient toutes les fonctions du programme)

#include <stdio.h>
#include <stdlib.h>
#include "sudoku.h"

/* SUPPRESION DE liregrille() et ecriregrille() POUR EVITER LE COPIAGE ET L'ANTIPLAGIAT */

/* void initJeu(int G[9][9], Cand C[9][9], Case O[81], int NBO) {
  int i, j, k = 0;
  int t;

  for (i = 0; i < 9; i++) {
    for (j = 0; j < 9; j++) {
      /* Initialisation de C[9][9]
      if(G[i][j] != 0) {
        C[i][j].nbc = 0;
        C[i][j].tab = NULL;
      }
      else {
        C[i][j].nbc = 9;

        O[i].x = i;
        O[j].y = j;
      }

      // printf("%d\n", C[i][j]); 
    }
  }
} */

/* Suppression de estCand() pour éviter le copiage + éviter anti-plagiat */

struct.h (qui contient les deux structures utilisés)

typedef struct {
  int x; // numéro de ligne
  int y; // numéro de colonne
} Case;

typedef struct {
  int nbc; // nombre de candidats
  int *tab; // table des candidats
} Cand;

Voilà, maintenant je vous explique mon problème. J’essaye de faire fonctionner la fonction estCand qui me permettra de tester les nombres candidats qui seront dans une case (i, j) de ma grille de sudoku. Mais pour ça, je dois connaître les voisins qui doivent être différent du nombre pour lequel je cherche. En gros, que le nombre ne soit pas le même qu’un nombre en horizontale et en vertical à partir de la case, et ne soit pas non plus le même dans le groupe de cases.

Image pour que ce soit plus clair :

http://prntscr.com/m0d3rz

En gros, la case que j’ai entouré en carré ne doit pas être pareil que la flèche à l’horizontale, à la vertical, et de ce que j’ai entouré. Après, je vous invite à lire le sujet si vous voulez, c’est + clair :) ! Or, je n’ai aucune idée de comment faire pour savoir ça, j’y ait réfléchis 3 heures et fait plusieurs essais, mais je ne sais pas du tout comment faire…

Bref, merci de votre aide, j’suis grave bloqué là !

+0 -0

Bonsoir,

Tu pars de la case (i, j) et tu cherches à accéder aux cases voisines (case sur la ligne, sur la colonne, ou dans son "carré"). Si on considère que les cases sont numérotés de 0 à 8. Si i est le numéro de ligne et j le numéro de colonne tu veux accéder aux cases suivante :

  • Les cases qui ont la même ligne mais une colonne différente, ce sont les (i, y) où y va de 0 à 8.
  • Les cases qui ont la même colonne mais une ligne différente, ce sont les (x, j) où x va de 0 à 8.
  • Les cases qui sont dans le même carré 3*3, ce sont les (x, y) tels que x va de floor(i/3) à floor(i/3) + 2 et y va de floor(i/3) à floor(i/3) + 2.

Ces cases correspondent aux cases voisines de la case (i, j).

Par contre attention avec ta fonction estCand, d’après l’énoncé estCand est : "une fonction qui indique si un chiffre donné est candidat pour une case ouverte". La signature de estCand va donc probablement ressemblé à quelque chose comme ça : int estCand(int G[9][9], Case case_ouverte, int candidat) et le but est de tester si candidat est un candidat pour case_ouverte (en regardant si la valeur d’une des cases voisines de case_ouverte a pour valeur candidat ou non).

Après quoi, selon si candidat est un candidat valable pour case_ouverte la fonction retourne 0 ou 1 (et tu essaies d’ajouter un peu de documentation pour que cela soit clair lorsque tes camarades utilisent ta fonction).

+1 -0

Il me semble, si j’ai bien tout lu, que ta fonction estCand se résume à chercher si un nombre donné appartient ou non à un emsemble (ici ton ensemble de cases voisines, lignes et colonnes ).

Déjà, je vois que tu ne donnes à ta fonction que le sudoku en argument, ne faudrait il pas donner le nombre à tester aussi ?

Ensuite pour ce qui est de ta fonction actuelle, à vue de nez elle doit afficher Cand pour chaque case ouverte de ta grille ce qui n’est pas le comportement voulu.

Je te conseillerais de faire une fonction suivant déjà un prototype comme :

Booléen estCandidat(nombre à tester n ,Grille G, Case C) :
renvoie vrai si n est candidat pour C dans G,faux sinon.

Ensuite le corps de ta fonction peut se ramener à trois sous fonctions : 1. Tester si n est présent dans une autre case de la ligne (je te laisse chercher comment trouver toutes les autres cases de la ligne connaissant la coordonnée de C ) 2. Tester si n est présent dans une autre case de la colonne (je te laisse chercher comment trouver toutes les autres cases de la colonne connaissant la coordonnée de C ) 3. La plus "dure" trouver si n est présent dans les autres cases entourant C.

Si n n’est présent nulle part il est candidat, sinon non.

Pour la derniere fonction tu vas devor faire attention à ne tester que des cases existantes, pour ça soit tu hardcodes des limites de coordonnées dans les test, soit tu ajoutes des cases virtuelles tout autour de ta grille initialisées à une valeur non représentative.

Voilà en espérant que ça t’aides un peu !

Edit : grillé par jozifloqui t’as donné les réponses !

+1 -0

Salut,

Merci de vos réponses, ça m’a pas mal aidé à comprendre ! Du coup, j’ai travaillé un peu là dessus, mais j’ai (évidemment) quelques problèmes !

void initJeu(int G[9][9], Cand C[9][9], Case O[81], int NBO) {
  int i, j, k = 0;
  int ouverte;
  Case case_ouverte;

  for (i = 0; i < 9; i++) {
    for (j = 0; j < 9; j++) {
      /* Initialisation de C[9][9] */
      ouverte = G[i][j] == 0;

      if(!ouverte) {
        C[i][j].nbc = 0;
        C[i][j].tab = NULL;
      }
      else {
        if(estCand(G, case_ouverte, G[i][j]) == 1) {
          C[i][j].nbc++;
          C[i][j].tab = &G[i][j];
        }
      }
    }
  }

  for(i = 0; i < 9; i++) { // print de test pour vérifier les valeurs du tableau tab
    for(j = 0; j < 9; j++) {
      printf("%d ", C[i][j].tab);
    }
  }
}

/* Suppresion du estCand pour éviter anti-plagiat + recopiage */

Je n’ai pas vérifier les cases qui sont dans le même carré car je n’ai pas trop réussit, j’ai pas bien compris comment ça fonctionne avec la fonction floor, etc. Du coup, pour tester j’ai quand même utiliser le horizontal et le vertical. A priori ça me donnait de bons résultats, donc j’ai terminé la fonction avec des return et enlevé les print de test pour la tester dans initJeu.

J’ai donc printé mon tableau tab qui est censé me donner la liste des candidats. Je crois que j’ai pas bien compris comment fonctionne cette histoire de pointeur, lorsque je fais : C[i][j].tab = G[i][j]; je reçois un avertissement qui me dit que c’est pas le même type et qu’il faut caster. Pourtant tab est un entier… et G[i][j] aussi.

Avec le code que j’ai donné, il me print l’adresse des variables, j’aimerais bien qu’il me print les valeurs qui ont été mises dans *tab.

http://prntscr.com/m0mgpa

+0 -0

Bonjour,

Essaie d’écrire entièrement ta fonction estCand (et qu’elle fonctionne) avant de faire la fonction initJeu. Actuellement ta fonction considère que toute cadeau du sudoku est une case voisine.

La fonction edtCand n’est pas correcte actuellement, notamment les lignes 36 et 46 essaie de comprendre pourquoi et de l’expliquer. Essaie également de coder les tests pour les cases voisines dans le même "carré" en utilisant un exemple à la main (floor c’est l’arrondi inférieur pour un nombre à virgule floor(1.4) est égal à 1 par exemple).

Je reste évasif car ça sert à rien que je te donne trop d’informations sinon ça te mâche trop le travail. On repassera par le sujet pour t’aider mais fait petit bout par petit bout (et test ta fonction estCand sur une grille pour voir si elle retourne bien les résultats attendus). Je reviens plus tard pour te donner d’autres pistes si il faut.

+0 -0

Ok, j’ai donc repris le tout et recommencer ma fonction estCand. Après quelques recherches j’ai enfin réussit à faire cette fonction qui après quelques tests donne de bons résultats.

J’ai donc recommencé "initJeu", qui à priori fonctionne, le soucis c’est que je n’arrive pas à stocker les nombres candidats dans "Cand *tab" (la structure Cand). Le code que j’ai actuellement me renvoie le nombre de candidats possible et non pas les candidats possibles.

J’ai besoin d’aide pour comprendre comment stocker ses valeurs dans le pointeur *tab qui est un tableau un peu bizzare… (Mais qu’on est obligé d’utiliser :/)

/* Suppresion du estCand() pour éviter anti-plagiat + recopiage */

void initJeu(int G[9][9], Cand C[9][9], Case O[81], int NBO) {
  int i, j, k = 0, l = 0;
  int ouverte;

  for (i = 0; i < 9; i++) {
    for (j = 0; j < 9; j++) {
      /* Initialisation de C[9][9] */
      ouverte = G[i][j] == 0;

      if(!ouverte) {
        C[i][j].nbc = 0;
        C[i][j].tab = NULL;
      }
      else {
        for(k = 1; k < 9; k++) {
          if(estCand(G, k, i, j)) {
            C[i][j].nbc++; // Incrémentation du nombre de valeurs possible pour une case
            C[i][j].tab = (int*)k; // Stockage des valeurs possible pour une case
          }
        }
      }
    }
  }

  for(i = 0; i < 9; i++) { // Affichage test de C[i][j]
    for(j = 0; j < 9; j++) {
      printf("%d ", C[i][j].tab);
    }
    printf("\n");
  }
}

J’ai donc un truc comme ça, je dois pas bien comprendre cette histoire de tableau qui sont des pointeurs. J’ai pas utilisé floor, mais le modulo du coup, j’ai trouvé ça sur OCR, j’ai compris comment ça fonctionnait, maintenant que j’y pense c’est logique. Donc si y’a des trucs qui vont pas, dites moi :) !

+0 -0

Salut,

Ta fonction estCand marche correctement maintenant. As-tu compris les erreurs que tu faisais dans l’implémentation précédente ? Plutôt que d’utiliser les variables i et j pour la ligne et colonne, il serait mieux d’utiliser la structure Case puis d’accéder au numéro de la ligne ou au numéro de la colonne dans la fonction estCand (lorsque l’on regarde le sujet donné par ton professeur c’est ce qu’il semble attendre comme paramètre de ta fonction) puis d’accéder aux attribut x et y.

Pour l’attribut tab de Cand je pense qu’une relecture du chapitre sur les pointeurs en C peut t’être utile.

D’après le sujet de ton professeur, Cand contient deux champs :

  • int nbc, le nombre de candidats
  • int *tab, une table d’entiers (géré de façon dynamique) pour mémoriser les candidats d’une case

Comment comprends-tu cela et qu’essaies tu de faire aux lignes 64 et 65 de ton code actuellement ? Pourquoi as-tu besoin de int nbc et qu’est ce que tu dois stocker dans int * tab ? Qu’est ce qu’il doit y avoir dans C[0][0] une fois que initJeu l’a initialisé ?

+0 -0

Dans l’implémentation précédente, je parcourais tout le tableau à chaque fois, donc il cherchait dans tout le tableau le "candidat".

Pour la structure Case, en gros je remplace tout les int i et int j par un Case… Je trouve que ça complique bien les choses, mais je me suis aussi demandé si je devais pas l’utiliser. Du coup ça donne ça :

/* Suppresion du estCand pour éviter anti-plagiat + recopiage */

Donc, il faut faire ça dans TOUT le programme d’après toi, remplacer tout les i, j, par la structure Case ?

En effet, il faudrait que je re-lise la partie sur les pointeurs, j’ai un mal fou à comprendre, surtout que là c’est un pointeur dans une structure, c’est plutôt perturbant.

A la ligne 64, j’incrémente le compteur nbc de la structure C[][] quand la fonction estCand me renvoie true (donc quand la fonction a trouvé un nombre candidat).
A la ligne 65, je souhaite mettre ce nombre dans le tableau-pointeur *tab de la structure C[][], et c’est bien là que sa coince.
Je vais relire un peu mieux le chapitre sur les pointeurs et me renseignerez pour tester d’autres choses du coup…

Pourquoi as-tu besoin de int nbc et qu’est ce que tu dois stocker dans int * tab ?

  • int nbc, j’en ai besoin pour stocker le nombre de candidat possible pour ensuite je pense savoir quand est-ce qu’il y a un candidat unique ?
  • Et dans int tab, comme je l’ai dit plus haut, je dois stocker la liste des candidats justement, jusque là je comprend

Qu’est ce qu’il doit y avoir dans C[0][0] une fois que initJeu l’a initialisé ?

Il doit y avoir pour chaque "case de la grille" aux coordonnées C(i,j) le nombre de candidat possible si la case est ouverte, 0 si fermé. Et pour *tab, il doit y avoir la liste de ses candidats.

En me posant toutes ses questions, tu m’as fait comprendre pas mal de truc en fin de compte. Merci ^^ !

Bref, je vais re-travailler sur la notion de pointeur et je reviens en cas de problème ou de conseils, merci !

+0 -0

Pour la structure Case, en gros je remplace tout les int i et int j par un Case… Je trouve que ça complique bien les choses, mais je me suis aussi demandé si je devais pas l’utiliser.

Je pense que ton professeur veut que tu l’utilise car tu dois également remplir NBO et O dans la fonction initJeu même si ça peut paraître plus lourd. Une autre option peut être d’utiliser i et j et d’affecter les valeurs à coord.x et coord.y avant l’appel à estCand mais il faudra à un moment ou un autre utiliser la structure Case pour remplir le tableau O.

En effet, il faudrait que je re-lise la partie sur les pointeurs, j’ai un mal fou à comprendre, surtout que là c’est un pointeur dans une structure, c’est plutôt perturbant.

Il ne faut pas avoir peur du pointeur dans la structure ça ne change pas grand chose.

A la ligne 64, j’incrémente le compteur nbc de la structure C[][] quand la fonction estCand me renvoie true (donc quand la fonction a trouvé un nombre candidat).
A la ligne 65, je souhaite mettre ce nombre dans le tableau-pointeur *tab de la structure C[][], et c’est bien là que sa coince.
Je vais relire un peu mieux le chapitre sur les pointeurs et me renseignerez pour tester d’autres choses du coup…

Tu sembles avoir compris ce que tu devais faire avec la structure Cand mais tu as du mal à utiliser le pointeur.

Ce que tu fais actuellement :

C[coord.x][coord.y].tab = (int*)k; // Stockage des valeurs possible pour une case (Fonctionne qu'a moitié)

Que fais cette ligne pour toi ? Pourquoi ce n’est pas ce que tu veux ou pourquoi est-ce ce que tu veux ? Est-ce que tu fais de l’allocation dynamique comme en parle le sujet ou pas (d’ailleurs c’est quoi l’allocation dynamique ?) ? Qu’est ce qu’il se passe actuellement avers la case (0, 0) de l’exemple https://prnt.sc/m0d3rz.

Éléments de réponses (après y avoir réfléchi) :

Actuellement à C[coord.x][coord.y].tab tu affectes la valeur k (donc une adresse entre 1 et 9).

Dans le cas de la case (0, 0) de cet exemple : https://prnt.sc/m0d3rz, estCand(G, k, coord) va renvoyer 1 si k a la valeur 5 ; 6 ou 9.

Le code va donc réaliser les affectations suivantes :

C[0][0].tab = 5

C[0][0].tab = 6

C[0][0].tab = 9

À la fin la valeur stockée sera 9 (alors que tu veux un tableau qui contient [5, 6, 9]). Ça ne marche pas car ton utilisation du pointeur n’est pas correcte dès le début, il te faut allouer un tableau avec l’allocation dynamique

PS : Hésite pas à répondre directement à mes questions sans changer ton code, dans ton dernier message tu as juste changer les i et j par coord.x et coord.y et on peut plus facilement avoir des échanges rapides.

J’ai pas l’habitude de faire des réponses didactiques et j’essaie de te diriger vers les réponses plutôt que tout te mettre tout cuit dans le bec car je pense que c’est plus intéressant pour progresser. Dans les prochaines réponses j’essaie de mettre en spoiler les réponses aux questions mais essaie de réfléchir un peu avant.

+0 -0

Que fais cette ligne pour toi ?

Elle insère dans le tableau tab la liste des candidats possible pour une case de la grille G dans un tableau C.

Pourquoi ce n’est pas ce que tu veux ou pourquoi est-ce ce que tu veux ?

Sûrement que j’utilise mal les pointeurs, et quand je fais d’autres façons ça ne fonctionne pas. (J’ai regardé avec le debuguer gdb, c’est une erreur de segmentation)

Est-ce que tu fais de l’allocation dynamique comme en parle le sujet ou pas (d’ailleurs c’est quoi l’allocation dynamique ?) ?

A priori non ^^. L’allocation dynamique si je comprend bien, c’est d’allouer de la mémoire manuellement, donc allouer de la mémoire en fonction de ce que nous renvoie une instruction.

Qu’est ce qu’il se passe actuellement avers la case (0, 0) de l’exemple https://prnt.sc/m0d3rz.

Actuellement, avec la case (0,0), la fonction estCand me renvoie les candidats possibles (donc y’a 5, 9 et 6), le problème c’est que la fonction va arriver jusqu’à 9 et comme j’ai pas alloué d’espace dynamique au tableau, ben il remplace l’ancienne valeur. J’ai lu ton spoiler après, et c’était à peut prêt ce que je me disais.

J’ai pas l’habitude de faire des réponses didactiques et j’essaie de te diriger vers les réponses plutôt que tout te mettre tout cuit dans le bec car je pense que c’est plus intéressant pour progresser.

Je suis d’accord avec toi par rapport à ça, puis ça m’aide mieux à comprendre de toute façon. Merci ^^ !

Du coup, j’ai essayé ça :

void initJeu(int G[9][9], Cand C[9][9], Case O[81], int NBO) { // Initialise C, O et NBO
  int i, j, k = 0, l = 0;
  int ferme;
  Case coord;
  int tabTempo[9];

  for (coord.x = 0; coord.x < 9; coord.x++) {
    for (coord.y = 0; coord.y < 9; coord.y++) {
      /* Initialisation de C[9][9] */
      ferme = G[coord.x][coord.y] == 0; // 0 si la case est ouverte, 1 sinon

      if(!ferme) { // Si la case n'est pas ouverte (ouverte == 0)
        C[coord.x][coord.y].nbc = 0;
        C[coord.x][coord.y].tab = NULL;
      }
      else {
        for(k = 1; k < 9; k++) { // Vérification des candidats de 1 à 9
          if(estCand(G, k, coord)) { // Si un candidat fonctionne (==1), on l'initialise dans Cand C
            C[coord.x][coord.y].nbc++; // Incrémentation du nombre de valeurs possible pour une case
            C[coord.x][coord.y].tab = malloc(C[coord.x][coord.y].nbc * sizeof(Cand));
            if(C[coord.x][coord.y].tab == NULL) {
              printf("Erreur d'allocation !\n");
              exit(0);
            }
            printf("ca marche\n");
            C[coord.x][coord.y].tab[l] = k;
          }
        }
      }
    }
  }

  for(i = 0; i < 9; i++) { // Affichage test de C[i][j]
    for(j = 0; j < 9; j++) {
      for(l = 0; l < 9; l++) {
        printf("%d", C[i][j].tab[l]);
      }
      printf(" ");
    }
    printf("\n");
  }

  free(C[coord.x][coord.y].tab);
}

Résultat : http://prntscr.com/m1db5k http://prntscr.com/m1db8c

Ca doit être un truc qui se rapproche de ça, j’ai suivit les différents tutos sur l’alloc dynamique, mais à priori ça fonctionne pas tellement. Je dois faire n’importe quoi dans malloc(). Pourtant : C[coord.x][coord.y].tab = malloc(C[coord.x][coord.y].nbc * sizeof(Cand)); ca veut dire pour moi : donne au tableau-pointeur Cand.tab nbc(=nombre de valeur possible) * taille dans la mémoire de la structure Cand.

J’ai trouvé ça en une aprem’, et ça marche pas :colere2: ! J’ai du rater un truc sur les chapitres :euh: !

+0 -0

Ça avance un peu ! Il faut effectivement utiliser malloc mais tu ne l’utilises pas tout à fait de la bonne façon : D’abord, de quel type est l’attribut tab dans Cand est un pointeur vers un entier. La structure que tu va devoir manipuler ici est un tableau d’entier qui va être alloué dynamiquement (donc avec malloc).

Ici tu va stocker un tableau d’entier (gérer de manière dynamique) qui va contenir les candidats possibles, à la fin de l’initialisation de C[0][0] dans initJeu tu va donc avoir un tableau de int qui contient les trois entiers 5, 6 et 9.

L’appel que tu fais ici est le suivant :

C[coord.x][coord.y].tab = malloc(C[coord.x][coord.y].nbc * sizeof(Cand));

Ici tu n’alloues pas un tableau d’entier (int) mais un tableau de Cand, ce n’est pas ce que tu cherches à faire.

Pour allouer un tableau d’entier tu dois avoir quelque chose du genre malloc(taille_tableau * sizeof(int)) (voir https://zestedesavoir.com/tutoriels/755/le-langage-c-1/1043_aggregats-memoire-et-fichiers/4285_lallocation-dynamique/#2–12857_malloc-et-consoeurs -> allocation d’un tableau).

Maintenant qu’un tableau de int est allouer que se passe-t-il ? Si on prends l’exemple de C[0][0] encore une fois on devrait avoir l’exécution suivante :

  • 0 n’est pas candidat
  • 1 n’est pas candidat
  • 4 n’est pas candidat
  • 5 est candidat : nbc est incrémenté (= 1) et on alloue un tableau de 1 entier avec malloc.
  • 6 est candidat : nbc est incrémenté (= 2) et on alloue un tableau de 2 entier avec malloc.

Il y a néanmoins un problème ici, tu as une fuite de mémoire. Tu dois d’abord utiliser free (voir encore une fois le tutoriel C sur l’allocation dynamique et la partie sur free).

Notamment :

Retenez bien la règle suivante : à chaque appel à une fonction d’allocation doit correspondre un appel à la fonction free().

Si tu ne libères pas la mémoire alloué auparavant tu ne disposes plus de l’adresse du pointeur et tu ne peux plus libérer la mémoire (donc tu as une fuite de mémoire).

Ici lorsque 6 est un candidat possible tu dois augmenter la taille de ton tableau de 1. Pour cela tu |as deux possibilités possibles :

  • Allouer un nouveau tableau (avec malloc), copié les valeurs qui sont dans le tableau précédent dans le nouveau, y ajouter 6 puis libérer le tableau précédent.
  • Utilisé la fonction realloc qui copie tableau en modifiant avec une nouvelle taille (donc ici l’ancienne taille + 1) et y ajouter 6 (voir le tutoriel encore une fois pour realloc).

PS : Attention à ne pas oublié d’incrémenter l pour accéder à la dernière case de ton tableau.

Pour tes tests tu peux enlever les boucles sur coord.x et coord.y et regarder si ça marche correctement avec (0, 0), ça peut être plus facile pour corriger en affichant le contenu de C[0][0].tab par exemple et vérifier que c’est bien [5, 6, 9] (dans le cas de notre exemple).

C’est normal que ça te prennes du temps, tu utilises des notions que tu ne comprends pas complètement mais tu peux essayer de jouer un peu avec free / malloc / realloc sur un compileur en ligne (par exemple https://www.onlinegdb.com/online_c_compiler) pour voir ce qu’il se passe.

+1 -0

Okay, j’ai essayé pas mal de chose, sans grand succès…

Après pas mal d’essais pas du tout fructueux, je me retrouve avec ça :

void initJeu(int G[9][9], Cand C[9][9], Case O[81], int NBO) { // Initialise C, O et NBO
  int i, j, k = 0, l = 0;
  int *p;
  int ferme;
  Case coord;

  for (coord.x = 0; coord.x < 9; coord.x++) {
    for (coord.y = 0; coord.y < 9; coord.y++) {
      /* Initialisation de C[9][9] */
      ferme = G[coord.x][coord.y] == 0; // 0 si la case est ouverte, 1 sinon
      C[coord.x][coord.y].nbc = 0;

      if(!ferme) { // Si la case n'est pas ouverte (ouverte == 0)
        C[coord.x][coord.y].nbc = 0;
        C[coord.x][coord.y].tab = NULL;
      }
      else {
        for(k = 1; k < 9; k++) { // Vérification des candidats de 1 à 9
          if(estCand(G, k, coord)) { // Si un candidat fonctionne (==1), on l'initialise dans Cand C
            l = 0;
            C[coord.x][coord.y].nbc++; // Incrémentation du nombre de valeurs possible pour une case
            C[coord.x][coord.y].tab = malloc(C[coord.x][coord.y].nbc * sizeof(int));
            if(C[coord.x][coord.y].tab == NULL) {
              printf("Erreur d'allocation !\n");
            }

            C[coord.x][coord.y].tab[l] = k;
            l++;
            free(p);
          }
        }

        p = realloc(C[coord.x][coord.y].tab, C[coord.x][coord.y].nbc * sizeof(int));
        if(p == NULL) {
            printf("Erreur d'allocation de p!\n");
        }
        C[coord.x][coord.y].tab = p;
      }
    }
  }
  printf("\n");
  printf("%d\n", C[0][0].tab[1]);
  free(C[coord.x][coord.y].tab);
}

J’avais un code qui "fonctionnait" :

void initJeu(int G[9][9], Cand C[9][9], Case O[81], int NBO) { // Initialise C, O et NBO
  int i, j, k = 0, l = 0;
  int ferme;
  Case coord;

  for (coord.x = 0; coord.x < 9; coord.x++) {
    for (coord.y = 0; coord.y < 9; coord.y++) {
      /* Initialisation de C[9][9] */
      ferme = G[coord.x][coord.y] == 0; // 0 si la case est ouverte, 1 sinon
      C[coord.x][coord.y].nbc = 0;

      if(!ferme) { // Si la case n'est pas ouverte (ouverte == 0)
        C[coord.x][coord.y].nbc = 0;
        C[coord.x][coord.y].tab = NULL;
      }
      else {
        for(k = 1; k < 9; k++) { // Vérification des candidats de 1 à 9
          if(estCand(G, k, coord)) { // Si un candidat fonctionne (==1), on l'initialise dans Cand C
            l = 0;
            C[coord.x][coord.y].nbc++; // Incrémentation du nombre de valeurs possible pour une case
            C[coord.x][coord.y].tab = malloc(C[coord.x][coord.y].nbc * sizeof(int));
            if(C[coord.x][coord.y].tab == NULL) {
              printf("Erreur d'allocation !\n");
            }

            C[coord.x][coord.y].tab[l] = k;
            l++;
            // free(C[coord.x][coord.y].tab); // test mais, fonctionne pas +
          }
        }

        printf("%d ", C[coord.x][coord.y].nbc);
      }
    }
  }
  printf("\n");
  printf("%d\n", C[0][0].tab[0]);
  free(C[coord.x][coord.y].tab);
}

Mais qui au final à le même problème que celui d’hier, quand je met tab[1] il m’affiche une adresse et pas le bon résultat. Par contre [0] me donne 8 qui est juste, mais il manque 5 je crois comme candidat, puisque y’a 2 candidats.
Du coup, pour la fuite mémoire, je pensais qu’un free(C[coord.x][coord.y].tab); à chaque fin de la boucle suffirait, mais du coup, l’id 0 de tab ne fonctionne même plus à l’affichage !

Par contre, j’ai réglé un problème avec le nbc, j’ai oublié de l’initialiser à zéro au début de la boucle, ce qui fait qu’il donnait n’importe quoi comme résultat lorsque je l’ai printé ! Maintenant, je suis sûr qu’il donne les bons résultats, donc y’a plus d’erreur d’allocation.

-Allouer un nouveau tableau (avec malloc), copié les valeurs qui sont dans le tableau précédent dans le nouveau, y ajouter 6 puis libérer le tableau précédent. -Utilisé la fonction realloc qui copie tableau en modifiant avec une nouvelle taille (donc ici l’ancienne taille + 1) et y ajouter 6 (voir le tutoriel encore une fois pour realloc).

Franchement, j’ai essayé pas mal de trucs, mais je n’arrive à rien, je dois faire en gros un tableau temporaire qui s’occupe de faire les "traitements", puis tout mettre dans le tableau final à chaque fin de boucle ? C’est ce que j’ai "essayé" de faire dans le premier code que j’ai envoyé en haut du message, mais bon, ça ressemble à rien lol :'( !

+0 -0

Bonjour,

  • Essaye de ne pas supprimer le code que tu as mis dans tes messages précédent (la fonction estCand par exemple.
  • D’abord ta boucle n’est pas correcte à la ligne 17 tu dois avoir for(k = 1; k <= 9; k++) sinon tu ne testes pas pour la valeur 9.
  • Regarde comment tu remplis ton tableau, à chaque boucle tu as (ligne 20 ou ligne 19) l = 0 donc oui tu ne va remplir que la première case de ton tableau et les autres seront les valeurs avec lesquels malloc initialise (la valeur contenue en mémoire avant).
  • Ensuite tu n’as pas compris comment utiliser malloc / realloc / free

Si tu as le code suivant :

int * p;
p = malloc(sizeof(int) * 1);
p[0] = 5;
printf("%d", p[0]); // affiche 5
p = malloc(sizeof(int) * 2);
p[1] = 6;
printf("%d", p[0]); // affiche ? (on ne peut pas savoir car valeur non initialisée)
printf("%d", p[1]); // affiche 6

Donc lorsque tu fais un nouveau malloc comme aux lignes 22 ou 21 suivant le code tu dois recopier le valeurs précédentes par exemple;

int size_p = 1;
int *p = malloc(sizeof(int));
p[0] = 5;
int *tmp = malloc(2 * sizeof(int)); // idéalement tester si l'allocation a fonctionné correctement
for (int i = 0; i < size_p; ++i) {
  tmp[i] = p[i];
}
tmp[1] = 6;
free(p); // on désalloue le tableau précédent car on en a plus besoin
p = tmp; // le pointeur pointe maintenant sur la même chose que tmp donc le tableau qui contient [5, 6]

Il est important d’utiliser free autrement tu n’as plus de pointeur vers le premier bloc mémoire alloué et tu ne peux pas désallouer la mémoire que tu as alloué (et ça créé une fuite de mémoire).

Tu peux également utiliser realloc pour faire ce qu’on a fait.

int *p = malloc(sizeof(int));
p[0] = 5;
int * tmp = realloc(p, sizeof(int) * 2); // idealement tester si tmp alloué correctement, il faut utiliser seconde variable pour pouvoir `free(p) en cas d'erreur d'allocation ici (voir cours)
// à ce moment là si pas eu de problème p a été désalloué et les valeurs copiés vers tmp (donc tmp[0] = 5)
tmp[1] = 6; // on a aggrandit le tableau et on initialise la deuxième valeur à 6.
p = tmp; // le pointeur pointe maintenant sur la même chose que tmp donc le tableau qui contient [5, 6]

Avec ça essaies de faire la boucle interne de ta fonction (je sais pas pourquoi mais la mise en forme du code déconne)

l = 0;
for(k = 1; k <= 9; k++) {
     if(estCand(G, k, coord)) { // Si un candidat fonctionne (==1), on l'ajoute à C[coord.x][coord.y].tab
            C[coord.x][coord.y].nbc++; // Incrémentation du nombre de valeurs possible pour une case

            /* 
                ici il faut compléter avec malloc / realloc / free pour :
                copier le tableau précédent dans un nouveau tableau de taille supérieur (une nouvelle case), attention, si (l = 0 il n'y a pas de tableau précédent donc il faut juste faire un malloc(sizeof(int)).
                libérer la mémoire allouée pour le tableau précédent (optionnel si on utilises realloc avant)
            */

            C[coord.x][coord.y].tab[l] = k;
            l++;
     }
}
+0 -0

Bonsoir, je suis le camarade de Deewens pour ce projet. Actuellement il n’est pas là donc je me charge de prendre le relais :) Nous avons essayé de compléter le code à l’intérieur de la boucle for ( k = 1; ….) Cela donne ça :

  /* Suppression temporaire du code le temps de rendre le projet afin d'éviter tout problème/malentendu avec le logiciel anti-plagiat de l'établissement + copiage */

Et on obtient ce résultat : https://prnt.sc/m1y47n

Le problème c’est qu’on ne sait pas pourquoi à un moment donné, l’allocation dynamique ne fonctionne plus, surement du à une mauvaise allocation de notre part…

Avons-nous utilisé la bonne méthode pour copié un nouveau tableau de taille supérieur ?

Bonne soirée.

+0 -0

Arthur à oublier un else dans le code… C’est plutôt ça :

/* Suppression temporaire du code le temps de rendre le projet afin d'éviter tout problème/malentendu avec le logiciel anti-plagiat de l'établissement + copiage */

Ce qui donne ça : http://prntscr.com/m1z12h

Pour le code que je supprime, c’est temporaire le temps de terminer le projet à cause du système anti-plagiat de l’IUT qui risque de retrouver des similitudes avec le code qu’on envoie ici et qu’on enverra au propre (pour éviter tout malentendu). Et de plus, pour éviter de se faire allègrement recopier le code par des gens de notre promo et encore une fois d’éviter ainsi un malentendu avec le fameux système anti-plagiat. On a prévu de remettre les messages en entier à la fin pour aider d’autres personnes qui ont besoin.

+0 -0

Salut,

Le problème vient du malloc de la ligne 27 qui efface les valeurs contenues dans tab, en effet systématiquement lorsque l != 0 celui-ci va remplacé le tableau contenu dans l par un tableau par un nouveau tableau (avec les valeurs initialisés de manière aléatoire) si bien qu’à la fin de ton exécution seule la dernière case de tab va contenir une valeur pertinente.

Vous auriez pu vous en rendre compte en affichant toutes les valeurs contenues dans C[0][0].tab plutôt que juste celle à l’indice 0.

for (int i = 0; i < C[0][0].nbc; ++i) {
  printf("%d ", C[0][0].tab[i]);
}
printf("\n");

plutôt que

printf("%d\n", C[0][0].tab[0]);

Si on modifie le code cela donne quelque chose comme :

void initJeu(int G[9][9], Cand C[9][9], Case O[81], int NBO) { // Initialise C, O et NBO
  int i, k = 0, l = 0;
  int ferme;
  int *tmp;
  Case coord;

  for (coord.x = 0; coord.x < 9; coord.x++) {
    for (coord.y = 0; coord.y < 9; coord.y++) {
      /* Initialisation de C[9][9] */
      ferme = G[coord.x][coord.y] == 0; // 0 si la case est ouverte, 1 sinon
      C[coord.x][coord.y].nbc = 0;

      if(!ferme) { // Si la case n'est pas ouverte (ouverte == 0)
        C[coord.x][coord.y].nbc = 0;
        C[coord.x][coord.y].tab = NULL;
      }
      else {
        l = 0;
        for(k = 1; k <= 9; k++) { // Vérification des candidats de 1 à 9
          if(estCand(G, k, coord)) { // Si un candidat fonctionne (==1), on l'initialise dans Cand C
            C[coord.x][coord.y].nbc++; // Incrémentation du nombre de valeurs possible pour une case

            if(l == 0) {
              C[coord.x][coord.y].tab = malloc(sizeof(int));
              if(C[coord.x][coord.y].tab == NULL) {
                printf("Erreur d'allocation de C[coord.x][coord.y].tab !\n");
              }
            }
            /*else {
              C[coord.x][coord.y].tab = malloc(C[coord.x][coord.y].nbc * sizeof(int));
            }*/
            else {
              tmp = malloc((C[coord.x][coord.y].nbc /*+ 1*/) * sizeof(int)); // pas besoin d'incrémenté ici car nbc déjà incrémenté avant
              if(tmp == NULL) {
                printf("Erreur d'allocation de tmp !\n");
              }
              for (i = 0; i < C[coord.x][coord.y].nbc - 1; ++i) { // attention au -1 ici, car autrement tab[C[coord.x][coord.y]] accède à une case mémoire qui n'appartient pas au tableau je pense mais pas sûr à 100%
                tmp[i] = C[coord.x][coord.y].tab[i];
              }
              free(C[coord.x][coord.y].tab);
              C[coord.x][coord.y].tab = tmp;
            }

            C[coord.x][coord.y].tab[l] = k; // dans tous les cas on ajoute valeur à dernière case du tableau
            l++;
          }
        }
      }

      printf("%d ", C[coord.x][coord.y].nbc);
    }
  }
  printf("\n");
  printf("%d\n", C[0][0].tab[0]);
}

Plutôt qu’utilisé l il est possible de raisonner par rapport à nbc pour les différents if / accès au tableau.

Le même bout de code en utilisant malloc en allouant systématiquement dans tmp et en utilisant free que si tab == NULL (corresponds au moment où aucune alloc dynamique n’a été faite donc la première fois), ça évite d’utiliser une variable l et le code est peut-être un peu plus succinct :

         for(k = 1; k <= 9; k++) { // Vérification des candidats de 1 à 9
           if(estCand(G, k, coord)) { // Si un candidat fonctionne (==1), on l'initialise dans Cand C
             C[coord.x][coord.y].nbc++; // Incrémentation du nombre de valeurs possible pour une case
 
             int * tmp = malloc(sizeof(int) * C[coord.x][coord.y].nbc);
             if(tmp == NULL) {
               printf("Erreur d'allocation de tmp !\n");
             }

             if (C[coord.x][coord.y].tab != NULL) {
               for (int i = 0; i < C[coord.x][coord.y].nbc - 1; ++i) {
                 tmp[i] = C[coord.x][coord.y].tab[i];
               }
               free(C[coord.x][coord.y].tab);
             }
             C[coord.x][coord.y].tab = tmp;
             C[coord.x][coord.y].tab[C[coord.y][coord.y].nbc - 1] = k; // dans tous les cas on ajoute valeur à dernière case du tableau
           }
         }

ou en utilisant realloc :

         for(k = 1; k <= 9; k++) { // Vérification des candidats de 1 à 9
           if(estCand(G, k, coord)) { // Si un candidat fonctionne (==1), on l'initialise dans Cand C
             C[coord.x][coord.y].nbc++; // Incrémentation du nombre de valeurs possible pour une case
             
             if (C[coord.x][coord.y].tab == NULL) {
               C[coord.x][coord.y].tab = malloc(sizeof(int)); // forcément besoin d'alloué qu'une case ici
               // vérifié que allocation faite correctement
             } else {
               int *tmp = realloc(C[coord.x][coord.y].tab, C[coord.x][coord.y].nbc * sizeof(int));
               // vérifié que allocation de tmp correcte
               C[coord.x][coord.y].tab = tmp; // la copie des cases ainsi que le free sont dans realloc
             }
             C[coord.x][coord.y].tab[C[coord.y][coord.y].nbc - 1] = k; // dans tous les cas on ajoute valeur à dernière case du tableau
           }
         }
+1 -0

Salut,

En effet, ça fonctionne, j’ai pas tout compris parfaitement bien, mais ça nous aide quand même à mieux comprendre comment fonctionne les pointeurs. J’ai pas très bien compris la partie sans le "l", par contre…

Du coup, on doit quand même avancer, et je pensais pouvoir réussir le reste plus facilement que les pointeurs, mais on se heurte à quelque chose de VRAIMENT incompréhensible. Donc, nous avons voulu nous occuper d’initialiser O. C’est pas bien compliqué, suffit de faire ça à priori :

/* Suppression temporaire du code le temps de rendre le projet afin d'éviter tout problème/malentendu avec le logiciel anti-plagiat de l'établissement + copiage */

Sauf que, ça nous renvoie absolument n’importe quoi…
http://prntscr.com/m27so4 (même principe d’affichage que l’autre) Ca ne devrait pas être 80, 80, 80, 80, 80, 80 mais 00, 01, 04, etc.

Je ne vois pas pourquoi ça nous donne pas ça, c’est pourtant exactement la même façon d’afficher que le premier affichage qui fonctionne, c’est simplement dans une autre boucle qui fait la même chose. Or, si on doit utiliser O ailleurs dans le programme et qu’il donne des valeurs de ce genre, on va avoir de gros problèmes.

Du coup, je donne quand même le code entier :

/* Suppression temporaire du code le temps de rendre le projet afin d'éviter tout problème/malentendu avec le logiciel anti-plagiat de l'établissement + copiage */

Je sais pas trop ce que tu en penses, mais d’après ce que qu’on a compris de l’énoncé, il faut faire comme ça, peut-être que tu le comprends autrement toi…

Voilà et encore une fois, merci de prendre du temps pour nous aider, car c’est quand même vraiment la galère :/ …

+0 -0
O[coord.x * coord.y].x = coord.x;
O[coord.x * coord.y].y = coord.y;

Que se passe-t-il avec des coordonnées de la forme (0, y) ou (x, 0) ?

Le problème c’est que vous n’accédez pas correctement aux indices puisque par exemple avec la |façon dont vous cherchez à accéder (coord.x * coord.y) alors par exemple toutes les coordonnées |de la forme (0, y) ou (x, 0) vont dans la case O[0]).

Comment stocker autrement les cases ?

Pourquoi ne pas stocker à l’indice 0 puis l’indice 1 et ainsi de suite, seulement les cases ouvertes (les cases fermés ne nous intéressent pas). La variable NBO permettant de savoir jusqu’où les cases sont encore ouvertes et donc "pertinantes" ?

Comment fermer une case du tableau ? (ie : qu’elle ne fasse plus partie des NBO premières cases du tableau ?)

Comment stocker autrement les cases ?

Arthur57255 avait pensé à le faire avec NBO (comme tu l’as précisé dans ton spoiler d’ailleurs). Ce qui est effectivement plus logique c’est vrai. Moi je pensais que les cases ouvertes devaient être placé à l’endroit ou elles sont ouvertes dans la grille X/.

Et du coup, pour fermer une case du tableau, suffira de virer O.x et O.y de la case à fermé, de tout décaler vers la gauche et de décrémenter NBO. C’est bien plus simple comme ça en effet…

Merci du coup de main :) , je crois que la fatigue se fait ressentir, c’était un problème plutôt simple :-° !

+0 -0

Pas de problème,

Pour la solution à laquelle tu avais pensé, si tu veux qu’un tableau à une dimension se "comporte" comme un tableau à deux dimensions alors les accès peuvent se fiare de la façon suivante : O[coord.x * numberOfColums + coord.y]

Une autre possibilité plutôt que tout décaler vers la gauche (si l’ordre dans le tableau n’a pas d’importance et de swap la case à fermer avec la dernière ouverte (indéxée par NBO - 1) puis de décrémenter NBO (de cette façon cela se fait en constant).

+1 -0

Bonsoir, Nous avons presque fini le projet mais nous avons malheureusement un problème auquel on ne sait pas répondre… Ce problème se trouve dans la fonction fermerCase(). Nous avons réalisé cette fonction suivant :

/* Suppression temporaire du code le temps de rendre le projet afin d'éviter tout problème/malentendu avec le logiciel anti-plagiat de l'établissement + copiage */

Mais comme à notre habitude, nous rencontrons un problème de segmentation.. Faut-il faire de l’allocation dynamique ? Si oui, comment devons-nous nous y prendre parce que j’avoue que nous avons passé l’après-midi dessus et nous sommes complètement bloqué. Est-ce que la façon de procéder actuellement est la bonne afin de chercher les cases voisines ?

Ah, oups j’allais oublié, voici notre fonction appartient :

/* Suppression temporaire du code le temps de rendre le projet afin d'éviter tout problème/malentendu avec le logiciel anti-plagiat de l'établissement + copiage */

Est-elle bonne ?

Pour finir, la fonction rechCaseUnique() ressort 1 si une case possède un candidat unique, sinon 0. Merci encore pour vos réponses. Bonne soirée. :)

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte