Backtracking Magisches Quadrat Laufzeit Problem

Hallo,

Wie der Titel schon sagt hab ich ein Problem beim schreiben eines Programmes welches mittels Backtracking Magische Quadrate erstellen soll.

Aktuell funktioniert mein Programm auch soweit das alle Zeilen Magisch sind, die erste Spalte und die Diagonale von oben rechts nach unten links.

Den Rest sollte ich auch noch hinbekommen hierbei liegt auch nicht mein Problem.

Mein Problem ist das sich mein Programm nach genau 4772 versuchen mit den Einstellungen "Debug" aufhängt, verwende Microsoft Visual Studio Ultimate.

Wenn ich die Einstellung auf "Release" stelle hängt sich mein Programm nach 35452 versuchen auf.

Ich bin etwas verzweifelt weil bevor ich den Fehler nicht finde warum sich das Programm aufhängt brauch ich nicht weiter machen. Da es so niemals ein Magisches Quadrat mit Kantenlänge 4 lösen wird. Da die Versuchs Anzahl mit Sicherheit höher als 4772 oder 35452 sein wird.

Ich hab schon überall gesucht an was es liegen könnte allerdings bin ich kein C Profi und würde mich eher als Anfänger bezeichnen.

Daher entschuldige ich mich gleich Vorweg wenn mein Code unübersichtlich sein sein sollte. Hier nun der Code ich Hoffe das mir jemand weiter helfen kann oder nen tip geben kann.

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define index(zeile, spalte) n*zeile + spalte
int  summZeile,summSpalte,summD1,summD2,magischeSumme,pruefw,j=1;
int *feld;

void pruef(int zeile, int spalte, int i, int n){ 
	if (zeile >= 0 && spalte >= 0 && zeile < n && spalte < n && pruefw <2){
		/*printf("Zeile: %d , Spalte: %d ",zeile,spalte);*/
		if (zeile == 0 && spalte == 0){
			/*printf("feld00: %d i: %d \n\n",feld[index(zeile,spalte)],i);*/
			if(feld[index(zeile,spalte)] == i){
			pruefw++;
			/*printf("Gleich00, pruefw: %d\n\n",pruefw);*/
			pruef(zeile-1,spalte-1,i,n);
			}
			pruef(zeile-1,spalte-1,i,n);
		}
		if (zeile != 0 && spalte == 0){
			/*printf("feldO: %d i: %d \n\n",feld[index(zeile,spalte)],i);*/
			if(feld[index(zeile,spalte)] == i){
			pruefw++;
			/*printf("GleichO, pruefw: %d\n\n",pruefw);*/
			pruef(zeile-1, n-1,i,n);
			}
			pruef(zeile-1, n-1,i,n);
		}
		else{
			if(spalte !=0){
				/*printf("ZeileU: %d , SpalteU: %d \n\n",zeile,spalte);*/
			/*printf("feldU: %d i: %d \n\n",feld[index(zeile,spalte)],i);*/
			if(feld[index(zeile,spalte)] == i){
			pruefw++;
			/*printf("GleichU, pruefw: %d\n\n",pruefw);*/
			pruef(zeile, spalte-1,i,n);
			}
			pruef(zeile, spalte-1,i,n);
			}
		}
	}

}

void summS(int zeile, int spalte, int n) {
	if (zeile >= 0 && spalte >= 0 && zeile < n && spalte < n){
		if (zeile == n-1){
			summSpalte += feld[index(zeile,spalte)];
		}
		else
		{
			summSpalte += feld[index(zeile,spalte)];
			summS(zeile+1, spalte,n);
		}
	}
}

void summDLR(int zeile, int spalte, int n) {
	if (zeile >= 0 && spalte >= 0 && zeile < n && spalte < n){
		summD1 += feld[index(zeile,spalte)];
		summDLR(zeile+1, spalte+1,n);
	}
}

void summDRL(int zeile, int spalte, int n) {
	if (zeile >= 0 && spalte >= 0 && zeile < n && spalte < n){
		summD2 += feld[index(zeile,spalte)];
		summDRL(zeile+1, spalte-1,n);
	}
}

