Sudoku...

[Kinimod8]

Zitat:

Zitat von OldGrumpy

Ein gutes Sudoku sollte sich allein mit Logik und nicht mit stumpfem Ausprobieren lösen lassen. Leider wird das oft ignoriert...

Natürlich ist ein Sudoku, das sich vom Menschen auch lösen lässt, zu bevorzugen. Dein Logik-Vorschlag deckt aber zu wenig Denkschritte ab. Sudokus, die sich nur mit dieser Methode lösen lassen, können nur als 'sehr einfach' eingestuft werden. Logik-Solver, die eine Menge Logik-Methoden benutzt, gibt es hier oder (absolut gigantisch) hier.

[OldGrumpy]

Ich hab ja auch nicht behauptet, dass ich alle Methoden kennen würde oder aufzeigen wollte. Vielleicht haette ich ja noch dazuschreiben sollen dass das die Spitze des Eisbergs ist. Aber es macht IMHO mehr Sinn, erstmal laufen zu lernen bevor man rennen lernt :) Und ihn mit zig Strategien zu erschlagen löst zwar ein PICNIC-Problem, aber das auch auf recht radikale Weise :mrgreen:

[dino]

geb ich dir völlig recht

ich habe selbst einen kleinen sudoku computer(von dem freund meiner schwester zum geburtstag geschenkt bekommen) und finde auch immer bessere lösungsstrategien

geschweige denn dem computer sie zu vermitteln

[Nuclear-Ping]

Zitat:

Zitat von dino

hab mir alles angeguckt und finds sehr interessant

doch glaube nciht, dass es so einfach ist alein eine geeignete codierung für eine Lösung zu finden geschweige denn den fitnesswert zu berechnen

dazu bezweifle ich, dass das verfahren besser ist als das, was hier vorgeschlagen wurde, doch darüber lässt sich durchaus streiten

Ich hab nicht gesagt, dass es einfach sei, die Lösung für ein Sudoku ordentlich zu codieren. Ich hab nur gesagt, dass es "freakig" (im Sinne von nicht alltäglich, aussergewöhnlich) wäre, da mit GAs ranzugehen. ;)

Und unterschätze GAs nicht. Sie sind in der Regel meistens effektiver wie "Try 'n Error"-Läufe oder Rekursionen. In den Anwendungsbeispielen da ist nicht allzuviel "praktisches" aufgeführt. Aber man denke nur mal an Routenplaner, Fahrplansuche, Fehleranalyse in Systemen, etc. (siehe auch http://de.wikipedia.org/wiki/Genetische_Algorithmen).

[dino]

try and error ist sowieso das premitivste überhaupt

obwohl dabei schonmal möglich ist, dass man jeden Versuch nur einmal macht
bei anderen Verfahren ist das möglicherweise noch ein Problem

[dino]

also seöbst, was kinimod hier als gigantisch darstellt, ist nicht vollkommen, da es auch mal vorkommen kann, dass alle ihm bekannten strategien ihn nciht weiter bringen

und zwar, weil er die primitivste aller strategien nciht drin hat: raten

ich denke, dass wenn man anfängt zu programieren, dann kann man auch direckt einbauen, dass wenn das Programm nicht mehr weiter kommt, dass er dann anfängt mit try and error weiterzuarbeiten

also das, was zuvor erarbeitet wurde speichern und dann etwas raten und hoffen, dass es sich von da an wieder mit der üblichen logik lösen lässt(ein widerspruch ist auch eine Lösung, denn dann weisst du, dass du die zahl, die geraten wurde an der stelle auf jeden fall schonmal nicht da hinkommt)

[Kinimod8]

Ähmmm, hast du dir Backtracking mal genauer angeguckt? Der größte Teil der Sudoku-Solver setzt auf diese Technik (siehe z.B. hier, hier oder hier).

Zur Verbesserung (und Effizienzsteigerung) der Technik werden dann Logikverfahren eingesetzt, die ich in meinen Posts bereits erwähnt habe.

[dino]

joa schön

hab mir das früher schon angeguckt, habs aber vergessen, woher ich es kenne

jedenfalls macht die page, die du da als genial bezeichnest es nciht

und ich denke, dass kann man in ein anfängerprogramm einbringen, meint ihr nciht?

[imp]

Zitat:

Zitat von dino

..und zwar, weil er die primitivste aller strategien nciht drin hat: raten..

ich denke, ne mutation kann man durchaus auch als ne form des ratens ansehen :-)

[dino]

sprichst du nun von GA?(Genetische Algorithmen oder so)

dass das zum zeil führt habe ich nciht gesagt, sondern die seite, zu der uns

Zitat:

Zitat von Kinimod8

Zitat:

Zitat von OldGrumpy

Ein gutes Sudoku sollte sich allein mit Logik und nicht mit stumpfem Ausprobieren lösen lassen. Leider wird das oft ignoriert...

[..](absolut gigantisch) hier.

hier mit der bemerckung absolut gigantisch verlinkt, führt zwar sehr viele logische tests durch, doch wurde da nciht bedacht, dass wenn all diese test fehlschlagen, dass dann eben alternative strategien gebraucht werden(wie es das raten nunmal ist)