-4
Mon programme fonctionne correctement lorsque j'utilise un tableau de 81 éléments mais quand je fais face à un tableau de 256 blocs, il se bloque et je ne sais pas pourquoi il le fait. Je vous présente tout le code source et le texte d'entrée que vous pouvez utiliser dans un fichier .txt avec un dernier retour chariot.Pourquoi mon programme plante-t-il avec un débordement de pile?
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <windows.h>
#include <malloc.h>
int grille[256];
int domaine[256][17]; /* indique les valeurs possib pour case donnee */
int domaine_taille[256]; /* nombre de valeurs possibles une case donnee */
int compteur_noeuds;
void restreindre_domaines(int);
int backtrack(int imite_limite_par_ton_nez);
#define PERR(bSuccess, api) \
{if (!(bSuccess)) perr(__FILE__, __LINE__,api, GetLastError());}
#define INCONNU -1
void lire_grille()
{
int k = 0;
while (k < 256) {
char c = getchar();
if (c >= '0' && c <= '9') //0 a 9
grille[k++] = c-48;
if(c >= 'a' && c <= 'f') // a a f
grille[k++] = c-87;
if (c == '.' || c == ' ' || c== '+') // espace + ou .
grille[k++] = INCONNU;
if (c == EOF)
{
fprintf(stderr, "Lecture de la grille : mauvais format\n");
exit(1);
} }}
void afficher_grille() /* afficher la grille courante sur stdout */
{
int c, l;
for (l = 0; l < 16; l++) {
for (c = 0; c < 16; c++) {
int k = l*16+c;
if (grille[k] == INCONNU) printf(".");
if (grille[k] >= 0 && grille[k] <= 9) //0 a 9
printf("%c", grille[k]+48);
if(grille[k] >= 10 && grille[k] <= 15) // a a f
printf("%c", grille[k]+87);
}
printf("\n");
}
printf("\n");
}
void init_domaines() /* en fonction grille,initialiser domaines */
{
int i, v;
for (i = 0; i < 256; i++)
{
domaine_taille[i] = 16;
for (v = 0; v <= 16; v++)
domaine[i][v] = 1;
}
for (i = 0; i < 256; i++) /* restreindre domaines cases remplies */
if (grille[i] != INCONNU) restreindre_domaines(i);
}
/*oter valeurs des domaines incompatibles avec valeur case i */
void restreindre_domaines(int i)
{
int l = i/16; //ligne
int c = i % 16; //colonne
int lb = l/4; //
int cb = c/4; //
int l2, c2, lr2, cr2, i2;
/* contraintes de la colonne contenant la case i */
for (l2 = 0; l2 < 16; l2++) {
i2 = l2*16+c;
if (domaine[i2][grille[i]]!=0) {
domaine[i2][grille[i]] = 0;
domaine_taille[i2]--;
}
}
/* contraintes de la ligne contenant la case i */
for (c2 = 0; c2 < 16; c2++) {
i2 = l*16+c2;
if (domaine[i2][grille[i]]) {
domaine[i2][grille[i]] = 0;
domaine_taille[i2]--;
}
}
/* verifier la region contenant la case i */
for (lr2 = 0; lr2 < 4; lr2++)
for (cr2 = 0; cr2 < 4; cr2++) {
i2 = (lb*4+lr2)*16+(cb*4+cr2);
if (domaine[i2][grille[i]]) {
domaine[i2][grille[i]] = 0;
domaine_taille[i2]--;
}}}
int main()
{
lire_grille();
afficher_grille();
init_domaines();
backtrack(0);
printf("%d noeuds cherches\n", compteur_noeuds);
printf(" \n");
_getch();
return 0;
}
int backtrack(int uz)
{
if (uz==-99) return(uz);
int i, i_min = -1,aa=0;
int taille_min = 17;
int domaine2[256][17];
int domaine_taille2[256];
static int toc,Toc;
int iz,zzz=0;
toc++;
static int xu;
xu=true;
int lnum[16];
lnum[0]=0;
lnum[1]=15;
lnum[2]=14;
lnum[3]=13;
lnum[4]=12;
lnum[5]=11;
lnum[6]=4;
lnum[7]=3;
lnum[8]=2;
lnum[9]=1;
lnum[10]=5;
lnum[11]=10;
lnum[12]=9;
lnum[13]=8;
lnum[14]=7;
lnum[15]=6;
int tst=0;
for (iz = 0; iz < 256; iz++)
{
if (grille[iz] != INCONNU)tst++;
}
if(tst==256)
{ /*fin:*/
// printf("\n%d 2 valeur tst\n", tst);
afficher_grille();
xu=0;
return xu;
}
/* chercher la case avec le domaine le plus petit */
for (i = 0; i < 256; i++)
{
if (grille[i] == INCONNU && domaine_taille[i] < taille_min)
{
i_min = i;
taille_min = domaine_taille[i];
//printf("i %d *do_tail[i] %d *tail_min %d \n",i,domaine_taille[i],taille_min);
}
if(toc >10000)
{
toc=0;
afficher_grille();
printf("\n%d noeuds cherches\n", compteur_noeuds);
printf(" toc %d et Toc %d \n",toc,Toc);
Toc++;
printf("-------------------------------------------\n");
}
}
compteur_noeuds++;
// for (grille[i_min] = lnum[aa]; grille[i_min] <= lnum[aa+15]; grille[i_min]++,aa++)
for (grille[i_min] = 0; grille[i_min] <= 15; grille[i_min]++,aa++)
{
if (domaine[i_min][grille[i_min]] == 0)
continue;
/* on sauvegarde l'etat courant de domaine
et domaine_taille pour les retablir apres l'appel recursif */
memcpy (domaine2, domaine, sizeof(domaine));
memcpy (domaine_taille2, domaine_taille, sizeof(domaine_taille));
restreindre_domaines(i_min);
backtrack(uz);
if (xu==0)return xu;
memcpy (domaine, domaine2, sizeof(domaine));
memcpy (domaine_taille, domaine_taille2, sizeof(domaine_taille));
}
grille[i_min] = INCONNU;
return 0;
}
Vademecum: prog.exe < inp.txt
ici est un texte inp.txt avec un bon format (16x16 numéro 1-F et pour le cas de la recherche.)
.ae692...0..5.8d
5....4.12.37.bc6
..f.....5......4
.b.8e5f..9.d..01
.42b.17.3.......
.3.52....bf0...c
.......a.1..042b
....4.cb8...1..a
....f.4eb...3..8
.......5.3..acef
.7.2d....51f...9
.e3c.ab.0.......
.0.a58e..7.1..63
..1.....d......2
4....d.26.59.eb0
.6b7c9...4..d.15
Donc, si vous pouvez m'aider.
Recommandez de lire ceci: http://stackoverflow.com/help/how-to-ask et cela http://stackoverflow.com/help/mcve. Je recommande également d'essayer de déboguer. Pire encore, vous avez des inclusions spécifiques au système d'exploitation dans votre programme. Si vous voulez que les gens vous aident, vous devriez certainement poster un code minimal qui reproduit vos erreurs. Et les noms de variables doivent être en anglais, pas français;) – LBes
[Comment déboguer de petits programmes] (http://ericlippert.com/2014/03/05/how-to-debug-small-programs/) –
'backtrack' nécessite environ 20 Ko de pile * par appel récursif *. La profondeur de la récursivité n'est pas évidente, mais si vous utilisez Windows (comme le suggère votre code), vous n'obtenez que 2 Mo de pile, ce qui est suffisant pour une profondeur de récursivité de 100 ou plus. Pensez à utiliser 'unsigned short', ou peut-être même' unsigned char' si toutes les valeurs nécessaires vont correspondre, pour tous les tableaux. Si cela ne suffit pas, vous devrez vous débarrasser de la récursivité et/ou passer à des tas de scratch alloués. – zwol