void ausgabe(int zeile, int spalte, int n) {
	if (zeile >= 0 && spalte >= 0 && zeile < n && spalte < n){
		if (spalte == n-1){
			printf("%d \n",feld[index(zeile,spalte)]);
			ausgabe(zeile+1, 0,n);
		}
		else
		{
			printf("%d ",feld[index(zeile,spalte)]);
			ausgabe(zeile, spalte+1,n);
		}
	}

}

void eingabe(int zeile, int spalte, int i, int n) {
	if (zeile >= 0 && spalte >= 0 && zeile < n && spalte < n && i <= n*n+1){
		printf("Versuch: %d\n", j);
		j++;
		/*ausgabe(0,0,n);
		printf("\n");*/
		/*if(j==120){
			exit(0);
		}*/
		pruefw=0;
		/*summSpalte=0;*/
		if(i == n*n+1){
			//if(summSpalte != magischeSumme){
			//	summSpalte=magischeSumme;
			//	//ausgabe(0,0,n); /*später weg*/
			//	eingabe(0,0,(feld[index(0,0)]+1),n);
			//}
			if(spalte == 0){
				summZeile=(magischeSumme-(feld[index((zeile-1),(n-1))]));
				/*printf("Warnung, Wertfeld: %d, Zeile: %d, Spalte: %d\n",feld[index((zeile-1),(n-1))]+1,zeile,spalte);
				printf("Zeile-1: %d, Spalte n-1: %d\n",zeile-1,spalte=n-1);
				printf("SummeZeile : %d\n",summZeile);*/
				/*ausgabe(0,0,n);*/
				/*exit(0);*/
				eingabe((zeile-1),(n-1),(feld[index((zeile-1),(n-1))]+1),n);

			}
			summZeile-=feld[index(zeile,spalte-1)];
			eingabe(zeile,spalte-1,(feld[index(zeile,spalte-1)]+1),n);
		}
		if (spalte == n-1){

			feld[index(zeile,spalte)]=i;
			pruef(zeile,spalte,feld[index(zeile,spalte)],n);
			/*printf("pruefw: %d gebrueft: %d \n\n",pruefw,feld[index(zeile,spalte)]);*/
			if(pruefw == 2){
				eingabe(zeile,spalte,i+1,n);
				pruefw=0;
			}
			pruefw=0;
			summZeile += feld[index(zeile,spalte)];
				if(summZeile != magischeSumme){
					/*printf("Nicht magisch summZeile: %d \n\n",summZeile);*/
					summZeile-=feld[index(zeile,spalte)];
					/*ausgabe(0,0,n);*/
					/*printf("\n");*/
					eingabe(zeile,spalte,i+1,n);
					/*exit(0);*/
				}
				else{
					/*printf("Magisch summZeile: %d \n\n",summZeile);*/
					/*pruef(zeile,spalte,i);*/
					/*ausgabe(0,0);*/
					/*printf("\n");*/
					summZeile=0;
					//ausgabe(0,0,n); /*später weg*/
					eingabe(zeile+1,0,1,n);
					/*pruef(zeile,spalte,i);*/
					/*printf("pruefw: %d \n\n",pruefw);*/
					printf("***Its Magic Wuhu***\n\n");
					ausgabe(0,0,n);
					printf("\n");
					exit(0);
				}
		}
		else{

			feld[index(zeile,spalte)]=i;
			pruef(zeile,spalte,feld[index(zeile,spalte)],n);
			/*printf("pruefw: %d gebrueft: %d \n\n",pruefw,feld[index(zeile,spalte)]);*/
			if(pruefw == 2){
				eingabe(zeile,spalte,i+1,n);
				pruefw=0;
			}
			pruefw=0;
			if(zeile == n-1 && spalte == 0){
			summSpalte=0;
			summS(0,spalte,n);
			/*printf("SummSpalte: %d\n\n",summSpalte);*/
			if(summSpalte != magischeSumme){
				/*summSpalte=0;*/
				//ausgabe(0,0,n); /*später weg*/
				eingabe(zeile,spalte,i+1,n);
			}
			if(summSpalte == magischeSumme){
				summD2=0;
				summDRL(0,n-1,n);
				if(summD2 != magischeSumme){
					eingabe(zeile,spalte,i+1,n);
				}
				//ausgabe(0,0,n); /*später weg*/
				/*exit(0);*/ /*test*/
				summSpalte=0;
			}
			}
			summZeile += feld[index(zeile,spalte)];
			eingabe(zeile, spalte+1,/*i+1*/1,n);
		}
	}
}

