Problem mit der Rekursion

[Schap]

Hallo,
Wir haben die Aufgabe das Springerproblem mit Hilfe des Backtracking-Verfahrens zu lösen.

Wir haben u.g. Code geschrieben der innerhalb von ca 0.5 bis 2sec Schachbretter der Kantenlänge 5 bis inkl. 7 berechnet. Die geforderte Kantenlänge von 8 Feldern klappt nicht.
Selbst nach über einer Stunde Rechenzeit kein Ergebnis. Der Taskmanager zeigt aber weiter Aktivität an.

Unsere Vermutung ist das er sich in der Rekursion verrent. Nur wo? Unser Praktika Begleiter meinte nur nach 5min drüberschauen er fände den Fehler nicht.
Wir haben jetzt nichtmal einen Ansatzpunkt warum er mit 25, 36 und 49 Feldern großen Brettern keine Probleme hat aber mit dem 64er

Compiler ist "Dev-C++" in der Version 4.9.9.2

#include<stdio.h>

int Feld[8][8];

void Ausgabe(int g)
{	
  int i, j;
  for(i=0 ; i<g ; i++) {
    for(j=0 ; j<g ; j++) {
      printf("%3d",Feld[i][j]);
    }
    printf("\n");
  }
}

int Springer(int g, int zeile, int spalte, int num)
{	
  if(num > g*g) {
    Ausgabe(g);
    return 1; /* Bei endgültiger Lösung Rekursion abbrechen */
  }
  else {
    /* Feld muss innerhalb des Brettes und noch nicht besucht worden sein */
    if(0<=zeile && zeile<g && 0<=spalte && spalte<g && Feld[zeile][spalte]==0) {
      /* Momentan besuchtes Feld auf nächst höhere Zahl setzen */
      Feld[zeile][spalte]=num;

      /* Alle Möglichkeiten probieren und bei */
      /* gefundener Lösung Rekursion abbrechen */
      if(Springer(g, zeile+2,spalte+1,num+1)) return 1;
      else if(Springer(g, zeile+2,spalte-1,num+1)) return 1;
      else if(Springer(g, zeile-2,spalte+1,num+1)) return 1;
      else if(Springer(g, zeile-2,spalte-1,num+1)) return 1;
      else if(Springer(g, zeile+1,spalte+2,num+1)) return 1;
      else if(Springer(g, zeile-1,spalte+2,num+1)) return 1;
      else if(Springer(g, zeile+1,spalte-2,num+1)) return 1;
      else if(Springer(g, zeile-1,spalte-2,num+1)) return 1;

      /* Besuch rückgängig machen */
      Feld[zeile][spalte]=0;
    }
  }
  /* Rekursion fortsetzen */
  return 0;
}

int main(void) {
  /* g = Kantenlänge des Brettes */
  int g = 8;
  int i, j;

  /* Nullen des Brettes */
  for(i=0 ; i<g ; i++) {
    for(j=0 ; j<g ; j++) {
      Feld[i][j] = 0;
	}
  }
  /* Startposition (unten links) */
  Springer(g, g-1, 0, 1);

  getch(); /* Pause nach Ausführung */
}

[Cler]

Überprüf mal deine Abbruchbedingung der Rekursion und bau dir doch mal eine Ausgabe der Zeilen und Spaltennummer ein.
Dann solltest du schnell merken weshalb er nicht abbricht...

[Schap]

Der Code arbeitet scheinbar fehlerfrei.
Habe gerade ausprobiert ob es einen Unterschied macht in welcher Reihenfolge ich diesen Teil des Codes durchgehe:

if(Springer(g, zeile+2,spalte+1,num+1)) return 1;
else if(Springer(g, zeile+2,spalte-1,num+1)) return 1;
else if(Springer(g, zeile-2,spalte+1,num+1)) return 1;
else if(Springer(g, zeile-2,spalte-1,num+1)) return 1;
else if(Springer(g, zeile+1,spalte+2,num+1)) return 1;
else if(Springer(g, zeile-1,spalte+2,num+1)) return 1;
else if(Springer(g, zeile+1,spalte-2,num+1)) return 1;
else if(Springer(g, zeile-1,spalte-2,num+1)) return 1;

Ja... Es macht einen gewaltigen Unterschied.

Ich hab es auf folgendes geändert:

if(Springer(g, zeile+2,spalte+1,num+1)) return 1;
else if(Springer(g, zeile-2,spalte+1,num+1)) return 1;
else if(Springer(g, zeile+1,spalte+2,num+1)) return 1;
else if(Springer(g, zeile-1,spalte+2,num+1)) return 1;
else if(Springer(g, zeile+2,spalte-1,num+1)) return 1;
else if(Springer(g, zeile-2,spalte-1,num+1)) return 1;
else if(Springer(g, zeile+1,spalte-2,num+1)) return 1;
else if(Springer(g, zeile-1,spalte-2,num+1)) return 1;

und jetzt wird mir die Antwort innerhalb von ca 5sec geliefert.

Die Aufgabe ist somit gelöst.
Ich lasse das Programm einfach mal über Nacht mit der alten Reihenfolge laufen und schaue mal ob auch dort nach einer (großen) Zeit ein Ergebnis erreicht wird.

Gruß Schap

[Cler]

Nun der Code macht das was du programmiert hast.
Ist dir denn klar, weshalb die Reihenfolge eine so wichtige rolle spielt?
wenn du es jetzt nicht ausführst, würde folgender Code auch korrekt laufen?

if(Springer(g, zeile+2,spalte+1,num+1)) return 1;
else if(Springer(g, zeile-2,spalte+1,num+1)) return 1;
else if(Springer(g, zeile+1,spalte+2,num+1)) return 1;
else if(Springer(g, zeile+2,spalte-1,num+1)) return 1;
else if(Springer(g, zeile-1,spalte+2,num+1)) return 1;
else if(Springer(g, zeile-2,spalte-1,num+1)) return 1;
else if(Springer(g, zeile+1,spalte-2,num+1)) return 1;
else if(Springer(g, zeile-1,spalte-2,num+1)) return 1;