Springerproblem Problem

[Odatas]

Hey Leute auch ich hab mich mal an das Springerprbolem gemacht und ein Problem gefunden.

Also folgendes Problem ich finde für 6x6 Felder sofort Lösungen es dauert keine 5 Minuten und ich habe schon über 100.000 Lösungen. Also da funktioniert der Algorithmus.

Ich wollte mal für ein 8x8 Feld einen Pfad berechnen aber auch nach Knapp 10 Stunden Berechnung kein einziger Pfad. Das lässt mich dann doch daran zweifeln ob mein Algorithmus richtig ist.

Ok ich weiß das mein Code vielleicht nicht der beste ist. Habt etwas Nachsicht. Ich schätze mal der Fehler liegt in den Regeln und deshalb hier der Generelle Gedanke zu den Regeln. Im Grunde muss ich drauf achten dass ich nich aus dem Spielfeld rausspringe. Deshalb habe ich mein Array doppelt so lang wie die Anzahl der Spielfelder gemacht und die Spielfelder durchnummeriert. Ich schau mir dann einfach die Nummerierung an die ich in der variable "rechner" abspeicher.

Am beispiel von der ersten Regel die 2 Sprunge nach oben und einen Nach Links vertretten soll.

Ich hab mich gefragt wann darf ich den Sprung nicht machen? Naheliegend ist das ich 2 Felder nach oben frei haben muss und 1 Feld nach links. Ich hab also erstmal mit 2*N einfach geschaut ob genügend felder im array sind. Genauer gesagt habe ich geschaut ob rechner groß genug ist sprich beim 6x6 Feld muss Rechner größer als 12 Felder sein. So habe ich immer die Ränder nach oben und unten des Spielfeldes geprüft. Ob ich zu nahe an der Seite stehe habe ich mit dem Modul operator geschaut. Den Sprung der ersten Regel darf ich wann nicht machen genau wenn ich in der ersten Spalte im spielfeld bin. Also darf ich den Nicht machen wenn ich rechner%N (N ist Spielfäldlänge) =1 ist.

So habe ich dann alle Regeln implementiert. Vielleicht nicht die beste Lösung aber es scheint ja zu funktionieren. Dachte ich zumindest bei einem 6x6 Feld....aber 10 Stunden einen Rechner laufen lassen für einen Einzigen Pafad eines 8x8 Feldes finde ich ein bisschen lange.

Ich habe das Programm zwar so geschrieben dass es durch das define mit N auf ein beliebig großes Feld angepasst werden soll. Aber ich denke genau da habe ich irgend einen Fehler gemacht der dafür sorgt das es bei 8x8 nicht mehr funktioniert.

Ich hoffe das sind alles infos die ihr braucht. Danke schonmal für Hilfe

#include <stdio.h>
#define N 6

long int final=0; //Zaehler damit man sehen kann ob was passiert
int p=-1,q=0;//Noch ein paar andere Zähler

int fuellen (int *feld) //Nummeriert das Array durch. Funktioniert.
{
	int i=N*N;
	feld ++;//Die durchnumerierung befindet sich immer auf dem 2. Feld. Das erste Feld ist für den Wert. 
	int j=1;
	i++;
	while (j<i+1)
	{
		*feld=j;
		feld++;
		feld++;
		j++;
	}

return 0;
}

int zeichnen (int *a)// Zeichnet das Feld. Funzt auch gut.
{
	int zahl=N, i=0,j=0;
	printf(" ");
	while(i<zahl)
	{
	printf(" %d ",i+1);	
	i++;
	}
	i=0;
	printf("\n  ");
	while (i<zahl)
	{
	printf("---");
	i++;
	}
	i=0;
	while (i<zahl)
	{
		printf("\n%d",i+1);
		while (j<zahl)
		{
			if (*a<10)
			printf("|%d ",*a);
			else
				printf("|%d",*a);
			 j++;
			 a++;
			 a++;
		}
		printf("|");
	i++;
	j=0;
	printf("\n  ");
	while (j<zahl)
	{
	printf("---");
	j++;
	}
	j=0;
	}
	i=0;
	printf("\n  ");
	return 0;
}

