Springer(Schach) minimaler Weg gesucht

N

Nico1989

Mitglied
Hi!

Ich hab mich wiedermal an ein Beispiel getraut. Ich zerbreche jedoch ziemlich daran.

Wie es der Titel verrät soll ein C Programm erstellt werden das den minimalen Weg von einem beliebigen Feld eines Schachbrettes(8x8) zu einem beliebigen Zielfeld berechnet, sprich die Anzahl der benötigten Sprünge.

Mein Lösungsansatz bis jetzt:
Felder teile ich in x und y Koordinaten

(1,1) ist ganz links unten, (8,8) ganz rechts oben.

Ein Springer bedroht bis zu 8 umliegende Felder.
Also je Feld habe ich dann 8 Möglichkeiten um weiterzuspringen.

Ich dachte zunächst an Backtracking wie zb. auch bei dem n-Damen Problem verfahren wird.
Doch irgendwie find ich nicht die richtige Brücke zu meinem Problem.

Das einfachste Verfahren das natürlich gleichzeitig ineffizient ist, wäre alle Möglichkeiten auszuprobiern und die Sprünge mitzählen, daraus könnte man die minimalste Sprunganzahl zum Weg herrausfinden. Damit würd ich mich auch voll und ganz zufrieden geben. Ich hab jedoch keine Idee wie ich das Formulieren soll. :/

Ich bin für jeden Denkansatz dankbar !

Mfg
Nico
 
Hi

auch nicht "die" optimale Lösung, aber wesentlich besser als Bruteforce:
Prinzip von Algo. von Dijkstra/Ford für kürzeste Graphenwege:

Ich hoffe, du bist nicht beleidigt, wenn du "fertigen" Pseudocode bekommst.
Eigentlich sollte ich ja keine Fertiglösungen geben,
aber a) ists ja nicht wirklich fertig und b) find ich sowas einfach viel zu lustig zu programmieren :D
Moment...edit: Sorry, doch nicht gleich.
Falls es kein anderer machen will, ich komm in ca. 2 Stunden wieder dazu.
 
sheel hat gesagt.:
Hi

auch nicht "die" optimale Lösung, aber wesentlich besser als Bruteforce:
Prinzip von Algo. von Dijkstra/Ford für kürzeste Graphenwege:

Ich hoffe, du bist nicht beleidigt, wenn du "fertigen" Pseudocode bekommst.
Eigentlich sollte ich ja keine Fertiglösungen geben,
aber a) ists ja nicht wirklich fertig und b) find ich sowas einfach viel zu lustig zu programmieren :D
Moment...edit: Sorry, doch nicht gleich.
Falls es kein anderer machen will, ich komm in ca. 2 Stunden wieder dazu.
Zum Vergrößern anklicken....

Nein beleidigt bin ich keines wegs, solange das Verständis dafür vorhanden ist :) ich sag schonmal danke falls du zeit findest für eine kleine Erklärung !
 
So, verspätet aber doch
Und es wurde doch C :D
Variablennamen etc. sind natürlich beliebig anpassbar

calc aufrufen mit
Koordinaten x,y vom Schachfeld mit dem Springer
(jeweils 1-8. x ist in am Brett A-H, y die 1-8-Richtung)
x,y vom Zielfeld
und ein 128-char-Array für das Ergebnis.

Immer in zwei char im Array sind dann für x,y von einem Feld des kürzesten Weges.
Quellfeld und Zielfeld inklusive.
Der Returnwert ist, wieviel char drin sind (also zweimal so viel Koordinaten belegt).
"Kein Sprung nötig" wäre 2 (weil Quellfeld selbst drin), einer 4 usw...

Der Code ist wie gesagt nicht ausprobiert,
und eher einfach statt möglichst schnell/speichersparend
C: 
struct Node
{
    signed char prev;
	signed char active;
	signed char visited;
};

int destination(const struct Node *board, int index)
{
	int ret = 0;
	while(board[index].prev >= 0)
	{
		index = board[index].prev;
		ret++;
	}
	return ret;
}

char reassign(struct Node *board, int src, int dst)
{
	if(!board[dst].visited)
	{
		board[dst].visited = 1;
		board[dst].active = 1;
		board[dst].prev = src;
		return 1;
	}
	else if((destination(board, src) + 1) < destination(board, dst))
		board[dst].prev = src;
	return 0;
}

