{"id":9,"date":"2005-12-14T22:05:09","date_gmt":"2005-12-14T21:05:09","guid":{"rendered":"http:\/\/www.buschtrommel.net\/?p=9"},"modified":"2006-01-16T14:04:55","modified_gmt":"2006-01-16T13:04:55","slug":"kniffelige-sache-ein-sudoku-generator","status":"publish","type":"post","link":"https:\/\/www.buschtrommel.net\/?p=9","title":{"rendered":"Kniffelige Sache: Ein Sudoku Generator"},"content":{"rendered":"

Wie l\u00c3\u00b6st 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:<\/p>\n

    \n
  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\u00c3\u00a4llige der noch erlaubten Zahlen eintr\u00c3\u00a4gt. Kommt man mal nicht weiter trackt man back!<\/li>\n
  2. Jetzt bestimmt man zu\u00c3\u00a4llig x Felder die aufgedeckt sein sollen und l\u00c3\u00b6scht die restlichen Zahlen.<\/li>\n
  3. Ergebniss ist ein Sudoku nur leider ist noch nicht gew\u00c3\u00a4hrleistet, ob es eine eindeutige L\u00c3\u00b6sung hat. Dies erreicht man mit einem logischen Solver, der \u00c3\u00a4hnlich kombiniert wie der Mensch es machen w\u00c3\u00bcrde.<\/li>\n<\/ol>\n

    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\u00c3\u00b6sbar. Von vorne anfangen? Nein das w\u00c3\u00a4re ja doof, das hat ja schon Rechenzeit gekostet die Ausgangsbelegung zu generieren und die ist ja noch gut. Eine neue Teilmenge offener Zahlen w\u00c3\u00bcrfeln? Bei 48 und 36 offenen Zahlen funktioniert das gut. Hier hat man nach im Schnitt zwei Anl\u00c3\u00a4ufen ein l\u00c3\u00b6sbares R\u00c3\u00a4tsel gefunden. Bei schweren R\u00c3\u00a4tseln der 24er-Kategorie ist die Wahrscheinlichkeit zuf\u00c3\u00a4llig ein l\u00c3\u00b6sbares R\u00c3\u00a4tsel zu treffen schon kleiner. Was nun? Ich hatte mir hier folgendes ausgedacht:<\/p>\n

      \n
    1. Man deckt eins der 24 vorgegebenen Felder wieder zu<\/li>\n
    2. Der L\u00c3\u00b6ser soll sehen wie weit er kommt. L\u00c3\u00b6sung gefunden? Hurra!?<\/li>\n
    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<\/li>\n<\/ol>\n

      Diese Variante hat in meinen Experimenten einen Geschwindigkeitssteigerung m den Faktor 3 zur Folge. Weitere Kniffs und Tricks sind Betriebsgeheimniss<\/a> \ud83d\ude42<\/p>\n","protected":false},"excerpt":{"rendered":"

      Wie l\u00c3\u00b6st 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: 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\u00c3\u00a4llige der noch erlaubten […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"_links":{"self":[{"href":"https:\/\/www.buschtrommel.net\/index.php?rest_route=\/wp\/v2\/posts\/9"}],"collection":[{"href":"https:\/\/www.buschtrommel.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.buschtrommel.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.buschtrommel.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.buschtrommel.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=9"}],"version-history":[{"count":0,"href":"https:\/\/www.buschtrommel.net\/index.php?rest_route=\/wp\/v2\/posts\/9\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.buschtrommel.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=9"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.buschtrommel.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=9"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.buschtrommel.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=9"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}