int zug (int *feld, int *nullter, int *letzter)
{
	int i=*feld,j=0;  // j als Zählvariable i bekommt die Nummer des Schrittes der als letztes gemacht wurde und von dem nun der neue Schritt gesucht wird..
	int *momentan=feld;//einen Pointer für das momentane Feld.
	//Feld wird
	if (final%50000000000==0)//Wenn die Funktion 50.000.000.000 aufgerufen wurde wird einmal die Schleife durchgelaufen.
	{
		feld=nullter;//Feld wird auf NUll gesetzt da beim Zeichen der Pointer auf das erste Element zeigen muss.
		p++;// Zähler ein Hoch
		printf("Schon %d 50 Milliarden Funktionen aufgerufen\n\n",p);
		zeichnen(feld);//Feld wird einmal ausgegeben
		final=0;//Final wieder auf los so werden Wrap arounds verhindert.
		feld=momentan;//Feld wieder aufs momentane Feld
	}
	final++;
	feld++;//Feld wird auf die Nummerierung des Feldes geschoben
	int rechner=*feld;//Nummerierung des Feldes wird ausgelesen.
	feld--; //Feld wieder auf den Wert.
	i++;//i wird nur gebraucht um ggf einen neuen Pfad im Springerpfad zu makieren deshalb einen weiter
	if (*feld==N*N)//Sollte schon der letzte Schritt im Springerfad gefunden sein so greift diese if schleife.
	{  
		q++;//q für die Anzahl der Gefundenen Springerpfade hochzählen
		printf("Gefunden %d\n",q);
		//printf(" EIN SPRINGEPFAD IST GEFUNDEN");
		//feld=nullter;
		//zeichnen(feld);//feld wird ausgegeben
		//getchar();
		//feld=momentan;//feld wird auf das momentane gesetzt
		*feld=0;//und es wird eine Null reingeschrieben also der Pfad wieder unmakiert
		return(0);//funktion wird beendet
	}
	if ((rechner%N)!=1&&rechner>(2*N))//Erste Regel soll 2 Schritte nach oben und 1 Schritt nach Links bewegen. Für Regelerklärung Grundlegende Erklärung beachten
	{ //printf("\nRegel 1\n");
	while (j<2*N+1)//Regel erklärung beachten
	{
		j++;
		feld--;
		feld--;//Wenn nicht wird ein Feld hoch geschaltet (2 Felder wegen Nummerierung)

	}

	if (*feld==0)//Wenn eine 0 im Feld ist es also Leer ist wird der nächste Schritt reingeschrieben und die Funktion für den nächstne Schritt geöffnet
	{
		*feld=i;
		zug (feld,nullter,letzter);
		feld=momentan;//Wenn die Rückgabe erfolgt ist eine Sackgasse erreicht. Um die nächste Regel zu testen muss wieder aufs Momentanen feld gegangen werden
	}
	feld=momentan;//Wenn keine Null im Feld ist muss trozdem auf das Feld zurück.
	j=0;
	}
	if((rechner%N)!=0&&rechner>(2*N-2))//2 Schritte nach oben ein Schrit nach Rechts
	{//printf("\nRegel 2\n");
			while (j<2*N-1)//Regel 2 Wird implementiert
	{
		j++;
		feld--;
		feld--;//Wenn nicht wird ein Feld hoch geschaltet

	}
	if (*feld==0)
	{
		*feld=i;
		zug (feld,nullter,letzter);
		feld=momentan;
	}
	feld=momentan;
	j=0;
	}
	if((rechner%N)!=1&&rechner%N!=2&&rechner>(N+1))//2 nach links 1 nach oben
	{//printf("\nRegel 3\n");
	while (j<N+2)//Regel 3 Wird implementiert
	{
		j++;		
		feld--;
		feld--;//Wenn nicht wird ein Feld hoch geschaltet
	}
	if (*feld==0)
	{
		*feld=i;
		zug (feld,nullter,letzter);
		feld=momentan;
	}
	feld=momentan;
	j=0;
	}
	if((rechner%N)!=N-1&&(rechner%N)!=0&&rechner>(N-3))//2 nach Rechts 1 nach oben
	{//printf("\nRegel 4\n");
	while (j<N-2)//Regel 4 Wird implementiert
	{
		j++;
		feld--;
		feld--;//Wenn nicht wird ein Feld hoch geschaltet

	}
	if (*feld==0)
	{
		*feld=i;
		zug (feld,nullter,letzter);
		feld=momentan;
	}
	feld=momentan;
	j=0;
	}	
	if((rechner%N)!=0&&rechner<((N*N)-(2*N)))//2 nach unten 1 nach Rechts
	{//printf("\nRegel 5\n");
	while (j<2*N+1)//Regel 5 Wird implementiert
	{
		j++;
		feld++;
		feld++;//Wenn nicht wird ein Feld runter geschaltet

	}
	if (*feld==0)
	{
		*feld=i;
		zug (feld,nullter,letzter);
		feld=momentan;
	}
	feld=momentan;
	j=0;
	}
	if((rechner%N)!=1&&rechner<((N*N)-(2*N-1)))//2 nach unten 1 nach links
	{//printf("\nRegel 6\n");
	while (j<2*N-1)//Regel 6 Wird implementiert
	{
		j++;
		feld++;
		feld++;//Wenn nicht wird ein Feld hoch geschaltet
	}
	if (*feld==0)
	{
		*feld=i;
		zug (feld,nullter,letzter);
		feld=momentan;
	}
	feld=momentan;
	j=0;
	}
	if((rechner%N)!=0&&(rechner%N)!=N-1&&rechner<((N*N)-(N-1)))//2 nach rechts 1 nach unten
	{//printf("\nRegel 7\n");
	while (j<N+2)//Regel 7 Wird implementiert
	{
		j++;
		feld++;
		feld++;//Wenn nicht wird ein Feld hoch geschaltet
	}
	if (*feld==0)
	{
		*feld=i;
		zug (feld,nullter,letzter);
		feld=momentan;
	}
	feld=momentan;
	j=0;
	}
	if((rechner%N)!=1&&(rechner%N)!=2&&rechner<(N*N-N))//2 nach links 1 nach unten
	{//printf("\nRegel 8\n");
	while (j<N-2)//Regel 8 Wird implementiert
	{
		j++;
		feld++;
		feld++;//Wenn nicht wird ein Feld runter geschaltet
	}
	if (*feld==0)
	{
		*feld=i;
		zug (feld,nullter,letzter);
		feld=momentan;
	}
	j=0;
	}
	feld=momentan;//sind alle Regeln versucht haben wir ne Sackgasse erreicht. Der Wert des Feldes wird auf 0 gesetzt und die Funktion wird zurück gegeben.
	*feld=0;
	return 0;
}

