rekursion stack globale variable - probleme

hallo an alle.
ich hab mir mal als einstiegsaufgabe einen sudoku löser aufgegeben.

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

long int count;

short zeile, spalte, x;
short z,s,kand;

/*
int blatt[9][9] = {{0 ,0 ,0 ,0 ,16,0 ,0 ,0 ,0},
                   {0 ,0 ,14,15,0 ,0 ,12,0 ,0},
                   {0 ,0 ,0 ,0 ,17,12,13,0 ,0},
                   {0 ,17,0 ,0 ,0 ,13,0 ,12,0},
                   {0 ,13,0 ,12,0 ,16,19,0 ,0},
                   {0 ,0 ,19,0 ,0 ,0 ,0 ,0 ,13},
                   {0 ,0 ,0 ,0 ,11,0 ,17,0 ,0},
                   {18,14,0 ,0 ,13,17,0 ,0 ,0},
                   {0 ,0 ,0 ,0 ,0 ,18,0 ,15,0}};
*/
short blatt[9][9]={{0 ,13,0 ,0 ,0 ,0 ,0 ,0 ,0},
                   {0 ,0 ,0 ,11,19,15,0 ,0 ,0},
                   {0 ,19,18,0 ,0 ,0 ,0 ,16,0},
                   {18,0 ,0 ,0 ,16,0 ,0 ,0 ,0},
                   {14,0 ,0 ,0 ,0 ,13,0 ,0 ,11},
                   {0 ,0 ,0 ,0 ,12,0 ,0 ,0 ,0},
                   {0 ,16,0 ,0 ,0 ,0 ,12,18,0},
                   {0 ,0 ,0 ,14,11,19,0 ,0 ,15},
                   {0 ,0 ,0 ,0 ,0 ,0 ,0 ,17,0}};

ausgabe() {
   int i;
   int j;
   printf("\n");
   for (j=0;j<9;j++){
       if (j==3 | j==6) {
       printf("-----------------------------\n");}
       for (i=0;i<9;i++){
           if (i==3 | i==6) {
              printf("| ");}
              if (blatt[j][i]>10){
                 printf("%d ",blatt[j][i]);
              }
              else if(blatt[j][i]<10){ 
                   printf("%d  ",blatt[j][i]);
              }
       }
   printf("\n");
   }
}

/*returns 1 for correct ; 0 for not correct  */
is_correct(short x ,short zeile, short spalte){ //x-kandidat
   short j,i,k,l,treffer;
   if (x==10) treffer=1;
   for (j=0;j<9;j++){            //sucht in der zeile
       if (x==(blatt[zeile][j])%10) treffer=1;
   }

   for (i=0;i<9;i++){           //sucht in der spalte
       if (x==(blatt[i][spalte])%10) treffer=1;    
   }

   //sucht im kleinen quadrat
   for (l=zeile/3*3;l<(((zeile/3)*3)+3);l++){       
       for (k=spalte/3*3;k<spalte/3*3+3;k++){
           if (x==(blatt[l][k])%10) treffer=1;
         //printf("zeile:%d ",l);
         //printf("spalte:%d ",k);
       }
   //printf("\n");
   }
   if (treffer != 1) return 1;
   else return 0;
}

fill(short x,short zeile,short spalte){
   short abbruch;
   //if (count==65094)printf("debug");
   //z = zeile; 
   //s = spalte;
   //kand = x;
   count = count + 1;
   //printf("count: \%d");
   if ((zeile==0)&&(spalte==9)) abbruch=1;
   if (count<20){//die grosse abbruchbed.???
      if (blatt[zeile][spalte]<10) {             //vorgabe zahl
         if (zeile==9) fill(x,0,spalte + 1);     //zeile9? ->neue spalte
         else{                                   // 
             if (is_correct(x,zeile,spalte)){     //wenn der kandidat passt -eintragen
                blatt[zeile][spalte]=x;
             }
             else {                               //kandi passt net
                if (x<10){                        //wenn kand <=9 probieren
                   fill(x+1,zeile,spalte);        //
                }
                else{                            //wenn kand =10 
                   blatt[zeile][spalte]=0;           //zelle zurücksetzen
                   if (zeile==0) {                  //spalte nach links springen
                      zeile=8;
                      spalte=spalte-1;
                      fill((blatt[zeile][spalte])+1,zeile,spalte);
                   }
                   else {
                      zeile=zeile-1;                //zeile nach links springen
                      fill((blatt[zeile][spalte])+1,zeile,spalte); 
                   }
                }
             }
         fill(1,zeile+1,spalte);
         }     
      }

      else if (blatt[zeile][spalte]>10) {     // wenn vorgabezahl alles lassen
         if (x>11) fill((blatt[zeile-1][spalte])+ 1,zeile -1,spalte);
         else{
             if (zeile==8) fill(x,0,spalte + 1);    // neue spalte
             else fill(x,zeile +1 ,spalte);
         }
      }
   }
}

main(void) {
   ausgabe();
   fill(1,0,0);
   ausgabe();
   //fill(1,5,1);
   printf("count:%d\n",count);
   //printf("zeile:%d\n",z);
   //printf("spalte:%d\n",s);
   //printf("kandidat:%d\n",kand);
   //ausgabe();
   //printf("%d ",blatt[4][0]);
   //printf("rueckgabe:%d ",is_correct(1,0,0));
   system("pause");
   return EXIT_SUCCESS;
}

ich glaube, dass das inhaltlich stimmen könnte, abgesehen davon dass mein hauptspeicher nicht für die lösung reicht.
was mich wundert: ich lasse in fill() den counter hochzählen und bei 20 abbrechen. lasse ich nach ausführung count ausgeben steht er auf 33?
weiter: versuchte ich die globale variable z zu belegen. leider funktioniert das nur beim ersten rekursiven aufruf der funktion fill.
ich bitte um meinungen.

mcr

Hi,

ich habe mir mal deinen Code angesehen und reporte dir hier ein paar
Fehler, die mir aufgefallen sind:

- In C sieht die Funktionsdeklaration wie folgt aus:
     Rückgabewert Funktionsname (Parameterliste)
  Zum Beispiel sieht deine Funktion ausgabe dann so aus:
     void ausgabe(void)    oder         void ausgabe()
- In der Funktion ausgabe() fragst du in einer If-Anweisung folgendes:
     if (j==3 | i==6)
  Dieses | (oder) ist eine Bitoperation. Du meintest aber: ||
  richtig wäre also:  if (j==3 || i==6)

Du verwendest die folgenden globale Variablen, die du nicht wirklich
brauchst:

short zeile, spalte, x;
short z,s,kand;

Nun noch zu deiner Frage: warum count am Ende 33 ist.
Du brichst zwar nach count == 20 ab, hast aber immer noch ein paar Aufrufe
innerhalb der Rekursion. Da du count vor dem Abbruch erhöhst, wächst count
weiter an.

Ob dein Programm ansonsten korrekt arbeitet, habe ich nicht überprüft.

Gruß mcr

PS: Die Kommentierung mit // ist nicht Ansi-C like.

mcr schrieb:

PS: Die Kommentierung mit // ist nicht Ansi-C like.

isse wohl!