Sudoku...

[logo123]

Hi, ich versuche gerade ein Sudoku Lösungsgenarator zu programmieren. Ich weiss nicht wie ich dei einzelnen Zellen miteinander vergleichen kann. Kann mir jemand helfen. Ich habe die daten angehängt.

[logo123]

Hat denn niemand eine Ahnung davon?
Es ist ein Projekt für die Schule und ich möchte nur wissen wie ich das machen soll (Kein Quellcode).Vieleicht ein Struktogramm oder so

[OldGrumpy]

Ahnung davon haben hier sicherlich etliche :)

Strategien zum Lösen eines Sudokus gibt es viele. Für ein Computerprogramm empfiehlt es sich auf jeden Fall, Kandidatenlisten zu führen. D.h. Du hast ja eine Matrix (in den meisten Fällen 9x9 Felder) und an jedem Platz können die Zahlen 1-9 stehen. Im ersten Schritt werden jetzt die Zahlen die im Lösungsfeld schon vorgegeben sind in diese Matrix eingetragen und damit alle anderen Kandidaten für das jeweils betreffende Feld eliminiert.

Danach wendest Du die üblichen Regeln an:

- In jedem 3x3-Block darf 1-9 nur einmal vorkommen, d.h. aus den Kandidatenlisten für diese Felder kannst Du die gerade eingetragene Zahl entfernen.

- In jeder Zeile darf 1-9 nur einmal vorkommen, d.h. aus den Kandidatenlisten in dieser Zeile auch wieder die entsprechenden Ziffern entfernen.

- In jeder Spalte darf 1-9 nur einmal vorkommen, d.h. aus den Kandidatenlisten in dieser Spalte auch wieder die entsprechenden Ziffern entfernen.

Jedes Mal wenn Du irgendwo Kandidaten eliminiert hast, musst Du dann durch das Feld laufen und schauen ob Du irgendwo schon alle Kandidaten bis auf einen eliminiert hast. Den kannst Du dann auch wieder als Lösung eintragen und die entsprechenden Kandidaten (siehe oben) entfernen.

Aus den Kandidatenlisten ergibt sich dann auch noch:

- Wenn ein Kandidat nur in einem Feld einer Zeile vorhanden ist, dann gehört der dort als Lösung hin, also eintragen und weiter wie oben

- Wenn ein Kandidat nur in einem Feld einer Spalte vorhanden ist, dann gehört der dort als Lösung hin, und weiter wie oben.

- Wenn ein Kandidat in einem 3x3-Block.... usw.

Wie Du das jetzt in ein Programm überführst, darfst Du Dir aber erstmal selber überlegen. Nur mit viel Übung wird man Meister :)

[Nuclear-Ping]

Richtig freakig wäre ein Lösungsansatz über "genetische Algorithmen". :D

Kurzeinführung: http://techni.tachemie.uni-leipzig.de/jsga/gakurz.html
Crash-Kurs: http://www.ai-junkie.com/ga/intro/de-gat1.html (hier gibts auf Seite 3 zwei Delphi-Beispiele)

[logo123]

Das Programm guckt jetzt vertikal horizontal und im 3*3 Kasten ob eine Zahl vorhanden ist oder nicht. Was soll ich jetzt machen?

[OldGrumpy]

Mein Posting nochmal lesen, die erledigten Sachen abhaken und den Rest noch einbauen? :mrgreen:

[Kinimod8]

Zum Lösen von Sudokus kannst du mal die DP durchsuchen, den Wikipedia-Eintrag zum Sudoku lesen oder dich direkt über Backtracking informierren (siehe auch Tutorial auf dsdt.info).

[dino]

Zitat:

Zitat von Nuclear-Ping

Richtig freakig wäre ein Lösungsansatz über "genetische Algorithmen". :D

Kurzeinführung: http://techni.tachemie.uni-leipzig.de/jsga/gakurz.html
Crash-Kurs: http://www.ai-junkie.com/ga/intro/de-gat1.html (hier gibts auf Seite 3 zwei Delphi-Beispiele)

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

[Kinimod8]

Zitat:

Zitat von dino

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

Das von OldGrumpy vorgeschlagene Verfahren, das auf einer sehr einfachen Logik basiert, kann aber nur einen minimalen Bruchteil aller Sudoku-Rätsel lösen. Neben dem oben angesprochenen Verfahren des Backtrackings (Try+Error), das für jedes Rätsel eine Lösung findet, gibt es noch eine Vielzahl an Logikverfahren neben den Singles (OldGrumpy). Siehe dazu bspw. auch hier.

[OldGrumpy]

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

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

[Corpsman]

Ho, ich hab mal ein SudokuProgramm geschrieben . Mein NSudoku war dann die Weiterentwicklung. ich hab immer zuerst ein Fertiges Feld erzeugt und das dann Mittels Logik wieder Zerlegt bis das nicht mehr möglich war. so ist sichergestellt das ein "Mensch" oder ein Computer nur durch logische Kombinationen das Rätsel auch lösen kann.

Das Fertige Feld muste ich aber immer mittels Mischung aus Logik und ein bischen Backtracking erzeugen.