int main ()
{
int bla[2*(N*N)]={ 0 };//Das Array muss doppelt so lang sein wie die Anzahl der Felder wegen der Nummerierung
int *feld=&bla[0];//Ein Zeiger für das Feld
int *nullter=&bla[0];//Ein Zeiger für das Nullte Feld also das erste Array feld.
int *letzter=&bla[N*N-1];//Ein für den letzten Schritt -1 damit er auf dem Wert und nicht auf der Nummerierung steht
fuellen(feld);//Erstmal das Array füllen
feld=nullter;//Feld Pointer auf den ersten Wert
feld=feld+2;//2 Weiterschalten damit bei einem 8x8 Feld der Springer dort Startet wo im Schachspiel auch wirklich einer steht.
*feld=1;//Ersten Schritt reinschreiben.
zug(feld,nullter,letzter);//Und ab gehts

printf("ende");//Alles gefunden? einmal Ende bitte
getchar();//Aber nicht das Fenster schließen
return 0;
}

[SeppJ]

Der Code ist viel, viel zu kompliziert. Außerdem trotz Kommentaren für Außenstehende absolut unverständlich. Weißt du selber an jeder Stelle im Code, was überhaupt der momentane Zustand deiner Variablen ist? Hast du mal die 6x6-Lösungen kontrolliert, ob sie auch stimmen? Würde mich ehrlich gesagt wundern.

