Springerproblem Algorithmus

    • VB.NET

    Es gibt 10 Antworten in diesem Thema. Der letzte Beitrag () ist von nafets3646.

      Springerproblem Algorithmus

      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:

      VB.NET-Quellcode

      1. Public Class Algorythm
      3. ''' <summary>
      4. ''' Eine Auflistung aller möglichen Bewegungen eines Springers
      5. ''' </summary>
      6. 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}, _
      7. New Integer() {-1, 2}, New Integer() {1, 2}, New Integer() {-2, -1}, New Integer() {-2, 1}}
      9. ''' <summary>
      10. ''' Löst das Springerproblem
      11. ''' </summary>
      12. ''' <param name="fieldSize">Die Größe des Schachfeldes.</param>
      13. ''' <param name="buffer">Der Puffer für die Spielzüge.</param>
      14. Private Shared Sub Springerproblem(ByVal fieldSize As Size, ByRef buffer As Stack(Of Point))
      15. 'Geht alle Züge durch
      16. For Each Zug In MöglicheZüge
      17. 'Wenn die Lösung schon gefunden wurde, Vorgang abbrechen
      18. If buffer.Count = fieldSize.Width * fieldSize.Height Then
      19. Exit Sub
      20. End If
      22. 'Berechnet das Ziel des aktuell ausgewählten Zuges
      23. Dim ptZug As Point = New Point(buffer.Peek.X + Zug(0), buffer.Peek.Y + Zug(1))
      25. 'Überprüfen ob der aktuelle Zug möglich ist
      26. If ((ptZug.X <= fieldSize.Width AndAlso ptZug.X >= 1) AndAlso (ptZug.Y <= fieldSize.Height AndAlso ptZug.Y >= 1)) AndAlso (Not buffer.Contains(ptZug)) Then
      27. 'Zug zum Puffer hinzufügen
      28. buffer.Push(ptZug)
      29. 'Nächste Rekursionsstufe aufrufen
      30. Springerproblem(fieldSize, buffer)
      31. End If
      32. Next
      33. 'Wenn keine Bewegungsmöglichkeit gefunden wurde, einen Schritt zurück gehen
      34. buffer.Pop()
      35. End Sub
      37. ''' <summary>
      38. ''' Löst das Springerproblem
      39. ''' </summary>
      40. ''' <param name="fieldSize">Die Größe des Schachfeldes.</param>
      41. ''' <param name="start">Der Startpunkt des Springers.</param>
      42. ''' <returns>Die Züge die durchzuführen sind.</returns>
      43. Public Shared Function Springerproblem(ByVal fieldSize As Size, start As Point) As Stack(Of Point)
      44. 'Der Puffer in dem später alle Züge gespeichert werden
      45. Dim Buffer As New Stack(Of Point)
      46. 'Den Startpunkt zum Puffer hinzufügen
      47. Buffer.Push(start)
      48. 'Die Berechnung starten
      49. Springerproblem(fieldSize, Buffer)
      50. 'Wenn alle Berechnungen abgeschlossen sind, den Puffer zurückgeben
      51. Return Buffer
      52. End Function
      54. End Class

      nafets3646 schrieb:

      der auf einem Schachbrett beliebiger Größe an einem beliebigen Punkt steht
      Fangen wir mit einem 3x3-Brett und der Mittelposition an. :D
      Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
      Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
      Ein guter .NET-Snippetkonverter (der ist verfügbar).
      Programmierfragen über PN / Konversation werden ignoriert!

      Es gibt noch eine Heuristik, dass der Springer, wenn es mehrere legale Möglichkeiten gibt, immer den Zug machen sollte, von dem aus er beim nächsten Zug am wenigsten legale Möglichkeiten hat. Wenn es davon mehrere mit derselben Anzahl gibt, würde ich den Zufall entscheiden lassen.

      Das könntest du noch implementieren, der Algorithmus sollte dann wesentlich schneller sein.

      Ich hab das jetzt mal umgesetzt, allerdings ist es noch deutlich langsamer als die erste Methode, um genau zu sein, ist es immer ungefähr um den Faktor 3. Getestet habe ich mit 6x6-Feldern und einem zufällig generierten Startpunkt für beide Methoden.
      Hier ist jedenfalls der Code:

      VB.NET-Quellcode

      1. Public Class AlgorythmV2
      3. ''' <summary>
      4. ''' Löst das Springerproblem
      5. ''' </summary>
      6. ''' <param name="fieldSize">Die Größe des Schachfeldes.</param>
      7. ''' <param name="buffer">Der Puffer für die Spielzüge.</param>
      8. Private Shared Sub Springerproblem(ByVal fieldSize As Size, ByRef buffer As Stack(Of Point))
      9. 'Alle möglichen Züge durchgehen
      10. For Each Zug In GetPossibleMovesSorted(fieldSize, buffer)
      11. 'Wenn die Lösung schon gefunden wurde, Vorgang abbrechen
      12. If buffer.Count = fieldSize.Width * fieldSize.Height Then
      13. Exit Sub
      14. End If
      15. 'Den Zug zum Puffer hinzufügen
      16. buffer.Push(Zug)
      17. 'Prüfen ob hiermit die Aufgabe gelöst ist
      18. If buffer.Count = fieldSize.Width * fieldSize.Height Then
      19. 'Wenn ja, die Sub verlassen
      20. Exit Sub
      21. Else
      22. 'Wenn nein, nächste Rekursionsstufe aufrufen
      23. Springerproblem(fieldSize, buffer)
      24. End If
      25. Next
      26. 'Wenn keine Bewegungsmöglichkeit gefunden wurde, einen Schritt zurück gehen
      27. buffer.Pop()
      28. End Sub
      30. ''' <summary>
      31. ''' Berechnet alle möglichen Züge und gibt diese sortiert zurück.
      32. ''' </summary>
      33. ''' <param name="fieldSize">Die Größe des Schachfeldes.</param>
      34. ''' <param name="buffer">Der Puffer für die Spielzüge</param>
      35. ''' <returns>Alle möglichen Züge, sortiert nach Relevanz.</returns>
      36. Private Shared Function GetPossibleMovesSorted(ByVal fieldSize As Size, ByVal buffer As Stack(Of Point)) As List(Of Point)
      37. 'Alle möglichen Züge mit Anzahl der als nächsten Schritt möglichen Züge
      38. Dim MöglicheZüge As New List(Of Tuple(Of Point, Integer))
      39. 'Alle möglichen Züge, sortiert nach Relevanz
      40. Dim MöglicheZügeSortiert As New List(Of Point)
      41. 'Alle möglichen Züge durchgehen
      42. For Each Zug As Point In GetPossibleMoves(fieldSize, buffer)
      43. 'Den Zügen ein neues Element hinzufügen: Ziel des Zuges, mögliche darauffolgende Züge
      44. MöglicheZüge.Add(Tuple.Create(Zug, GetPossibleMoves(fieldSize, buffer, Zug).Count))
      45. Next
      46. 'Die möglichen Züge nach der Anzahl der möglichen darauffolgenden Züge absteigend sortieren
      47. MöglicheZüge.OrderByDescending(Function(t) t.Item2)
      48. 'Alle sortierten Züge zur Liste 'MöglicheZügeSortiert' hinzufügen
      49. MöglicheZügeSortiert = MöglicheZüge.Select(Function(t) t.Item1).ToList
      50. 'Die möglichen Züge sortiert zurückgeben
      51. Return MöglicheZügeSortiert
      52. End Function
      54. ''' <summary>
      55. ''' Eine Auflistung aller möglichen Bewegungen eines Springers
      56. ''' </summary>
      57. Private Shared Züge As New List(Of Integer()) From {New Integer() {1, -2}, New Integer() {-1, -2}, New Integer() {2, 1}, New Integer() {2, -1}, _
      58. New Integer() {-1, 2}, New Integer() {1, 2}, New Integer() {-2, -1}, New Integer() {-2, 1}}
      59. ''' <summary>
      60. ''' Berechnet alle möglichen Züge.
      61. ''' </summary>
      62. ''' <param name="fieldSize">Die Größe des Schachfeldes.</param>
      63. ''' <param name="buffer">Der Puffer für die Spielzüge</param>
      64. ''' <returns>Alle möglichen Züge.</returns>
      65. Private Shared Function GetPossibleMoves(ByVal fieldSize As Size, ByVal buffer As Stack(Of Point)) As List(Of Point)
      66. Dim MöglicheZüge As New List(Of Point)
      67. 'Alle Züge durchgehen
      68. For Each Zug As Integer() In Züge
      69. 'Ziel des Zuges berechnen
      70. Dim ptZug As Point = New Point(buffer.Peek.X + Zug(0), buffer.Peek.Y + Zug(1))
      71. 'Prüfen, ob Zug möglich
      72. If ((ptZug.X <= fieldSize.Width AndAlso ptZug.X >= 1) AndAlso (ptZug.Y <= fieldSize.Height AndAlso ptZug.Y >= 1)) AndAlso (Not buffer.Contains(ptZug)) Then
      73. 'Wenn Zug möglich, Zug zur Liste hinzufügen
      74. MöglicheZüge.Add(ptZug)
      75. End If
      76. Next
      77. 'Die möglichen Züge zurückgeben
      78. Return MöglicheZüge
      79. End Function
      81. ''' <summary>
      82. ''' Berechnet alle möglichen Züge.
      83. ''' </summary>
      84. ''' <param name="fieldSize">Die Größe des Schachfeldes.</param>
      85. ''' <param name="buffer">Der Puffer für die Spielzüge</param>
      86. ''' <param name="position">Ein zusätzlicher Punkt</param>
      87. ''' <returns>Alle möglichen Züge.</returns>
      88. Private Shared Function GetPossibleMoves(ByVal fieldSize As Size, ByVal buffer As Stack(Of Point), ByVal position As Point) As List(Of Point)
      89. 'Den zusätzlichen Punkt zum Stack hinzufügen und den Rückgabewert der Funktion GetPossibleMoves(fieldSize, buffer) zurückgeben
      90. Return GetPossibleMoves(fieldSize, New Stack(Of Point)(buffer.Concat({position})))
      91. End Function
      93. ''' <summary>
      94. ''' Löst das Springerproblem
      95. ''' </summary>
      96. ''' <param name="fieldSize">Die Größe des Schachfeldes.</param>
      97. ''' <param name="start">Der Startpunkt des Springers.</param>
      98. ''' <returns>Die Züge die durchzuführen sind.</returns>
      99. Public Shared Function Springerproblem(ByVal fieldSize As Size, ByVal start As Point) As Stack(Of Point)
      100. 'Der Puffer in dem später alle Züge gespeichert werden
      101. Dim Buffer As New Stack(Of Point)
      102. 'Den Startpunkt zum Puffer hinzufügen
      103. Buffer.Push(start)
      104. 'Die Berechnung starten
      105. Springerproblem(fieldSize, Buffer)
      106. 'Wenn alle Berechnungen abgeschlossen sind, den Puffer zurückgeben
      107. Return Buffer
      108. End Function
      110. End Class

      Weiß jemand vielleicht, woran das liegen könnte, dass dieser Code so lange braucht?

      Ich weiß das ganze gehört wohl schon zum alten Eisen, aber wenn man mal etwas langeweile haben sollte, wäre eine grafische Darstellung wohl Nett anzusehen
      (Auch wenn das jetzt nicht wirklich Spektakulär wäre, wie sich da ein paar Felder einfärben und/oder eine Figur sich bewegt).

      Ich bin zwar kein Deutschlehrer, aber bitte: A-l-g-o-r-i-t-h-m-u-s :D
      Und auf Englisch: Algorithm ;)

      Desweiteren mal zum Code, ich empfehle dir, dich für eine Sprache zu entscheiden, Deutsch oder Englisch :)
      »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais

    Facebook
    Telefonspende