vbInside - Das Springerproblem

Ein Springer soll nach den normalen Regeln dafür, wie er im Schach zieht, auf einem n*n großen Spielfeld von beliebiger Startposition so springen, dass er jede Position genau einmal - nicht mehr und nicht weniger - berührt.

Wieso n*n? Ein Schachfeld hat genau 8*8 Felder! - Richtig, aber auf einem 8*8 großen Feld werden die Zeiten für das Finden einer einzigen Lösung sehr, sehr groß. Es gibt dann nämlich 8^64 Möglichkeiten, die der Computer durchrechnen muss (8 Möglichkeiten zu springen, dies bei jedem Zug bis das Brett voll ist; also 8^Anzahl der Positionen auf dem Brett = 8^64). Man nimmt darum generell ein n*n großes Feld, damit man auch funktionierende Ergebnisse beobachten kann.

Im Beispielprogramm wurden für n Werte von 4 bis Acht möglich gemacht. Jeder kann sich sehr schnell überlegen, dass es für ein 1*1 großes Feld genau eine recht uninteressant zu berechnende Lösung gibt, für das 2*2 Feld gibt es keine, genausowenig wie für das 3*3 große Feld (Der Springer startet entweder in der Mitte und kann sich von dort nirgendwohin bewegen, oder er wird die Mitte von irgendwo anders her niemals erreichen). Für das 4*4 große Feld ist es unmöglich im Kopf nachzuvollziehen, ob es eine Lösung gibt. Wie das Programm nachher zeigt, gibt es keine.

Doch nun zur Funktionsweise von Backtrackingalgorithmen: Der Trick ist, jede Möglichkeit, die es gibt, mit Hilfe einer rekursiven Funktion oder Prozedur (in diesem Fall Prozedur) durchzurechnen und sich die letztendlich funktionierenden Lösungen zu merken.

In diesem Fall sähe das so aus: Ich suche mir eine Startposition für den Springer. Von da aus gehe ich der Reihe nach alle 8 Möglichkeiten ab, die der Springer setzen kann. Von jenen angegangenen Möglichkeiten gehe ich ebenfalls jeweils 8 Möglichkeiten und so weiter. Jedesmal markiere ich dabei die Position, an der ich schon gewesen bin, damit ich nicht doppelt auf diese setzen kann. Wenn ich nun alle Möglichkeiten von einer Position aus versucht habe, so nehme ich den letzen Zug wieder zurück (ich lösche die Markierung), egal ob ich eine Lösung gefunden habe oder nicht. Auf diese Art und Weise werden wirklich alle Zugmöglichkeiten, die es gibt, ausprobiert und alle Lösungen werden gefunden.

Dieses an sich sehr simple Verfahren lässt sich für viele Probleme verwenden, beispielsweise auch die Wegsuche aus einem Labyrinth (Probiere alle Wege aus; bei Sackgasse geh zurück zum letzten Knoten und probier anderen Weg bis der Ausgang gefunden wurde). Es bildet auch die Grundlage für einfache künstliche Intelligenzen die mit dem sogenannten Alpha-Beta-Schnitt arbeiten.

History
25.06.2003 Hinzugefügt

Autor: Benjamin Schröder <Benny_auf_vbInside.de>

Code aus frmSpringer.frm Option Explicit
Dim N, SOLUTIONS, STARTX, STARTY As Integer
'N = Breite des Spielfelds
'SOLUTIONS = Anzahl der gefunden Lösungen * 8
'STARTX & STARTY = Startposition für die Springerbewegungen
Dim WEITER As Boolean
'Abbruchkontrolle für das Backtracking

Private Sub Springen(x, y, ZugNr As Integer)
'Die Backtrackingprozedur. Übergeben werden die Position, an
'die gesprungen werden soll sowie die Nummer des Zuges
If ZugNr = N ^ 2 Then
'Wenn alle Felder bereits besetzt sind (die Aufgabe ist _
erfolgreich beendet)

'Wenn man einfach nur SOLUTIONS anzeigen würde, so erhielte _
man für jeden Lösung 8 Ausgaben. Von der
'letzten möglichen Position, die besetzt wurde, wird nämlich _
die Prozedur noch 8mal aufgerufen. Daher
'ist die wirkliche Anzahl der Lösungen = SOLUTIONS / 8. Daher:
SOLUTIONS = SOLUTIONS + 1
'Bei jedem Aufruf mit vollem Brett erhöhen
If SOLUTIONS Mod 8 = 0 Then
'Sobald 8 zusammen sind eine Lösung ausspucken
List1.AddItem "Lösung gefunden! (Nr. " & SOLUTIONS / 8 & ")"
List1.Refresh
End If
Exit Sub
ElseIf x < Int(N) And y < Int(N) And x > -1 And y > -1 And _
WEITER Then
'Wenn die Werte innerhalb des Feldes
'und kein Abbruch gedrückt wurde
If Feld.TextMatrix(y, x) = "" Then
'Wenn ich an die jetzige Position setzen kann
Feld.TextMatrix(y, x) = ZugNr
'Setze den Springer um (zeige die Zugnummer im Feld an

Feld.Refresh
DoEvents

Springen x + 1, y - 2, ZugNr + 1
'Vom jetzigen Feld aus werden alle 8 Zugmöglichkeiten des _
Springers
Springen x + 2, y - 1, ZugNr + 1
'ausprobiert, der Reihenfolge nach von Oben-Rechts nach _
Oben-Links
Springen x + 2, y + 1, ZugNr + 1
'mit dem Uhrzeigersinn.
Springen x + 1, y + 2, ZugNr + 1
Springen x - 1, y + 2, ZugNr + 1
Springen x - 2, y + 1, ZugNr + 1
Springen x - 2, y - 1, ZugNr + 1
Springen x - 1, y - 2, ZugNr + 1
Feld.TextMatrix(y, x) = ""
'Sobald alle Zugmöglichkeiten ausprobiert worden sind wird _
der eigentliche
'Zug zurückgenommen.
End If
End If
End Sub

Private Sub Initialize()
'Initialisierungsprozedur für das Feld
Dim i As Integer

WEITER = True
STARTX = 0
'Defaultstartposition ist linke obere Ecke
STARTY = 0
Feld.Clear
Feld.Rows = N
'Größe des Feldes einstellen etc...
Feld.Cols = N
Feld.Height = N * 302
Feld.Width = N * 302

For i = 0 To Feld.Cols - 1
Feld.ColWidth(i) = 300
Feld.RowHeight(i) = 300
Next i

End Sub

Private Sub cmbN_Click()
'Zuweisung einer Größe für das Spielfeld aus N*N Feldern
N = cmbN.Text
Initialize
End Sub

Private Sub cmdEnde_Click()
Unload Me
End
End Sub

Private Sub cmdStart_Click()
Feld.Clear
'Initialisierungen
List1.Clear
Feld.Enabled = False
'Bedienung wird für den Vorgang des Backtrackings deaktiviert _
-> Stichwort Dummyproof :)
cmdStart.Enabled = False
cmbN.Enabled = False
cmdEnde.Enabled = False

lbldesc.Caption = "Backtracking..."
lbldesc.Enabled = False
lbldesc.Refresh

SOLUTIONS = 0
'SOLUTIONS-counter auf 0 setzen (ehm, sinnvoller Kommentar, äh :)

Springen STARTX, STARTY, 0
'Ab hier beginnt das Backtracking. Der nullte Zug geht auf die _
vorher
'definierte Startposition STARTX|STARTY, das bedeutet der _
Springer steht anfangs
'auf jener Position. Jede weiter Zahl gibt nun die Nummer des _
Zuges an, in dem
'der Springer die der Zahl entsprechende Position berührt hat.

WEITER = True
'Falls abgebrochen wurde wird die Abbruchbedingung wieder entfernt
STARTX = 0
'Die Startposition wird wieder auf den Default gesetzt
STARTY = 0
lbldesc.Enabled = True
'Bedienung ist nun wieder möglich
lbldesc.Caption = ""
Feld.Enabled = True
cmdStart.Enabled = True
cmbN.Enabled = True
cmdEnde.Enabled = True

End Sub

Private Sub cmdStop_Click()
WEITER = False
'Wenn während des Backtrackings auf Stop gedrückt wird, so _
werden alle Funktionsaufrufe
'abgebrochen werden, man kann so das Backtracking vorzeitig beenden.
End Sub

Private Sub Feld_Click()

STARTX = Feld.ColSel
'Durch Klick aufs Spielfeld wird eine Startposition definiert...
STARTY = Feld.RowSel

Feld.Clear
Feld.TextMatrix(STARTY, STARTX) = "0"

End Sub

Private Sub Form_Load()
Dim i As Integer
'Initialisierungskram

For i = 4 To 8
cmbN.AddItem i
Next i
cmbN.Text = "8"

N = cmbN.Text

Initialize
End Sub

'Ab hier ist nur noch die Textanzeige in dem Label ganz unten auf _
der Form

Private Sub cmdEnde_MouseMove(Button As Integer, Shift As Integer, _
x As Single, y As Single)
lbldesc.Caption = "Programm beenden."
End Sub

Private Sub cmdStart_MouseMove(Button As Integer, Shift As _
Integer, x As Single, y As Single)
lbldesc.Caption = "Backtracking mit eingegebenen Parametern " & _
"starten."
End Sub

Private Sub cmdStop_MouseMove(Button As Integer, Shift As Integer, _
x As Single, y As Single)
lbldesc.Caption = "Backtracking abbrechen."
End Sub

Private Sub Form_MouseMove(Button As Integer, Shift As Integer, x _
As Single, y As Single)
lbldesc.Caption = ""
End Sub

Private Sub lbldesc_MouseMove(Button As Integer, Shift As Integer, _
x As Single, y As Single)
lbldesc.Caption = ""
End Sub

Private Sub List1_MouseMove(Button As Integer, Shift As Integer, x _
As Single, y As Single)
lbldesc.Caption = "Gibt die Anzahl der Lösungen aus."
End Sub