{"id":21,"date":"2006-01-28T16:19:28","date_gmt":"2006-01-28T15:19:28","guid":{"rendered":"http:\/\/www.buschtrommel.net\/?p=21"},"modified":"2008-03-19T23:09:17","modified_gmt":"2008-03-19T22:09:17","slug":"sudokus-generieren-teil-2","status":"publish","type":"post","link":"http:\/\/www.buschtrommel.net\/?p=21","title":{"rendered":"Sudokus generieren &#8211; Teil 2"},"content":{"rendered":"<p><img decoding=\"async\" align =\"left\" src=\"\/images\/sudoku-farbig.png\" alt=\"Sudoku\" \/>Vor kurzem berichtete ich \u00c3\u00bcber eine Methode <a href=\"http:\/\/www.buschtrommel.net\/?p=9\">Sudokus zu generieren<\/a>. Leider war der vorgestellte Algorithmus sehr zeitkomplex. Durch einen Benutzer von <a href=\"http:\/\/sudoku.buschtrommel.net\">Mobile Sudoku<\/a> wurde ich auf eine alternative schnelle und interessante Generierungsmethode aufmerksam gemacht.<\/p>\n<p>Man geht von einer gro\u00c3\u0178en aber \u00c3\u00bcberschaubaren Menge von Sudokus aus, die man mit einem aufw\u00c3\u00a4ndigeren Verfahren erzeugt hat. Diese &#8222;Ausgangspopulation&#8220; von sagen wir 100 R\u00c3\u00a4tsel kann man zu einer sehr gro\u00c3\u0178en Menge verschiedener R\u00c3\u00a4tsel ausweiten indem man eine beliebige Anzahl folgender Mutationsschritte auf einem R\u00c3\u00a4tsel durchf\u00c3\u00bchrt:<\/p>\n<ul>\n<li> <strong>Vertauschen der Bockspalten<\/strong>: Im Beispiel vertauscht man den blau markierten Bereich mit dem gr\u00c3\u00bcnen Bereich. Man erh\u00c3\u00a4lt wiederum ein  g\u00c3\u00bcltiges Sudoku.<\/li>\n<li><strong>Vertauschen von Blockzeilen<\/strong>: Was oben f\u00c3\u00bcr Blockspalten funktioniert, gilt ebenso zur Blockzeilen. Drei verschiedene Vertauschungen sind m\u00c3\u00b6glich.<\/li>\n<li><strong>Vertauschen von Einzelspalten<\/strong>: Innerhalb einer Blockspalte kann man jeweils zwei Spalten vertauschen und alle Sudokuconstraints bleiben erhalten. Im Beispiel sind dies die rote und die gelbe Spalte.<\/li>\n<li><strong>Vertauschen von Einzelzeilen<\/strong>: Keine gro\u00c3\u0178e \u00c3\u0153berraschung. Die Sudokueigenschaften bleiben auch hier erhalten!<\/li>\n<\/ul>\n<p>Auf diese Weise erh\u00c3\u00a4lt man aus jedem R\u00c3\u00a4tsel der Ausgangsmenge 3^10 neue R\u00c3\u00a4tsel! Jippie!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Vor kurzem berichtete ich \u00c3\u00bcber 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. Man geht von einer gro\u00c3\u0178en aber \u00c3\u00bcberschaubaren Menge von Sudokus aus, die man mit einem aufw\u00c3\u00a4ndigeren Verfahren erzeugt hat. Diese &#8222;Ausgangspopulation&#8220; [&hellip;]<\/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":"http:\/\/www.buschtrommel.net\/index.php?rest_route=\/wp\/v2\/posts\/21"}],"collection":[{"href":"http:\/\/www.buschtrommel.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.buschtrommel.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.buschtrommel.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.buschtrommel.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=21"}],"version-history":[{"count":0,"href":"http:\/\/www.buschtrommel.net\/index.php?rest_route=\/wp\/v2\/posts\/21\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.buschtrommel.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=21"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.buschtrommel.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=21"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.buschtrommel.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=21"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}