Weblog

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).

sudoku

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 🙂

22/08: Nervender Spam

Heute habe ich aus reiner Bequemlichkeit einen neuen Filter eingerichtet. Wer mir nun ein Mail schreibt, in dessen Betreff die Worte „pornodvd“ oder „erotikvideos“ vorkommen, muss damit rechnen, dass sie ungelesen in den Papierkorb wandern. Klar, das ist keine optimale Lösung. Wahrscheinlich werden die Spammer Porno bald mit zwei n schreiben. Aber wie gesagt, manchmal sind solche Aktionen nötig, um den Frust abzubauen.