Rekursion, fürsorgliche Browser, vorherbestimmte Zufallszahlen
oder
Wie man den Stack verschont

Die Aufgabe Konstruktion neuer Rätsel, die Humanoiden Freude bereiten bedarf einer begrifflichen Klärung. Es dürfte evident sein, daß es sich beim Ergebnis der Bemühungen um gültige ungelöste Sudokus handeln soll; der Aspekt des Freude Bereitens sollte aber genauer definiert werden.

Zu Zynismus neigende Spieleentwickler werden sich vielleicht auf den Standpunkt stellen, die meisten Nutzer seien übersättigt und würden ein neues Spiel- oder Rätselprogramm nur ein einziges mal verwenden, deswegen brauche man sich nicht um Abwechslung zu bemühen. Für den unwahrscheinlichen Fall der mehrmaligen Nutzung könne man die Invarianz von Sudokus gegen Austausch von Zahlen nutzen, wodurch sich bei einem 81teiligen Sudoku 9! = 362880 Möglichkeiten ergäben, bei einem 16teiligen Sudoku immerhin 4! = 24, und sich diese Anzahl durch Drehen der jeweiligen Möglichkeit um 90°, 180° und 270° noch vervierfache1.

Eine derartige Argumentation mißfällt mir nicht nur wegen der darin zum Ausdruck gebrachten herablassenden Haltung, sondern auch, weil die vorgeschlagenen Permutationen im Sinne der Aufgabenstellung fragwürdig sind. Derart veränderte Sudokus werden zwar ganz anders aussehen als die Rätsel, aus denen sie hervorgegangen sind, zu ihrer Lösung werden aber genau die gleichen logischen Schritte notwendig sein. Ich glaube nicht, daß das wiederholte Lösen wesensgleicher Rätsel auf Dauer Freude bereitet. Zudem müßte man sich fragen, zu welchem Zweck man einen Algorithmus verfassen soll, wenn das einmalige Hinterlegen einer geeigneten Lösung genügte.

Da Algorithmen deterministisch arbeiten, also unter identischen Bedingungen stets identische Ergebnisse liefern, muß eine Zufallskomponente eingebaut werden, um Abwechslung zu gewährleisten; natürlich darf diese die Gültigkeit der Lösung nicht beeinträchtigen. Zwei Möglichkeiten bieten sich an:

Bei beiden Möglichkeiten kommt der Bedingung im Rahmen der Gültigkeit besondere Bedeutung zu. Weder der Zufall noch eine zuvor beschlossene Regel können festlegen, welche Zahl letztendlich auf einem Feld erscheint; es kann lediglich die Reihenfolge der Kandidaten bestimmt werden, die bei der Suche nach einer gültigen Zahl zum Einsatz kommt.

Die zweite Möglichkeit ist der ersten vorzuziehen, da die erste folgende Nachteile aufweist:

Die Tauglichkeit der zweiten Möglichkeit kann man sich vor Augen halten, indem man bedenkt, daß mit ihrer Hilfe alle gültigen gelösten Sudokus gefunden werden können. Zu diesem Zwecke stelle man sich ein beliebiges gültiges gelöstes Sudoku vor und nehme an, der Zufall habe als Reihenfolge der zu besetzenden Spielfelder erst alle, die später eine 1 aufweisen, dann alle, die später eine 2 aufweisen usw. ausgewählt.

Eine weitere wichtige Komponente für die Freude am Rätseln ist die Schwierigkeit des ungelösten Sudoku. Es erscheint als selbstverständlich, daß zu leichte Sudokus wenig Freude bereiten; der Umkehrschluß, also die Annahme, schwierigere Sudokus machten grundsätzlich mehr Spaß, wird durch die Tatsache infrage gestellt, daß Sudokus meist in verschiedenen Schwierigkeitsgraden angeboten werden. Zudem ist zu klären, welche Sudokus als schwierig und welche als leicht gelten. Eine naheliegende (und zumindestens tendenziell offensichtlich richtige) Annahme ist, Sudokus mit einer geringen Anzahl an vorgegebenen Zahlen einen höheren Schwierigkeitsgrad zuzubilligen; es mag aber noch andere Kriterien geben, die mir unbekannt sind.

Als Gerüst für einen Algorithmus zur Generierung verwendbarer Sudokus schlage ich folgendes vor:

Der letzte Punkt ist zugegebenermaßen ein bißchen schwammig. Falls die fertigen ungelösten Sudokus tendenziell zu schwierig sein sollten, bestünde eine einfache Möglichkeit, sie zu vereinfachen, darin, nicht ganz so viele Zahlen zu löschen. Eine Erhöhung des Schwierigkeitsgrades dürfte aufwendiger sein. Im Rahmen der sich an Einsparung von Ressourcen orientierenden Optimierung des Algorithmus werde ich Möglichkeiten aufzeigen, wie man den Komplexitätsgrad für den Computer erhöht oder erniedrigt; diese Methoden lassen sich sicherlich zumindestens teilweise auch für die Generierung schwieriger Sudokus anwenden. Da ich aber nicht weiß, welche Eigenschaften eines Sudoku von passionierten Rätsellösern als besonders schwierig empfunden werden (und wieviel Schwierigkeit überhaupt gewünscht ist), wird dieser Aspekt im folgenden vernachlässigt.

Auf der folgenden Seite wird eine Umsetzung des obigen Gerüstes für ein 16teiliges Sudoku näher erläutert. Eine Demonstration genau dieser Umsetzung finden Sie hier; den dazugehörigen Code hier. (Sie erreichen diesen Code nur über diesen Link, nicht über das Menu)


 zurück: Problemstellungweiter: 4x4 rekursiv 

1 Wenn man sich den Luxus leisten kann, 9! * 4 = 1451520 Möglichkeiten zu einer einzigen zusammenzufassen und trotzdem noch von einer Vielzahl an Möglichkeiten ausgeht, muß die Gesamtmenge wirklich astronomisch groß sein.  ↑