char moves(struct Node *board, int src)
{
	int ret = 0;
	if(src >= 8)
	{
		if(src >= 16)
		{
			if((src % 8) > 0) ret += reassign(board, src, src - 17);
			if((src % 8) < 7) ret += reassign(board, src, src - 15);
		}
		if((src % 8) > 1) ret += reassign(board, src, src - 10);
		if((src % 8) < 6) ret += reassign(board, src, src - 6);
	}
	if(src < 56)
	{
		if(src < 48)
		{
			if((src % 8) > 0) ret += reassign(board, src, src + 15);
			if((src % 8) < 7) ret += reassign(board, src, src + 17);
		}
		if((src % 8) > 1) ret += reassign(board, src, src + 6);
		if((src % 8) < 6) ret += reassign(board, src, src + 10);
	}
	return ret;
}

int calc(char srcX, char srcY, char dstX, char dstY, char *result)
{
	int i, j, k;
	struct Node board[64];

	/*init*/
	for(i = 0; i < 64;  i++)
	{
		board[i].visited = 0;
		board[i].active = 0;
	}
	i = (srcX - 1) * 8 + srcY - 1;
	board[i].visited = 1;
	board[i].active = 1;
	board[i].prev = -1;

	/*calculation*/
	k = 1;
	while(k < 64)
	{
		for(j = 0; j < 64; j++)
		{
			if(board[j].active)
			{
				k += moves(board, j);
				board[j].active = 0;
			}
		}
	}

	/*save result*/
	i = (dstX - 1) * 8 + dstY - 1;
	k = (destination(board, i) + 1) * 2;
	if(result)
	{
		j = k - 1;
		while(j >= 0)
		{
			result[j--] = (char)((i % 8) + 1);
			result[j--] = (char)((i / 8) + 1);
			i = board[i].prev;
		}
	}
	return k;
}
 
Ja genau.

Prinzip in etwa:
Man kann pro Schachfeld speichern, ob es schon abgearbeitet ist
und welches andere Feld ein "Vorgänger" ist.

Man beginnt am Startfeld und speichert für alle Felder,
die man mit einem Sprung davon erreichen kann, dass der Vorgänger das Startfeld ist.
Für die neu dazugekommen Felder macht man jeweils (einzeln) das Selbe,
also jedes von X erreichbare Feld Y bekommt als Vorgänger X.
Für alle neu dazugekommenen Y wieder das selbe...

Dabei kann man vorerst annehmen, dass der kürzeste Weg (am wenigsten Sprünge)
von irgendeinem besuchten Feld zum Startfeld genau über die Vorgängerfelder geht.
Also Feld, sein Vorgänger, davon wieder der Vorgänger... bis man am Startfeld ist.
Da man keinen anderen Weg kennt ist das (noch) der Kürzeste.

Das Wichtigste am Ganzen ist aber der Fall (der sicher auftreten wird),
wenn man während der Felderuntersuchungen von einem X aus zu einem Y springen könnte,
dass aber vorher schon mal besucht wurde und schon einen Vorgänger hat.
Jetzt hat man zwei verschiedene Wege vom Start zu Feld Y.
Dabei wird dann für beide Wegen abgezählt, wie viel Sprünge sie benötigen,
der Kürzere davon ist der Richtige (und Y bekommt dann den Vorgänger zugewiesen,
der zum kürzeren Weg passt)

Wenn man alle 64 Felder min. einmal besucht hat ist man fertig.
Vom Zielfeld weg immer Vorgänger, davon Vorgänger usw. kommt man zum Startfeld
und hat dabei garantiert den kürzestmöglichen Weg zurückgelegt
(zwar verkehrt vom Ende zum Start, aber trotzdem)

Ein paar Sachen zum Code noch, die vermutlich am Undurchsichtigsten sind:

Sowas: (srcX - 1) * 8 + srcY - 1
ist nur dazu da, um die Schachbrettkoordinaten wie 2. Zeile, 4. Spalte
in eine einzelne Nummern von 0 bis 63 umzurechnen (damit ists einfacher zu programmieren)

In moves: Diese ganze if und -17, -15 usw. sind dazu da,
um die möglichen Sprünge von einem Schachfeld aus (in 0-63-"Koordinaten") zu ermitteln
(die if dabei deswegen, falls man in Randnähe steht. Dann ist ja nicht alles möglich)

"active" sind die Felder, die in der letzten Runde der Untersuchung dazugekommen sind.

Und das Zeug unter /*save result*/ ist nur, um das result-Array zu füllen,
also die ganze Vorgängerkette als tatsächliche Feldkoordianten abzuspeichern
(und die Koordianten werden auch wieder zurück umgerechnet in die Form,
wie sie an calc übergeben werden)
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück