Haben Sie jemals Schach gespielt? Wenn ja, dann wissen Sie bereits, dass die Dame die wichtigste Figur ist und dass sie eine beliebige Anzahl von Feldern vertikal, horizontal oder diagonal ziehen kann. Falls nicht, keine Sorge: Heute lernen wir nur, wie man 8 Damen so auf dem Schachbrett platziert, dass keine Dame auf ein Feld ziehen kann, das von einer anderen Dame besetzt ist. Im Schachjargon sagen wir, dass sich die Damen nicht gegenseitig angreifen können. Wie machen wir das? Wir verwenden Backtracking.
Der Backtracking-Algorithmus findet eine Lösung für Probleme, bei denen einige Einschränkungen beachtet werden müssen. Er testet alle möglichen Lösungen, bis er die richtige findet. Versuchen wir es mit einem Beispiel, mit vier Damen und einem kleinen Brett. Wir beginnen mit der Platzierung der ersten Dame:
The second step is to place the second queen in a safe position, and then the third one:
At this point, there is no safe square on which we can place the last queen. So, we will change the position of the previous one. This is backtracking!
As you can see, there is no other square to safely place the third queen, different than the one we tried. Hence, this will require multiple backtracks. We will have to go back again and change the position of the second queen we placed.
We will have to perform multiple backtracks again to place all queens correctly and finally obtain a solution:
If you want to learn more how multiple backtracking steps inevitably lead you to a solution, check out Computer Science Distilled. Dort findest du auch viele andere Berechnungsstrategien, die dir helfen, interessante Probleme zu lösen!
Nachdem du nun weißt, wie Backtracking funktioniert, können wir das 8-Damen-Problem in voller Größe lösen. Unten findest du ein Schachbrett, mit dem du spielen kannst, um deine Fähigkeiten zu üben und eine Lösung zu finden. Beginnen Sie damit, die erste Dame zu setzen, indem Sie auf das linke obere Feld des Schachbretts klicken. Sie werden sehen, dass die von Ihnen platzierte Dame in der Liste „Aktuelle Damen“ aufgeführt wird.
Aktuelle Damen
Sie können nun eine weitere Dame so platzieren, dass sie sich nicht gegenseitig angreifen können. Unsere erste Dame steht auf a8, die zweite kann z.B. auf c7 platziert werden. Setzen Sie die Damen so lange, bis kein sicheres Feld mehr auf dem Schachbrett übrig ist. An diesem Punkt ist es an der Zeit, zurück zu gehen, indem Sie auf „Rückgängig“ klicken. Dadurch wird die zuletzt gesetzte Dame gelöscht und Sie können ein anderes Feld wählen, um sie zu setzen. Du kannst eine Dame auch vom Brett entfernen, indem du direkt auf sie klickst.
Indem du das interaktive Spiel spielst, bekommst du ein Gefühl für das Zurückgehen. Für uns Menschen kann es schwierig werden, den Überblick über alle bisherigen Platzierungen von Königinnen zu behalten. Hier hilft die Programmierung! Nachfolgend finden Sie eine Animation, die von einem Programm erzeugt wurde, das seine makellosen Backtracking-Fähigkeiten demonstriert:
Pseudocode:
- Starten Sie, indem Sie die erste Dame auf das linke obere Feld des Schachbretts setzen.
- Wenn wir alle 8 Damen gesetzt haben, sind wir fertig. Wenn nicht, ist es möglich, eine weitere Dame in einer sicheren Position zu platzieren?
- Wenn ja, dann markiere dies als Teil der Lösung und gehe zurück zu Punkt 2.
- Wenn nein, dann ändere die Position der vorherigen Dame (Backtracking) und gehe zurück zu Punkt 2.