Sudoku

[negaH]

Ich habe die Nacht nochmal drüber geschlafen und mich gefragt wie ich es anpacken würde.
Nur mal so als Anregungen:

1.) das Gitter besteht aus 9x9 Cardinal's, jeder speichert Bitcodiert die möglichen Zahlen. D.h. die 1 wäre (1 shl 1) die 2 wäre (1 shl 2) usw. bis (1 shl 9). Dies wäre im grunde identisch mit meinem obigen Vorschlag mit Mengen und Sets zu arbeiten, hat aber einen gravierenden Vorteil diesem gegenüber. Mit solchen Cardinals kann man per Boolscher Algebra, sprich AND, XOR, NOT, OR, viel effizienter nun die Mengen der möglichen Zahlen abfragen.

2.) zu jeder Spalte und Zeile wird parallel zum Gitter ebenfalls ein bitcodierter Cardinal gespeichert. Sobald man also eine Zahl in einer Zelle einfügt/löscht werden diese Spalten/Zeilen Werte ebenfalls per AND/OR aktualisiert.
Du hast also mit diesen Werten die exakte Kontrolle welche Zahlen pro Spalte und Zeile noch frei verfügbar und unbenutzt sind.

3.) zu jedem 3x3 Feld wird ebenfalls ein solcher bitcodierter Cardinal geführt. Auch hier die Grundbedingung das er beim Einfügen/Löschen einer Zahl in einer Zelle entsprechend aktualisiert wird.

4.) der kombinatorische Such-Algortihmus sollte nun absolut deterministisch sein, d.h. komplett ohne irgendwelches Random auskommen. Wird nun eine Countervariable der rekursiven Suchtiefe mitgeführt so indentifiziert diese Countervariable absolut exakt eine gefundene Lösung. Der Suchalgo. könnte nun beginnend mit diesem Counter die logisch nächstfolgende Lösung suchen, usw. usw. Mit dieser Methode ist es also möglich nicht nur eine beliebige Lösung zu finden sondern alle möglichen Lösungen zu errechnen, ohne das man eine auslässt.

5.) ändert man diesen algo so ab das er ohne schon fixierte/vorgegebene Zahlen arbeitet so hast du in fact statt eines Rätsel-Lösungs-Algos einen Rätsel-Erzeugungs-Algo. Dieser Algo kann dann succesive mit Hilfe der Countervariablen ein Rätsel nach dem anderen produzieren.

6.) es ist nämlich für deinen Algo. im grunde egal ob er ein schon bestehendes Rätsel lösen soll oder ob er ein neues Rätsel erzeugen soll. Die Suchstrategie unterscheidet sich in keinster Weise, dereinzigste Unterschied besteht nur darin das in einem Rätsel fixierte Zahlen eingetragen wurden.

Gruß Hagen