int main() {
	int n;
	scanf("%d",&n);
	printf("\n");
	magischeSumme=(n*n*n+n)/2;
	summSpalte=magischeSumme;

	feld = (int *) malloc(n*n*n*sizeof(int));
	if (feld == NULL) {
		printf("Malloc-Error!\n");
		return 1;
	}

	eingabe(0,0,1,n);	
	getchar();
	return 0;
}

Zeile 195 ist nen Fehler müsste:

feld = (int *) malloc(n*n*sizeof(int));

heißen. Hatte da gerade nur was getestet.

Vielleicht noch eine Kurze Erklärung zur Funktion "pruef" und "eingabe".

"pruef" prüft das Feld ob eine Zahl mehr wie einmal drin steht. Sprich ob diese 2 mal vorkommt.

"eingabe" ist die eigentliche Funktion wo das Feld magisch gemacht wird.

Für welche Werte von n passiert das denn?

Durch die Rekursionen läuft dein Stack über. (Kennst du Schleifen?)

Dein Makro index ist ziemlich übel. Fehlende Klammern und Bezug auf Variable n.

Funktionen können Rückgabewerte haben.
Dafür sind sie gemacht.
Dann kannst du auch auf die ganzen üblen globalen Variablen verzichten.

Danke für die schnelle Antwort DirkB.

Ich wäre erstmal glücklich wenn es für n=4 funktioniert.

Ja ich kenne schleifen allerdings sollen wir nur Rekursion benutzen, soll eine Art Übung sein.

Was genau meinst du mit Stack überlaufen? Und wie genau kann ich das verhindern. (Sry wenn ich doofe Fragen stelle)

Was genau meinst du mit mein Makro index ist ziemlich übel? (Sry wenn ich wieder doof frage möchte es nur verstehen und verbessern)

Ja das des mit den globalen Variablen schlecht ist ist mir bewusst. Das werd ich wohl gleich mal versuchen zu ändern. Wollte ich am ende eigentlich machen, war wohl nicht schlau...

