Aufgrund von Marcus seinem Posting in diesem Thread dachte ich, dass das doch mal ein interessantes Problem sein könnte. Also habe ich mir einen kleinen auf Rekursion basierenden Algorhytmus gebastelt.
Das Ziel der Aufgabe ist, mit einem Springer, der auf einem Schachbrett beliebiger Größe an einem beliebigen Punkt steht, alle Felder des Schachbretts einmal zu betreten, keines darf doppelt betreten werden.
Der Ablauf ist immer folgender:
-Die aktuelle Position des Springers wird übergeben
-Alle möglichen Züge werden durchprobiert bis ein möglicher Zug gefunden wurde
-Der Zug wird ausgeführt (auf den Stack gelegt) und der Ablauf startet von vorne
-Wenn kein möglicher Zug gefunden wurde, wird einen Schritt zurück gegangen (der letzte Zug vom Stack genommen) und der Ablauf startet auch wieder von vorne
-Wenn die Aufgabe erfüllt ist (alle Felder abgefahren), wird der Vorgang abgebrochen.
Hier jedenfalls mein Ansatz:
Das Ziel der Aufgabe ist, mit einem Springer, der auf einem Schachbrett beliebiger Größe an einem beliebigen Punkt steht, alle Felder des Schachbretts einmal zu betreten, keines darf doppelt betreten werden.
Der Ablauf ist immer folgender:
-Die aktuelle Position des Springers wird übergeben
-Alle möglichen Züge werden durchprobiert bis ein möglicher Zug gefunden wurde
-Der Zug wird ausgeführt (auf den Stack gelegt) und der Ablauf startet von vorne
-Wenn kein möglicher Zug gefunden wurde, wird einen Schritt zurück gegangen (der letzte Zug vom Stack genommen) und der Ablauf startet auch wieder von vorne
-Wenn die Aufgabe erfüllt ist (alle Felder abgefahren), wird der Vorgang abgebrochen.
Hier jedenfalls mein Ansatz:
VB.NET-Quellcode
- Public Class Algorythm
- ''' <summary>
- ''' Eine Auflistung aller möglichen Bewegungen eines Springers
- ''' </summary>
- Private Shared MöglicheZüge As New List(Of Integer()) From {New Integer() {1, -2}, New Integer() {-1, -2}, New Integer() {2, 1}, New Integer() {2, -1}, _
- New Integer() {-1, 2}, New Integer() {1, 2}, New Integer() {-2, -1}, New Integer() {-2, 1}}
- ''' <summary>
- ''' Löst das Springerproblem
- ''' </summary>
- ''' <param name="fieldSize">Die Größe des Schachfeldes.</param>
- ''' <param name="buffer">Der Puffer für die Spielzüge.</param>
- Private Shared Sub Springerproblem(ByVal fieldSize As Size, ByRef buffer As Stack(Of Point))
- 'Geht alle Züge durch
- For Each Zug In MöglicheZüge
- 'Wenn die Lösung schon gefunden wurde, Vorgang abbrechen
- If buffer.Count = fieldSize.Width * fieldSize.Height Then
- Exit Sub
- End If
- 'Berechnet das Ziel des aktuell ausgewählten Zuges
- Dim ptZug As Point = New Point(buffer.Peek.X + Zug(0), buffer.Peek.Y + Zug(1))
- 'Überprüfen ob der aktuelle Zug möglich ist
- If ((ptZug.X <= fieldSize.Width AndAlso ptZug.X >= 1) AndAlso (ptZug.Y <= fieldSize.Height AndAlso ptZug.Y >= 1)) AndAlso (Not buffer.Contains(ptZug)) Then
- 'Zug zum Puffer hinzufügen
- buffer.Push(ptZug)
- 'Nächste Rekursionsstufe aufrufen
- Springerproblem(fieldSize, buffer)
- End If
- Next
- 'Wenn keine Bewegungsmöglichkeit gefunden wurde, einen Schritt zurück gehen
- buffer.Pop()
- End Sub
- ''' <summary>
- ''' Löst das Springerproblem
- ''' </summary>
- ''' <param name="fieldSize">Die Größe des Schachfeldes.</param>
- ''' <param name="start">Der Startpunkt des Springers.</param>
- ''' <returns>Die Züge die durchzuführen sind.</returns>
- Public Shared Function Springerproblem(ByVal fieldSize As Size, start As Point) As Stack(Of Point)
- 'Der Puffer in dem später alle Züge gespeichert werden
- Dim Buffer As New Stack(Of Point)
- 'Den Startpunkt zum Puffer hinzufügen
- Buffer.Push(start)
- 'Die Berechnung starten
- Springerproblem(fieldSize, Buffer)
- 'Wenn alle Berechnungen abgeschlossen sind, den Puffer zurückgeben
- Return Buffer
- End Function
- End Class