Kniffelige Sache: Ein Sudoku Generator

Wie löst man ein Sudoku…schwierig…wie erzeugt man ein gutes Sudoku … noch schwieriger, … wie erzeugt man ein Sudoku extrem schnell … richtig schwierig! Zuerst mal der Basisansatz:

  1. Man erzeugt einfach eine korrekte Belegung eines 9×9-Feldes indem man von links oben nachts unten alle Felder durchgeht und in jedes Feld eine zufällige der noch erlaubten Zahlen einträgt. Kommt man mal nicht weiter trackt man back!
  2. Jetzt bestimmt man zuällig x Felder die aufgedeckt sein sollen und löscht die restlichen Zahlen.
  3. Ergebniss ist ein Sudoku nur leider ist noch nicht gewährleistet, ob es eine eindeutige Lösung hat. Dies erreicht man mit einem logischen Solver, der ähnlich kombiniert wie der Mensch es machen würde.

Ok das war ganz grob und nun zu den Detailproblemen. Was macht man, wenn im Schritt 3 rauskommt, es ist nicht mit reinem Schliessen ohne Raten oder Ausprobieren lösbar. Von vorne anfangen? Nein das wäre ja doof, das hat ja schon Rechenzeit gekostet die Ausgangsbelegung zu generieren und die ist ja noch gut. Eine neue Teilmenge offener Zahlen würfeln? Bei 48 und 36 offenen Zahlen funktioniert das gut. Hier hat man nach im Schnitt zwei Anläufen ein lösbares Rätsel gefunden. Bei schweren Rätseln der 24er-Kategorie ist die Wahrscheinlichkeit zufällig ein lösbares Rätsel zu treffen schon kleiner. Was nun? Ich hatte mir hier folgendes ausgedacht:

  1. Man deckt eins der 24 vorgegebenen Felder wieder zu
  2. Der Löser soll sehen wie weit er kommt. Lösung gefunden? Hurra!?
  3. Falls nicht: Man nimmt eins der Felder die nicht vorgegeben waren und nicht erschlossen werden konnten und deckt es als vorgegeben auf. Wechsel zu Schritt 2

Diese Variante hat in meinen Experimenten einen Geschwindigkeitssteigerung m den Faktor 3 zur Folge. Weitere Kniffs und Tricks sind Betriebsgeheimniss 🙂


Warning: count(): Parameter must be an array or an object that implements Countable in /homepages/7/d34956116/htdocs/buschtrommel/wp-includes/class-wp-comment-query.php on line 405

2 Responses to “Kniffelige Sache: Ein Sudoku Generator”

  1. Buschtrommel (=bush telegraph) » Blog Archive » Sudokus lösen Says:

    […] Vor einger Zeit habe ich an dieser Stelle über das Problem des Sudoku Generierens berichtet. Heute möchte ich einen Algorithmus zum Lösen vorstellen, wie er so ähnlich in Mobile Sudoku implementiert ist: […]

  2. Buschtrommel (=bush telegraph) » Blog Archive » Sudokus generieren - Teil 2 Says:

    […] Vor kurzem berichtete ich über eine Methode Sudokus zu generieren. Leider war der vorgestellte Algorithmus sehr zeitkomplex. Durch einen Benutzer von Mobile Sudoku wurde ich auf eine alternative schnelle und interessante Generierungsmethode aufmerksam gemacht. […]