\n
![](\"https:\/\/martin-seewaldt.de\/Programme\/Sudoku2.gif\")
<\/p>\n","protected":false},"excerpt":{"rendered":"Gestelltes Problem<\/b>
\nDas Sudoku war also prinzipiell gel\u00f6st. Es zeigte sich jedoch, dass f\u00fcr manche R\u00e4tsel recht viele Kombinationen ausprobiert werden mussten. Bei einem R\u00e4tsel waren es 45253, was f\u00fcr die heutige Hardware ein Witz ist, aber in Zusammenhang mit der Ausgabe jeder Position auf dem Monitor dann doch zu Laufzeiten von \u00fcber 10 Minuten f\u00fchrte. Da kann man dann nat\u00fcrlich tricksen und nur jede f\u00fcnfte oder zehnte Position ausgeben. Es zeigte sich jedoch dass bei einer vertikal gespiegelten Version des obigen R\u00e4tsels statt 45253 Versuchen nur noch 199 n\u00f6tig waren. Die Methode, die jeweils erste freie Zelle von links oben durchzuiterieren war offensichtlich suboptimal.<\/p>\n
Algorithmus<\/b>
\nDer Grundalgorithmus blieb gleich, freie Zelle suchen und f\u00fcr jede m\u00f6gliche Ziffer Rekursion mit der n\u00e4chsten freien Zelle. Ge\u00e4ndert wurde lediglich das Auffinden dieser Zelle. Unter allen noch freien Zellen wird die genommen, deren Kasten, Zeile und Spalte am meisten gef\u00fcllt sind. Bei der Optimierung von rekursiven Programmen habe ich immer eine gewisse Scheu, zus\u00e4tzliche Anweisungen einzuf\u00fcgen, aber letzten Endes h\u00e4ngt die Gesamtlaufzeit nur von einer m\u00f6glichst niedrigen Anzahl Rekursionen ab. Mein Referenzr\u00e4tsel wird jetzt jedenfalls mit 315 Versuchen gel\u00f6st.<\/p>\n
Screenshot:<\/b>
\n<\/p>\n","protected":false},"excerpt":{"rendered":"
Gestelltes Problem Das Sudoku war also prinzipiell gel\u00f6st. Es zeigte sich jedoch, dass f\u00fcr manche R\u00e4tsel recht viele Kombinationen ausprobiert werden mussten. Bei einem R\u00e4tsel waren es 45253, was f\u00fcr die heutige Hardware ein Witz ist, aber in Zusammenhang mit der Ausgabe jeder Position auf dem Monitor dann doch zu Laufzeiten von \u00fcber 10 Minuten […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_post_was_ever_published":false},"categories":[3],"tags":[],"class_list":["post-54","post","type-post","status-publish","format-standard","hentry","category-programme_apps"],"yoast_head":"\n