Hallo in die Runde! Ich habe ein spezielles Sudoku welches ich nicht zu Fuß lösen möchte ;-) ( Geocaching-Rätsel ) Hier ein Beispiel: http://2.bp.blogspot.com/-49uYhXVUThA/Tejbsm3h97I/AAAAAAAAARQ/fHzIAI6qcVo/s1600/0006.png Das ganze nennt sich Frame Sudoku oder auch Outside Sum Sudoku. Die Zahl die außen steht ist die Summe der nächsten 3 Zahlen in der jeweiligen Richtung. Kennt jemand von Euch einen Online-Solver für diese Variante. 3h Google habe ich schon hinter mir und selber proggen mag ich net. Danke und Gruß Stefan
Wenn er die 3h zum lösen genutzt hätte vermutlich auch ;-) Wie peinlich ist den das bitte... wenn du keinen Bock hast dann lass das doch mit dem Geocaching.
Läubi .. schrieb: > Wie peinlich ist den das bitte... Peinlich finde ich nur die beiden Antworten. In 3h sowas selbst proggen, da bekomme ich ja einen Lachflash!
Stefan W. schrieb: > In 3h sowas selbst proggen, da bekomme ich ja einen Lachflash! Ja, drei Stunden sind etwas übertrieben, das geht auch in 30 Minuten. Man muss einfach nur die richtigen Tools kennen&nutzen. In dem Fall: Prolog. Einfach die (Frame-) Sudoku-Beschreibung runtertippen, Lösungs-Weg und Lösung sucht der Computer.
Die Aufgabe ist eher trivial. Das ist doch eine gute Uebung... Ich wuerd's mal mit einem Gleichungsystem probieren. Ein Matritze durchlassen und gut ist.
Stefan W. schrieb: > Kennt jemand von Euch einen Online-Solver für diese Variante. Sollen wir den Cache für Dich auch mit loggen? Nicht dass Du schmutzig wirst...
...also ich weiss nicht, ob das wirklich so einfach zu programmieren ist... Für jedes 9er-Feld erhalte ich ja aus den Summen zunächst nur 6 Gleichungen. Also für alle neun Bereiche 54 Gleichungen. Benötigt werden 81 Gleichungen. Die fehlenden 27 Stück kommen aus den 9 Feldsummen und den 9 Reihensummen und den 9 Spaltensummen von jeweils 45 Ingesamt würde es also ein 81x81 Gleichungssystem werden, wenn ich daraus ein LGS bilde... Das System wäre regulär und damit lösbar. Alleine das Einhacken in Matlab würde aber sicher mehr als 2 Stunden benötigen... Matlab würde aufgrund der Regularität auf jeden Fall eine Lösung finden, aber im Aufwand von O². Kann man aufgrund der sudokuspezifischen Regelsätze den Aufwand reduzieren? VG
Großes Fragezeichen schrieb: > Kann man aufgrund der sudokuspezifischen Regelsätze > den Aufwand reduzieren? Naja die "Randzahlen" muss man so oder so abtippen, die Gleichungen für Mathlab könnte man sich dann mit etwas Geschick ggf. generieren lassen. Oder dann halt gleich einen kompletten solver schreiben. Das das ggf. ein paar Minuten bis zur Lösung dauert ist erst mal unerheblich wenn man nicht Millionen der Dinger lösen will oder eine der Ehrgeiz packt ;-) Großes Fragezeichen schrieb: > Alleine das Einhacken in Matlab würde aber sicher mehr > als 2 Stunden benötigen Er hat ja nun schon 3h gegoggelt, hier Beiträge verfasst, ... und Sinn des "Spiels" ist es doch das Rätsel eigenständig zu lösen. Wenn man halt keine Lust dazu hat zwingt einen ja niemand, da er auch nicht "selber proggen mag"...
Großes Fragezeichen schrieb: > Also für alle neun Bereiche 54 Gleichungen. Nix Gleichungen, Rekursion. Muss halt effizient programmiert werden, damit es noch in diesem Jahrhundert fertig wird.
...ist denn eine Rekursive Programmierung schneller als O(N²)? Wenn ja, wird sicherlich eine ganze Menge Speicherplatz benötigt, um falsche Lösungen nicht versehentlich zu wiederholen... VG
Großes Fragezeichen schrieb: > Wenn ja, wird sicherlich eine ganze Menge Speicherplatz benötigt, um > falsche Lösungen nicht versehentlich zu wiederholen... Häh? Das ist ja der Witz bei der Rekursion, dass quasi jedes Feld auf jede Variable getestet wird. Da wird nichts wiederholt. Die Kunst ist, die Abbruchbedingungen clever zu definieren, so dass das Programm recht schnell nicht zielführende Wege erkennt und nicht weiter verfolgt.
Das Verfahren nennt sich aber Backtracking... und das kann man dann rekursiv oder iterativ implementieren....
Backtracking muss im schlechtesten Fall alles abklapprn, quasi Brute-force, das waeren dann N-fakultaet. nein? Nicht ganz. Moment. Jede Zeile braucht 9 Fakultaet. Bin ich mit 9 Fakultaet im Quadrat dabei? Da fehlt noch was...
Siebzehn mal Fuenfzehn schrieb: > Backtracking muss im schlechtesten Fall alles abklapprn, > quasi Brute-force Für ein beliebiges Problem ja, für Sudoku und die hier vorgestellte Variante gibt es aber ungültige Züge, d.h. gewisse Pfade enden vorzeitig bevor man alles durchsuchen musste. Der Trick ist also möglichst gute Abbruchkriterien zu finden, ein "normales" Sudoku kann man innerhalb weniger Sekunden auf einem Standard PC lösen (lassen).
bei einem 9x9 Sudoku dauert Backtracking ein paar ms. Sudoku ist NP-vollständig, also kann man machen was man will schneller als exponentiell wirds nicht selbst wenn man mit Regeln den Rekursionsbaum prunt. Diese Variante kann man aber auch zügig lösen, ist ja nur 9x9.
Thread beobachten
Seitenaufteilung abschalten
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.