Die Lösung von Steckhalma kann ein Computer suchen. Der „Tipp“ der App „Steckhalma“ und die Programme, mit denen wir auf dieser Website Lösungen geprüft haben, arbeiten nach demselben Prinzip. Hier erklären wir es einfach.

Alle Züge der Reihe nach probieren

Am einfachsten ist es, einen möglichen Zug auszuwählen und zu spielen, dann wieder einen möglichen Zug auszuwählen und zu spielen und so weiter. Kommst du nicht weiter, gehst du einen Zug zurück und wählst einen anderen, den du noch nicht probiert hast.

  1. Wähle auf dem jetzigen Brett einen möglichen Zug und spiele ihn.
  2. Ist nur noch eine Kugel übrig, ist die Lösung gefunden.
  3. Gibt es keinen möglichen Zug mehr, geh einen Zug zurück und probiere einen anderen.
  4. Hast du alle Züge probiert, geh noch einen Zug weiter zurück.

Dieses Verfahren heißt Tiefensuche. Der Computer macht dasselbe wie ein Mensch, der „Rückgängig“ benutzt, nur wahnsinnig schnell.

Dieselbe Stellung nicht mehrfach prüfen

Bei Steckhalma ergibt sich dieselbe Stellung oft auch bei anderer Zugreihenfolge. Beim englischen Brett mit 33 Löchern gibt es nach dem 7. Zug mehr als 220.000 Zugfolgen, aber nur etwa 22.000 verschiedene Stellungen (Wie viele Lösungen gibt es?).

Deshalb merkt sich das Programm Stellungen, von denen es schon weiß, dass sie in einer Sackgasse enden, und kehrt sofort um, wenn es ihnen wieder begegnet. Allein das verringert den Aufwand stark.

Mit dem Programm, das wir für diese Website benutzt haben, war die Lösung für das englische Brett mit 33 Löchern, die von der Mitte aus in der Mitte endet, im Nu gefunden (in weniger als 0,1 Sekunden). Es ist aber nicht immer so schnell. Als wir von einem Brett mit anderem 2. Zug auf dieselbe Weise suchten, dauerte es etwa 9 Sekunden. Je nachdem, mit welchem Zug man anfängt zu probieren, ändert sich die Zeit stark.

Abbrechen, ohne vorauszurechnen

Ein weiterer Kniff: Wenn schon feststeht, dass man von dieser Stellung aus auf keinen Fall das Ziel erreicht, sucht man nicht weiter. Das nennt man „Beschneiden“.

Die App beschneidet an zwei Stellen.

  • Drei-Farben-Einteilung: Teilst du das Brett diagonal in drei Farben ein, wechselt mit jedem Zug in allen drei Farben die Kugelzahl zwischen gerade und ungerade. Daher steht von der jetzigen Stellung aus allein durch Rechnen fest, in welchen Löchern die letzte Kugel liegen kann (Artikel zur Drei-Farben-Einteilung).
  • Zeile und Spalte der Chefkugel: Die Chefkugel bewegt sich immer um zwei Felder, deshalb bleibt bei ihrem Loch die Zeile und Spalte gerade oder ungerade (So bleibt die Chefkugel zuletzt übrig).

Gibt es auf dem Brett kein einziges Loch mehr, das beide Bedingungen erfüllt, kann die Chefkugel nirgends mehr als letzte übrig bleiben. Diese Stellung ist dann ohne Vorausrechnen als „nicht lösbar“ erkannt.

Beim „Tipp“ der App

Der „Tipp“ der App sucht von der jetzigen Stellung aus einen nächsten Zug, mit dem du das Ziel erreichst, und lässt ihn mit goldenen Ringen aufleuchten.

  • Die Lösung des Rätsels vorher merken: Ein „Rätsel“-Brett entsteht durch Rückwärtsspringen, die Lösung vom Bauen ist also bekannt (So entstehen immer lösbare Rätsel). Stellungen auf diesem Lösungsweg sind als „lösbar“ gemerkt, deshalb kann die App sofort antworten. Auch wenn du vom Weg abgekommen bist, kann die Suche aufhören, sobald sie auf den Lösungsweg trifft.
  • Eine Obergrenze für den Aufwand: Pro Tipp prüft die App höchstens 1,5 Millionen Stellungen oder 3 Sekunden. Auf großen Brettern kann es sein, dass bis dahin noch keine Antwort da ist.
  • Zahl der Züge zurück nennen: Kannst du von der jetzigen Stellung aus das Ziel nicht mehr erreichen oder weiß die App es innerhalb der Obergrenze nicht, prüft sie die Stellungen, zu denen du mit „Rückgängig“ zurückkommst, und sagt dir, wie viele Züge du zurückgehen musst, etwa „3 zurück, um sie zu retten“. Weil sie die Stellungen, zu denen du zurückkannst, immer wieder halbiert, findet sie das auch bei vielen Zügen schnell.

Hinweise, wenn du selbst löst

Die Kniffe des Computers helfen auch dir.

  • Gescheiterte Formen merken: Eine Form, die einmal gescheitert ist, scheitert auch, wenn du sie auf anderem Weg erreichst.
  • Vom Ziel aus denken: Die Löcher, in denen die letzte Kugel liegen kann, stehen von Anfang an fest. Wenn du dir zuerst ein Zielloch aussuchst, fällt dir die Zugwahl leichter (So endest du in der Mitte).
  • Zurückgehen und probieren: Wie bei der Tiefensuche ist es richtig, bei Unsicherheit ein Stück zurückzugehen und einen anderen Zug zu probieren.