Comments
28/08: Sudoku-Resolver 1.0
Was macht man an einem verregneten Sonntag Morgen? Genau, etwas programmieren nach dem Motto “Just for fun”. Heute morgen habe ich einen Sudoku-Resolver und Checker programmiert. Sicher kennt nun bald jeder die “neuen” Rätsel aus Japan, die in vielen Zeitungen abgedruckt werden. Man bekommt 9 Felder (angeordnet 3×3), die wiederum aus je 9 Felder (3×3) bestehen. Ziel ist es nun, die leeren Felder mit Zahlen zu füllen. Dabei müssen in jeder waagrechten und senkrechten Zeile die Zahlen von 1-9 vorkommen. Ausserdem müssen diese neun Zahlen auch in jedem der 9 Teilfelder vorkommen. Wer es mit meiner schlechten Beschreibung nicht begreift um was es geht, kann bei der Wikipedia nachschauen (die erklären das hier besser) 
Jedenfalls kann man hier (88Kb) mein kleines Programm herunterladen. Anschliessend muss man nur noch die bekannten Zahlen in die Felder einfüllen (oder wenn man das Rätsel bereits gelöst hat auch alle Zahlen). Mit Klick auf “Resolve!” werden die fehlenden Zahlen ergänzt (bei mehreren Lösungen gibt es einfach eine Lösung). Anschliessend (oder falls bereits von Beginn an alle Zahlen eingesetzt wurden) wird nochmals ein Check durchgeführt, ob die Lösung plausibel ist. Falls ja, bekommt man eine Erfolgsmeldung. Ansonsten (oder falls das Rätsel nicht eindeutig lösbar ist) wird die Meldung “Mission impossible” ausgegeben Das bedeutet Kapitulation für das Programm (wer ein solches Sudoku findet, darf es mir gerne senden).
Vielleicht noch einige Worte zur Funktionsweise. Das Programm liest die vorhandenen Zahlen ein. Anschliessend werden für jedes Feld die noch möglichen Werte errechnet. Dann wird überprüft, für welches Feld nur noch einen Wert in Frage kommt (=eindeutig ist). Diese Werte werden gesetzt. Danach beginnt das wieder von vorne (mögliche Werte errechnen, Eindeutige setzen etc.). Ich habe das Programm mit 3 Sudokus getestet. Beim “schwierigsten” hat es 13 solche Durchläufe benötigt. Ich habe auch einmal einen Test gefahren mit einem “Mission impossible”-Rätsel und 200 Durchläufen (wegen der Geschwindigkeit). Auch das hat nur wenige Sekunden gedauert.
PS: Das Programm ist eine .NET-Applikation. Wer beim Starten Probleme hat, Fehler findet oder Anregungen hat, kann mir gerne ein Mail senden.
Update vom 13. Oktober 2005
Der Sudoku-Resolver ist in der Version 1.2 verfügbar. Das Programm kann nun auch etwas schwierigere Sudokus lösen. Es werden, falls mit der oben beschriebenen Methoden keine Lösung gefunden werden kann, zwei neue Algorythmen angewendet.
1. Einzig mögliche Lösung unter Vielen
Beispiel: wir haben noch folgende, ungelöste Felder in einer Zeile:
Feld 1: mögliche Werte = 3,4,7,8
Feld 2: mögliche Werte = 2,4,7,8
Feld 3: mögliche Werte = 2,4,7
Somit ist klar definiert, dass in Feld 1 der Wert 3 stehen muss, da er in keinem anderen Feld mehr stehen kann.
2. Ausschluss bei 3 Zahlen in 3 Feldern
Wenn in drei Feldern ausschliesslich 3 Zahlen vorkommen, können diese Zahlen in keinen anderen Feldern vorkommen.
Beispiel: wir haben noch folgende, ungelöste Felder in einer Zeile:
Feld 1: mögliche Werte = 2,4,7
Feld 2: mögliche Werte = 4,7
Feld 3: mögliche Werte = 2,7
Feld 4: mögliche Werte = 2,4,6,7
Somit ist klar definiert, dass in Feld 4 der Wert 6 stehen muss. Denn in den Feldern 1,2 und 3 müssen die drei Werte 2, 4 und 7 stehen (genaue Verteilung noch unbekannt). Wir können diese Werte aus allen anderen, ungelösten Feldern entfernen.
Das selbe gilt natürlich bei zwei Zahlen in zwei Feldern:
Feld 1: mögliche Werte = 4, 6
Feld 2: mögliche Werte = 6, 4
In keinem anderen Feld in dieser Zeile können nun die Werte 4 oder 6 vorkommen.
Wie schon oben erwähnt: wer ein Sudoku findet, dass mit diesem Programm nicht gelöst werden kann, darf mir das gerne senden. Nach diesem Update ist mir wieder keines bekannt 
9 Kommentare »
Hinterlasse einen Kommentar
Line and paragraph breaks automatic, e-mail address never displayed, HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>
Bei mir erscheint nur die folgende Fehlermeldung:
>Die Anwendung konnte nicht richtig initiaslisiert werden (0xc0000135). Klicken Sie auf “OK”, um die Anwendung zu beenden.
6. Oktober 2005 @ 19:00 (comment)
Die Anwendung läuft unter .NET. Daher muss das .NET-Framework installiert sein. Wahrscheinlich ist das nicht der Fall.
Download unter:
http://www.microsoft.com/downloads/details.aspx?FamilyID=262d25e3-f589-4842-8157-034d1e7cf3a3&displaylang=de
7. Oktober 2005 @ 13:05 (comment)
OK. Das stimmt. Ich habe den Text falsch gelesen. Ich dachte es braucht kein .Net!
7. Oktober 2005 @ 18:22 (comment)
Hat schon mal jemand einen Fillomino-Solver geschrieben? Das scheint mir noch schwieriger als ein Sudokusolver!
12. Dezember 2005 @ 17:08 (comment)
Kommt ganz auf die Technik bzw. cleverness des Programms an. Natürlich könnte man bei all diesen Rätseln einfach alle Lösungen durchprobieren. Die Kunst ist es nun aber, einen Algorithmus zu schreiben, der mit *minimalstem* Rechenaufwand die/eine Lösung findet.
Ein stures Durchprobieren aller Möglichkeiten würde bei heutigen Rechnerleistungen niemand bemerken. Der Reiz liegt daher eher im Entwickeln anderer, raffinierter Methoden.
12. Dezember 2005 @ 21:21 (comment)
Na so ganz unwichtig ist das effizient berechnen nicht. Auf einem PocketPC zb hat man plötzlich wieder nur 200Mhz zur Verfügung.
13. Dezember 2005 @ 13:24 (comment)
Gibt es eine Möglichkeit einen Sudoku-Resolver in Visual Basic zu programmieren?
3. April 2006 @ 20:54 (comment)
Ich wollte Dein Resolver herunterladen, aber ich bekomm nur eine Error Meldung, dass die Seite nicht aktiv ist.
Kannst Du mir bitte das Tool auf meine Email Adresse senden?
29. August 2008 @ 09:39 (comment)
Danke für den Kommentar. Den Beitrag habe ich noch in meinem alten Blog geschrieben. Die Adresse des Downloads hat daher geändert, sie lautet neu:
http://gebloggt.ch/wp-content/pics_blog/SudokuResolver.exe
Das Tool wurde aber nicht mehr weiterentwickelt
30. August 2008 @ 14:47 (comment)