j2me_sudoku

5 Beiträge20.05.2006Archiviert
sis409620.05.2006 · Beitrag #7529
Mitglied seit: 08.01.2006
Forenbeiträge: 47
Besuche: 282
hallo,
habe ein "sudoku" solver / generator, in java geschrieben, mittels backtracking. (funktioniert soweit auch)
nun hab ich mich ein bisschen mit java programmen für handys befasst, also genauer
gesagt mit j2me.
nun frage ich mich, ob ein handy die noetige leistung fuer einen backtracking algorithmus
auf einer 9 x 9 matrix verkraften würde oder in moderater zeit lösen kann.
falls jemand schon erfahrungen in dieser richtung gemacht hat, wäre ich dankbar für anregungen.

gruss
squeez20.05.2006 · Beitrag #7530
Mitglied seit: 06.04.2005
Forenbeiträge: 687
Besuche: 668
tach sis4096

... mittels backtracking ...

Aha, bruteforce also ;}
Backtracking ist so ziemlich der langsamste Algorithmus ueberhaupt um ein solches Problem zu loesen.

Die Dauer ist sehr stark abhaengig von der Zahl der vorgegebenen Zahlen.
Wie viele Zahlen willst du den vorgeben?

Vom Speicher her wuerde ich sagen muesste es reichen (gehe von einer rekursiven Implementierung mit einem Stack aus). Das macht im worst case 81 Elemente auf dem Stack. Ueber die Zeit, die benoetigt wird moechte ich mich jetzt aber nicht unterhalten ;}


Fuer eine sinnvolle Einschaetzung deiner Frage waere ein Blick in den Source bestimmt nicht verkehrt.


Mich wuerden an dieser Stelle mal die Zeiten interessieren die deine Implementierung braucht, bis ein sudoku mit 23 vorgegebenen Zeichen geloest ist.



greetz by
Marco
sis409620.05.2006 · Beitrag #7538
Mitglied seit: 08.01.2006
Forenbeiträge: 47
Besuche: 282
also die anzahl der zahlen kannst beliebig waelen, 0 - 81
ich hab mal ein beispiel mit 28 zahlen aus einer zeitschrift genommen,
hierfuer braucht die backtracking methode mit meinem rechner: rund 60 ms
hab hier einen link zum sourcecode, kannst es ja mal ausprobieren.
link: http://server3.cyon.ch/~utgardch/java/sudoku/
warte auf dein feedback
gruss
squeez21.05.2006 · Beitrag #7550
Mitglied seit: 06.04.2005
Forenbeiträge: 687
Besuche: 668
tach sis4096

Ich bin positiv ueberrascht ueber die Geschwindigkeit (bei mir dauert's 10ms).
So rein intuitiv haette ich etwa eine Sekunde geschaetzt (hoppla ;}).

Ich glaube nicht, dass diese Implementierung mit j2me irgend welche Probleme bereiten wird.
Die genauen Details fuer eine praezise Abschaetzung in Zusammenhang mit j2me fehlen mir jedoch.
Ich meine jedoch, dass wenn Spiele auf j2me laufen, auch dein Algo damit keine Probleme haben sollte.

Eine Abschaetzung waere einfacher gewesen, wenn der Algo schlecht implementiert waere ;}

greetz
Marco
sis409621.05.2006 · Beitrag #7551
Mitglied seit: 08.01.2006
Forenbeiträge: 47
Besuche: 282
servus,
besten dank fuer dein feedback. werde dann wohl mal versuchen diesen in j2me zu konvertieren.
10ms sind schon eine hammerleistung.
versuchs mal mit einer 15x15 matrix, da wird wohl auch dein rechner seine muehe haben :-)
gruss