Im Grunde muss ich drauf achten dass ich nich aus dem Spielfeld rausspringe. Deshalb habe ich mein Array doppelt so lang wie die Anzahl der Spielfelder gemacht und die Spielfelder durchnummeriert. Ich schau mir dann einfach die Nummerierung an die ich in der variable "rechner" abspeicher.

Selbst wenn ich es verstehen würde, klingt es furchtbar kompliziert. Prüf doch einfach, ob eine Koordinate außerhalb eines 8x8-Feldes ist. Fertig.

Du hast auch dein ganzes Programm voll Stilblüten wie

feld++;
    int rechner=*feld;
    feld--;

Also int rechner = feld[1]; ? Dies ist, warum niemand deinen Code verstehen kann, das ist einfach total merkwürdig um drei Ecken gedacht, was eigentlich ganz einfach wäre. Ich wüde an deiner Stelle mal ordentlich Zeiger- und Arraysyntax pauken und dann das Programm nochmal lesbar schreiben. Dann kann man auch eventuelle Fehler finden, aber vermutlich wird es einfach sofort funktionieren.

[Odatas]

Ja ich versteh das das sehr kompliziert gedacht ist aber grade für die Überprüfung ob ich noch im Feld bin ist mir nichts besseres eingefallen.

Folgendes passiert im Hauptstück. Ich habe ein Array. Für jedes Feld auf dem Brett gibt es 2 Felder im Array. 1 Feld damit ich die Nummer des Schrittes reinschreibe (Für einen Springerpfad brauche ich ja die Reihenfolge der Züge. In das andere Feld wird einfach enie aufsteigende Nummerierung reingeschrieben. Damit ich die Positions der Felder identifizieren kann.

Beim Initialisieren sieht es dann so aus [0,1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9,....bis 0,N]

Wie du vielleicht gesehen hast funktioniert das Programm rekursiv. Das heißt sagen wir ich stehe auf dem 14. Feld was auf einem 8x8 Schachbrett Feld B 6 gleichkommen würde. Jetzt schreibe ich in das Feld hinein welchen Zug es darstellt. 20 z.b. das heißt auf dieses Feld wird der 20. Zug gemacht und gebe das dann an die Funktion (rekursiv) weiter.

Jetzt muss ich wissen welche Nummer das Feld auf meinem Brett hat. BZW muss ich ja im allgemeinen wissen von wo ich jetzt schauen soll wohin der nächste Zug gemacht wird. Und das mach ich mit der Nummerierung. Die Nummerierung ist immer 1 Schritt weiter als die Zugzahl. Deshalb schalte ich feld++; ein hoch nehme mir die Indentifikationsnummer für das Feld und dann wieder runter damit ich von da aus überprüfen kann wohin der andere Zug geht.

Ja ich weiß zu jeder Zeit was meine Variablen machen. Deshalb kann ich auch ziemlich genau sagen dass der Fehler in den Regeln liegen muss...wenn es den einen gibt und ich mit 10 Stunden laufzeit einfach noch nicht lange genug gewartet habe.

Schauen wir uns die erste Regel mal genauer an.

if ((rechner%N)!=1&&rechner>(2*N))//Erste Regel soll 2 Schritte nach oben und 1 Schritt nach Links bewegen. Für Regelerklärung Grundlegende Erklärung beachten
	{ //printf("\nRegel 1\n");
	while (j<2*N+1)//Regel erklärung beachten
	{
		j++;
		feld--;
		feld--;//Wenn nicht wird ein Feld hoch geschaltet (2 Felder wegen Nummerierung)

	}

	if (*feld==0)//Wenn eine 0 im Feld ist es also Leer ist wird der nächste Schritt reingeschrieben und die Funktion für den nächstne Schritt geöffnet
	{
		*feld=i;
		zug (feld,nullter,letzter);
		feld=momentan;//Wenn die Rückgabe erfolgt ist eine Sackgasse erreicht. Um die nächste Regel zu testen muss wieder aufs Momentanen feld gegangen werden
	}
	feld=momentan;//Wenn keine Null im Feld ist muss trozdem auf das Feld zurück.
	j=0;
	}

if ((rechner%N)!=1&&rechner>(2*N))//Erste Regel soll 2 Schritte nach oben

Diese if schleife kuckt sich an ob der Zug den ich machen will mich aus dem Spielfeld beförder würde. Also ob der Zug möglich ist.

rechner ist die Variable die die Identifikationsnummer des Spielfelds enthält.

Wir schauen uns hier den Zug 2 nach ob 1 nach Links an. Dieser Zug ist NICHT möglich wenn ich schon in der ganz Linken Spielfeldspalte stehe.

In dem ich

rechner%N

Bekomme ich raus in welcher Spalte das Spielfeld ist. Bei einem 6x6 Spielfeld und dem Feld mit der Nr 14 würdwe ich ja 14%6 haben. Heißt er sagt mir 2=14%6

Das wäre ok ich darf den Zug überall machen ausser in der ersten Spalte. Das heißt wann immer rechner%N=1 darf ich den Zug NICHT machen.

Deshalb:

(rechner%N)!=1

Außerdem mussen auch noch 2 Zeilen Spielfeld über mir frei sein. Wenn ich z.b. in Zeile B stehe kann ich den Zug nicht ausführen weil zeile a die letzte ist.

Wenn ich also jetzt bei einem 6x6 Spielfeld meine Feldidentifikationsnnumer anschaue muss sie größer sein als 2*6 = 2 Zeilen des Spielfelds.

Deshalb :

&&rechner>(2*N)

2*N<2+N+1.

Mein Zug der 2 Sprünge nach oben macht muss also 2 Zeilen überwinden was gleich 2+N bedeutet und dann noch einen Sprung nach Links machen. Da ich rückwärts zählen muss bei Sprüngen nach oben heißt das 2+N+1.

while (j<2*N+1)
	{
		j++;
		feld--;
		feld--;

	}

j ist einfach die Zählvariable und ich muss imm 2 Felder nehmen weil ja immer einmal Feld und einmal Indentifikationsnummer kommt.

if (*feld==0)
	{
		*feld=i;
		zug (feld,nullter,letzter);
		feld=momentan;
	}

Nachdem ich überprüft habe ob der Sprung möglich ist und auf das Feld gegangen bin wo der Sprung hingehen soll muss ich noch Prüfen ob ich das Feld vorher schon einmal besucht habe.

Das mache ich in dem ich schaue ob eine 0 in dem Feld steht was bedeutet würde dass ich das Feld vorher noch NICHT betretten habe. Steht eine andere Zahl drin war ich schon auf dem Feld wohin der Zug gehen soll und er wird einfach nicht ausgeführt

feld=momentan;

Damit ich die nächste Regel prüfen kann muss ich jetzt wieder auf das Uhrsprungsfeld gehen.

Diese erklärung geht für die anderen 7 Regeln Analog.

Ich schreibe keinen eleganten Code wie man sieht aber momentan kann ich es einfach nicht besser. Ich würd auch verstehen wenn sich keiner von euch die Mühe machen will den ganzen Murks durchzugehen. Würde mich aber trozdem freuen.

Vielen Dank auf jeden Fall schonmal für die Mühe

[SeppJ]

Hier hast du ein kleines Progrämmchen, welches auch Backtracking für das Springerproblem benutzt und das ich gerade schnell zusammengeschrieben habe. Beziehungsweise so schnell war es nicht, denn ich hatte das gleiche Problem wie du: Bis 7x7 geht es noch halbwegs, aber 8x8 dauert ewig lange. Da habe ich mal andere Beispielprogramme angesehen und bemerkt, dass diese die Startposition und Ausprobierreihenfolge geschickt wählen . Damit findet mein Programm die ersten paar Kombinationen sehr schnell, erst danach kommt das große Warten.

Du kannst aus diesem Programm folgendes lernen:
- Anfangen in einer Ecke (Zeile 62)ist geschickt gewählt.
- Die Zugreihenfolge (Zeile 11) ist geschickt gewählt.
- Du kannst ja mal rumspielen, wie lange die erste Lösung bei anderen Werten auf sich warten lässt. Mir war es nach ein paar Minuten zu doof. Backtracking ist für das Springerproblem eben einfach nicht gut genug.
- Insgesamt sollte dich das Programm inspirieren, wie man vieles geschickter machen kann. Ganz besonders das Umsetzen der Regeln! All die Regeln sind bei mir in Zeilen 11, 16, 48 und 49. Bei dir brauchst du für das gleiche über 100 Zeilen!

#include <stdio.h>
#include <stdbool.h>

#define N 8

typedef struct
{
  int x, y;
} Move;

static Move possible_moves[8] = {{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};

bool is_valid(int new_x, int new_y, int field[N][N])
{
  return (new_x >= 0 && new_x < N && new_y >= 0 && new_y < N && field[new_x][new_y] == 0 );
}

void print_field(int field[N][N])
{
  int x, y;
  for (y = 0; y < 3*N + 1; ++y) putchar('-');
  putchar('\n');
  for (x = 0; x < N; ++x)
    {
      putchar('|');
      for (y = 0; y < N; ++y)
        {
          printf("%2d|", field[x][y]);
        }
      putchar('\n');
      for (y = 0; y < 3*N + 1; ++y) putchar('-');
      putchar('\n');
    }
}

void solve_KT(int pos_x, int pos_y, int current_depth, int field[N][N])
{
  int which_move;
  if (current_depth == N*N + 1)
    {
      puts("Found a solution:");
      print_field(field);
    }
  else
    for (which_move = 0; which_move < sizeof(possible_moves)/sizeof(*possible_moves); ++which_move)
      {
        int new_x = pos_x + possible_moves[which_move].x;
        int new_y = pos_y + possible_moves[which_move].y;
        if (is_valid(new_x, new_y, field))
          {
            field[new_x][new_y] = current_depth;
            solve_KT(new_x, new_y, current_depth + 1, field);
            field[new_x][new_y] = 0;
          }
      }
}

int main()
{
  int field[N][N] = {};
  int start_x = 0, start_y = 0;
  field[start_x][start_y] = 1;
  puts("Starting configuration:");
  print_field(field);
  solve_KT(start_x, start_y, 2, field);
  return 0;
}

[Odatas]

Danke für das Beispiel. Ich werd mich da mal einarbeiten und ein wenig mehr versuchen diese "Elegante" programmiermethodig zu nutzen

[SeppJ]

Odatas schrieb:

Danke für das Beispiel. Ich werd mich da mal einarbeiten und ein wenig mehr versuchen diese "Elegante" programmiermethodig zu nutzen

Naja, "elegant" würde ich meines nicht nennen, dafür habe ich zu wenig Zeit investiert. Aber wie wäre es mit "lesbar"? Ich wette, mehr Leute verstehen meinen Code als deinen, obwohl dein Programm mehr Kommentar als Code enthält, meines hingegen nicht eine Zeile Kommentar.

[Allesquatsch]

SeppJ schrieb:

- Anfangen in einer Ecke (Zeile 62)ist geschickt gewählt.

Was aber von der genauen Problemstellung abhängt. Wenn nur geschlossene Wege gesucht werden, ist das Anfangsfeld eigentlich egal.
Wenn jedoch auch offene Wege zulässig sind oder Lösungen gar nur unter den offenen zu finden sind, muss das Startfeld variiert werden.

Wenn man die Möglichkeiten des Springers und die quadratische Form berücksichtigt, braucht man nicht alle Felder als Startfelder austesten. Wegen der dreifachen Achsensymmetrie (waagerecht, senkrecht, diagonal) reicht bereits ein großzügiges Achtel des Feldes, um auch offene Wege zu finden:

int main()
{
  int field[N][N] = {};
  int start_x,start_y;
  for (start_x = 0; start_x*2 < N; start_x++)
    for (start_y = 0; start_y <= start_x; start_y++)
      {
      field[start_x][start_y] = 1;
      puts("Starting configuration:");
      print_field(field);
      solve_KT(start_x, start_y, 2, field);
      field[start_x][start_y] = 0;
      }
  return 0;
}

Ciao, Allesquatsch