Die Benutzung gestaltet sich eigentlich ganz einfach: Über die Handy-Tastatur wird das Sudoku eingegeben, was zugegeben etwas umständlich ist, und per mehrmaligen Druck auf die Rautetaste (#) wird das Sudoku schrittweise gelöst (siehe Video).
Der Lösungsalgorithmus ist eigentlich auch recht simpel und orientiert sich an meiner Strategie Sudokus per Hand zu lösen:
- Grundsätzlich kommen für jedes Feld die Zahlen von 1 bis 9 als "Kandidaten" in Frage.
- Ich suche mir ein bestimmtes Feld aus und schaue welche Zahlen bereits in der gleichen Zeile, Spalte und "Box" (ihr wisst was gemeint ist, oder?) stehen und kann diese sofort als Kandidaten für dieses Feld ausschließen.
- Bleibt nur ein solcher Kandidat übrig, ist das die richtige Zahl für dieses Feld.
- So verfahre ich immer wieder mit jedem Feld bis das Sudoku gelöst ist.
Anmerkung: Natürlich verfahre ich nicht nur nach dem oben beschriebenen Verfahren, sondern nutze jede Menge "Abkürzungen", sonst würde man ja verrückt werden... :-)
Mathematisch könnte man das so beschreiben:
Ki,j sei die Kandidatenmenge des Feldes Fi,j in der Zeile i und Spalte j und ist zu Beginn Ki,j = {1...9}.
Z1...Z9 sind die Mengen der je in einer Zeile enthaltenen Zahlen.
S1...S9 sind die Mengen der je in einer Spalte enthaltenen Zahlen.
B1,1...B3,3 sind die Mengen der je in einer Box enthaltenen Zahlen.
Für die Kandidatenmenge des Feldes Fi,j gilt dann in jedem Iterationsschritt
Ki,j = Ki,j \ Zi ∩ Ki,j \ Sj ∩ Ki,j \ Bi,j oder kürzer Ki,j = Ki,j \ (Zi ∪ Sj ∪ Bi,j).
Sprich in jedem Iterationsschritt wird die Kandidatenmenge des Feldes um die Zahlen, die in der gleichen Zeile, Spalte und Box enthalten sind, reduziert.
Z1...Z9 sind die Mengen der je in einer Zeile enthaltenen Zahlen.
S1...S9 sind die Mengen der je in einer Spalte enthaltenen Zahlen.
B1,1...B3,3 sind die Mengen der je in einer Box enthaltenen Zahlen.
Für die Kandidatenmenge des Feldes Fi,j gilt dann in jedem Iterationsschritt
Ki,j = Ki,j \ Zi ∩ Ki,j \ Sj ∩ Ki,j \ Bi,j oder kürzer Ki,j = Ki,j \ (Zi ∪ Sj ∪ Bi,j).
Sprich in jedem Iterationsschritt wird die Kandidatenmenge des Feldes um die Zahlen, die in der gleichen Zeile, Spalte und Box enthalten sind, reduziert.
In Java sieht das ganze so aus:
Wobei Set eine eigene Klasse ist und eine mathematische Menge repräsentiert. Die Methode Set.merge führt zwei Mengen zusammen und gibt die Vereinigungsmenge zurück.
Ich habe für die Darstellung des Sudokus das Lightweight UI Toolkit (LWUIT), da es im Standard-LCDUI kein Tabellen-Widget gibt.
Die App sollte auf so ziemlich allen Java-Handys laufen, wobei ich vermute, dass (obwohl kein Beschleunigungssensor verwendet wird) die Java-Plattform 8 vorausgesetzt wird. Getestet wie immer nur mit einem Sony Ericsson K850i, W980 und C902, mit neueren Geräten sollte es keine Probleme geben.
Hier könnt ihr euch die Anwendung herunterladen und über USB oder Bluetooth auf eurem Handy installieren. Viel Spaß damit!
Bei Interesse veröffentliche ich auch gerne Ausschnitte des Java-Quellcodes.
candidatesSet = new Set(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9});
candidatesSet.remove(colSet.merge(rowSet).merge(boxSet));Wobei Set eine eigene Klasse ist und eine mathematische Menge repräsentiert. Die Methode Set.merge führt zwei Mengen zusammen und gibt die Vereinigungsmenge zurück.
Ich habe für die Darstellung des Sudokus das Lightweight UI Toolkit (LWUIT), da es im Standard-LCDUI kein Tabellen-Widget gibt.
Die App sollte auf so ziemlich allen Java-Handys laufen, wobei ich vermute, dass (obwohl kein Beschleunigungssensor verwendet wird) die Java-Plattform 8 vorausgesetzt wird. Getestet wie immer nur mit einem Sony Ericsson K850i, W980 und C902, mit neueren Geräten sollte es keine Probleme geben.
Hier könnt ihr euch die Anwendung herunterladen und über USB oder Bluetooth auf eurem Handy installieren. Viel Spaß damit!
Bei Interesse veröffentliche ich auch gerne Ausschnitte des Java-Quellcodes.