Lokale Variablen (dazu gehören auch die Paramter einer Funktion) werden auf dem Stack (http://de.wikipedia.org/wiki/Kellerspeicher) angelegt.

Dieser Speicher ist begrenzt.
Da bei einem rekursiven Aufruf die Variablen jedesmal neu angelegt werden, ist irgendwann mal Schluss.
(Im Debugmodus werden dort noch ein paar mehr Informationen abgelegt)

Du kannst irgendwo in den Projekteigenschaften die Stackgröße ändern.

Du hast beim Aufruf von deinem index-Makro ja schon Klammern gesetzt. (wegen Punkt- vor Strich-Rechnung)
Die gehören aber nicht in den Aufruf sondern in die Definition.
Und das n gehört da auch mit rein:

#define index(zeile, spalte, n) ((n)*(zeile) + (spalte))

Dann ist das Makro universell, auch wenn die Größe mal nicht n heißt.
Bei Makros kann man nicht zuviel Klammern machen.

Ok das mit der Definition hab ich verstanden und gleich geändert. Hätte ich mir die ganzen klammeren im Aufruf sparen können.

Werde die das dann gleich noch anpassen.

Ok das mim Stack hab ich auch einigermaßen nun verstanden. Die Stackgröße in den Projekteigenschaften zu ändern wäre ja eher nur nee mogel Packung.

Wenn ich nur Zeiger in den Funktionen benutzen würde könnte ich dann damit das Problem um gehen? Weil sonst wird mein Stack ja immer zwangsläufig irgendwann voll. Oder was könnte ich sonst noch dagegen tun?

Nochmal Danke für deine Antwort DirkB

knivil

Bei n=4 sollte die Rekursionstiefe eigentlich maximal nur 16 sein fuer jede Zahl im magischem Quadrat. Die Summe sollte nochmals 4 tief werden. Mit einer Rekursionstiefe von 20 sollte kein Stack Probleme haben.

Ooru schrieb:

void pruef(int zeile, int spalte, int i, int n){
    if (zeile >= 0 && spalte >= 0 && zeile < n && spalte < n && pruefw <2){
        /*printf("Zeile: %d , Spalte: %d ",zeile,spalte);*/
        if (zeile == 0 && spalte == 0){
            /*printf("feld00: %d i: %d \n\n",feld[index(zeile,spalte)],i);*/
            if(feld[index(zeile,spalte)] == i){
              pruefw++;
              /*printf("Gleich00, pruefw: %d\n\n",pruefw);*/
              pruef(zeile-1,spalte-1,i,n);
            }
            pruef(zeile-1,spalte-1,i,n);
        }

Ist das nötig, dass in Zeile 9 und 11 der gleiche Code steht?

Und warum rufst du die Funktion nochmal auf, wenn zeile und spalte schon 0 sind?
Beim Aufruf steht dann pruef(-1,-1,i,n);
Die Funktion kommt dann gleich zurück. Dann brauchst du sie auch gar nicht erst aufrufen.

So etwas wird auch noch im Rest des Programms sein.

DirkB schrieb:
void pruef(int zeile, int spalte, int i, int n){
    if (zeile >= 0 && spalte >= 0 && zeile < n && spalte < n && pruefw <2){
        /*printf("Zeile: %d , Spalte: %d ",zeile,spalte);*/
        if (zeile == 0 && spalte == 0){
            /*printf("feld00: %d i: %d \n\n",feld[index(zeile,spalte)],i);*/
            if(feld[index(zeile,spalte)] == i){
              pruefw++;
              /*printf("Gleich00, pruefw: %d\n\n",pruefw);*/
              pruef(zeile-1,spalte-1,i,n);
            }
            pruef(zeile-1,spalte-1,i,n);
        }
Ist das nötig, dass in Zeile 9 und 11 der gleiche Code steht?

Und warum rufst du die Funktion nochmal auf, wenn zeile und spalte schon 0 sind?
Beim Aufruf steht dann pruef(-1,-1,i,n);
Die Funktion kommt dann gleich zurück. Dann brauchst du sie auch gar nicht erst aufrufen.

So etwas wird auch noch im Rest des Programms sein.

Ja hast du absolut recht ist total unnötig. Hab es gerade getestet. Da hab ich mir wohl evtl viele Fehler erlaubt

Wenn du noch was siehst was dir auffällt poste es bitte. Ich kann nicht von dir verlangen das ganze Programm durch zu gehen aber schonmal vielen Dank dafür.

Hast mir schon einige Fehler aufgezeigt.

Bei n=4 sollte die Rekursionstiefe eigentlich maximal nur 16 sein fuer jede Zahl im magischem Quadrat. Die Summe sollte nochmals 4 tief werden. Mit einer Rekursionstiefe von 20 sollte kein Stack Probleme haben.

Hm ergibt sinn allerdings denke ich das die Rekursionstiefe durch die pruefw Funktion zu groß wird. Vermutlich liegt da mein Problem.

Danke dir.

Ooru schrieb:

Hm ergibt sinn allerdings denke ich das die Rekursionstiefe durch die pruefw Funktion zu groß wird. Vermutlich liegt da mein Problem.

Danke dir.

Die Aufrufe werden doch in eingabe gezählt.
Du rufst eingabe also schon 35452 mal auf. Das ist auch schon ein bisschen viel.

Die Zeilen/Spaltensumme ist doch bekannt (hängt von n ab)
Sobald die Summe einmal nicht stimmt kannst du den Versuch doch schon abbrechen.

Hm ich denk ich werds einfach nochmal komplett neu angehen.

Allerdings gibt es für n=4 worauf sich meine Angabe bezogen hat 16! Permutationen da sind 35.000 nicht gerade viel. Und ja ich breche aktuell ja ab sobald es nicht passt oder rufe viel mehr die funktion neu auf mit geänderten i wert.

Ok. Soweit bin ich da nicht durchgestiegen.
Aber bei 16! kommst du mit einem int nicht weit. Da gibt es bei 13! schon einen Überlauf.

Du kannst ja noch einen Paramter an die Funktion übergeben (Beispiel an deinem jetzigen Code, der ja nicht optimal ist):

eingabe(int zeile, int spalte, int i, int n, int tiefe){  // tiefe als neuen Parameter.
        printf("Versuch: %7d Tiefe %2d\n", j, tiefe);
        j++;

....
       eingabe(...., tiefe+1); // beim Aufruf nächste Ebene

Dann kannst du Rekursionstiefe verfolgen.