Das Haus des Nikolaus ist ein bekanntes Zeichenspiel, das Kinder oft gerne spielen. Das Ziel des Spiels ist es, ein Haus ohne Absetzen des Stiftes zu zeichnen, also in einem Zug mit acht Strecken. Allerdings kommt es oft vor, dass man eine Strecke mehrmals zeichnen muss, was nicht erlaubt ist. Zusätzlich sprechen Kinder bei jeder Ecke des Hauses einen Satz aus. Wie viele verschiedene Möglichkeiten gibt es, das Haus zu zeichnen?
Eine klassische Lösung
Um alle Lösungen des “Haus des Nikolaus” – Problems zu ermitteln, können geeignete C++-Klassen entworfen werden. Eine klassische Realisierung ohne “Modern C++” Kenntnisse kann einfach umgesetzt werden. Dafür werden die STL-Klassen std::vector und std::array sowie verschiedene STL-Algorithmen wie std::adjacent_find, std::all_of und std::generate verwendet.
Eine C++20 Lösung mit “Ranges”
Alternativ kann das Problem auch mit C++20 Ranges gelöst werden. Dabei werden die C++20 Ranges-Bibliotheksfunktionen std::views::iota, std::ranges::find_if und std::ranges::for_each verwendet. Zusätzlich kommen Lambda-Funktionen zum Einsatz. Diese Lösung ist etwas mächtiger und bequemer, aber die Laufzeitunterschiede zwischen den beiden Varianten sind minimal.
Mathematische Betrachtung
Das Haus des Nikolaus kann als ungerichteter Graph betrachtet werden, bestehend aus fünf Knoten und acht Kanten. Um alle Wege in diesem Graphen zu finden, die jede Kante genau einmal durchlaufen, wird eine neunstellige Zahl verwendet. Dabei stellen die Ziffern dieser Zahl die zu zeichnenden Kanten dar. Allerdings gibt es bestimmte Einschränkungen, z.B. keine Zahlen mit den Ziffern 6-9 oder 0. Auch aufeinanderfolgende identische Ziffern sind nicht erlaubt. Durch die Umsetzung der Zahlen und Kanten als Paare von Knoten kann ein zulässiger Pfad zum Zeichnen gefunden werden.
Zusammenfassung
Das “Haus des Nikolaus” – Problem kann auf verschiedene Weisen gelöst werden. Es gibt eine klassische Lösung mit einfacher Implementierung sowie eine modernere Lösung mit der C++20 Ranges-Bibliothek. Die mathematische Betrachtung des Problems zeigt, wie durch die Verwendung von Zahlen und Kanten ein zulässiger Pfad gefunden werden kann.
