Dienstag, 21. Oktober 2014

Sudokus mit C# lösen und generieren

Sudokus, wer kennt sie nicht, die kleinen Kästchen mit Zahlen, welche einem ganz schön Nerven kosten können. Der Wunsch und das Vorhaben, diese computergesteuert lösen zu können, brachte mich dann auf das Problem der Erzeugung von Sudokus. Diesen zwei Themen, das Lösen und das Erzeugen von neuen Sudokus, möchte ich die nächsten Posts widmen.
Es sollte klar sein, dass das Lösen von Sudokus von Computern relativ schnell erledigt werden kann - ein Computer kann in kurzer Zeit alle Möglichkeiten ausprobieren und so zu einer Lösung gelangen. Wesentlich schwerer ist da das Erzeugen. Hierbei ist jedoch das eigentliche Erzeugen auch nicht schwierig - wieder kann durch Ausprobieren ein fertiges Sudoku erzeugt werden. Die wesentliche Schwierigkeit liegt dann aber darin, bestimmte Felder zu löschen, um damit ein Sudoku der gewünschten Schwierigkeit zu erzeugen, welches immer noch eindeutig ist. Eindeutig sollte ein Sudoku sein, damit die Lösung leicht kontrollierbar / vergleichbar ist, außerdem sollte es für jedes richtige Feld nur eine richtige Möglichkeit geben.
Damit zur nächsten Schwierigkeit: Wann ist ein Sudoku leicht, schwer o.ä.? Wie ist dieses definiert? Es ist leicht feststellbar, dass zwischen der Anzahl der gelöschten Felder und der Schwierigkeit kein direkter Zusammenhang besteht.
Kurz ein paar Worte zu mir: Ich selber habe nie wirklich Sudokus gelöst, mein ganzes Wissen darüber habe ich im Laufe der Recherche und Programmierung zu diesem Thema gefunden. Alle hier präsentierten Ideen sind also meine Meinung und können falsch sein. Über Verbesserungen und Korrekturen würde ich mich natürlich wie immer sehr freuen.
Als ich an das Thema heranging, dachte ich, es gäbe einen "Standard" zur Erzeugung und Bewertung von Sudokus. Den gibt es anscheinend nicht. Allerdings ist ein viel verwendetes Prinzip das folgende: Man programmiert ein Lösungsverfahren für Sudokus, welches dem menschlichen ähnelt. Dafür implementiert man verschiedene Regeln, nach denen auch Menschen hierbei Entscheidungen treffen. Diese Regeln sortiert man dann nach Schwierigkeit und kann so erzeugte Sudokus bewerten, in dem man prüft, welche Regeln das Programm anwenden muss. Um die zu löschenden Felder zu bestimmen, kann man entweder versuchen, die Regeln "rückwärts" anzuwenden, oder man überlässt auch dies dem Zufall und prüft stetig die Schwierigkeit (für dieses Verfahren habe ich mich entschieden).
Nun stellt sich natürlich auch die Frage, was es für Regeln gibt und wie schwierig diese sind. Anfangs dachte ich, die meisten Sudokus lassen sich durch einige wenige einfache Regeln (wie z.B. wenn eine Zahl bereits in einem Feld steht, kann sie aus der Kandidatenliste der anderen Felder in derselben "Gruppe" gestrichen werden) lösen. Aber anscheinend gibt es unzählige, beliebig komplexe Regeln, die wohl auch nicht ineinander überführt werden können. So habe ich mich für einige dieser Regeln entschieden und hoffe, dass sie repräsentativ für die Masse sind und ihre Schwierigkeit angemessen beurteilt wurde. Das erste Paper, auf welches ich gestoßen bin, war Creating Sudoku Puzzles von SUN. Aus diesem habe ich das angesprochene Prinzip. Dort werden 4 Kategorien von Regeln benutzt, anfangs dachte ich, das wären auch im groben alle möglichen - aber wie schon erwähnt, es gibt doch noch unzählige Regeln und die dort erwähnten Regeln stehen auch auf vielen anderen Seiten, wie zum Beispiel auf der deutschen Wikipedia Seite oder der sehr umfangreichen Regelsammlung www.sudokuwiki.org. Außerdem habe ich 2 Regeln von dieser Seite übernommen. Motiviert wurde ich unter anderem von Udo's Blog, er hat einen Post zur Lösung von Sudokus durch Ausprobieren geschrieben.
Im nächsten Post werde ich zuerst die beschriebenen Regeln vorstellen. Danach werde ich die Implementierung eines Sudoku Lösers basierend auf diesen Regeln vorstellen - hierbei sollte klar sein, dass die letzte Regelstufe Ausprobieren ist, da es keine Regel gibt, welches jedes Sudoku ohne "Raten" lösen kann. Im letzten Post werde ich dann die Generierung von beliebig schweren Sudokus zeigen.

Mit dem Programm aus dieser Postreihe habe ich auch einen neuen Blog gestartet, dort gibt es täglich neue Sudokus.

Keine Kommentare:

Kommentar veröffentlichen