Das Springerproblem ist auf den Schweizer Mathematiker Leonhard Euler (1707 – 1783) zurückzuführen.
Dieser stellte sich vor über 200 Jahren, genauer gesagt im Jahre 1758, die folgende Frage:
„Gegeben sei ein leeres Schachbrett. Gibt es eine Zugfolge, mit der der Springer alle (schwarzen und weißen)
Felder des Bretts genau einmal besucht?”.
Hmmm, eine gute Frage, wird sich der geneigte Leser jetzt sagen. Möglicherweise kann man sie innerhalb
von wenigen Minuten selbst beantworten, schließlich ist ein Schachbrett mit seinen 8×8 Feldern
nicht so wirklich groß. Stellt man nach einer ersten Phase euphorischen Suchens ernüchternd fest,
dass das Problem doch nicht ganz so einfach zu lösen ist, kommt man vielleicht auf den revolutionären Gedanken,
dem Problem mit Hilfe eines Softwareprogramms auf den Leib zu rücken. Dies ist natürlich möglich,
wie wir in dieser Fallstudie am Beispiel von Modern C++ zeigen werden.
Neben der Implementierung einer Backtracking-Strategie betrachten wir auch Überlegungen,
wie sich das Suchen von Zugfolgen parallelisieren lässt.
Die Methode std::async
und Objekte, die es „erst in der Zukunft” gibt (std::future<T>
), kommen zum Einsatz.
[Read More]