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...