Sudoku Solver Schritt für Schritt

[Marcel2906]

Guten Morgen,

Ich habe die Aufgabe bekommen einen Sudoku Solver zu Programmieren.
(Was ich ganz schön schwer finde, da ich erst seit 1 Monat Programmiere und das mein 2. Programm sein wird)
Doch man soll ja nicht schon vorher aufgeben, so habe ich mit meiner Problemanalyse angefangen (s.A.)
Danach soll ich Struktogramme dazu erstellen (s.A.).
Nun wollte ich das Struktogramm zur ersten Lösung-Methode erstellen und komme nicht mehr weiter.
Ich hab mir dann sehr viel Gedanken gemacht und hab die Vermutung, dass ich mir das ganze völlig falsch überlegt habe. In meiner Überlegung habe ich ein Array 9x9 für das Sudoku.
Nun habe ich mir folgenden überlegt, weiß aber nicht ob es funktionieren würde :-P

Anstatt eines Arrays habe ich es unterteilt in:

1 Klasse: Sudoku --> 9 Felder (Array 3x3)
1 Klasse: Feld --> 9 Kästchen (3x3)
1 Klasse: Kästchen --> Kandidaten, fester Wert
Kandidaten --> Array (0-8)

oder bin ich völlig auf dem Holzweg??
Falls einer sehr viel Zeit und Lust hat kann er sich meine Sachen ja mal anschauen.

[FredlFesl]

Ich würde einfach ein 9x9 Feld nehmen.
Dann würde ich für eine Routine schreiben, die für jede Reihe, Spalte und 3x3-Feld die Kandidaten ermittelt und als Menge (SET OF Byte) ablegen

Eine Zelle in Reihe R, Spalte S und in Feld F hat dann die Kandidaten:

Delphi-Quellcode:

Zellen_Kandidaten = Kandidaten_Reihe[R] * Kandidaten_Spalte[S] * Kandidaten_Feld[F]

Das '*' ist hier die Schnittmenge.

Wenn die Menge "Zellen_Kandidaten" aus genau einem Element besteht kann ich die Zelle direkt setzen.
Ist die Menge leer, ist das Sudoku nicht lösbar.
Enthält sie mehr als ein Element, könntest Du alle durchprobieren. Das wird dann aber rekursiv und ist nicht so leicht zu verstehen.

Grundsätzlich geht eine rekursive Lösung so:

Code:

FindeRekursiveLoesung (B : TSpielbrett)
  ZugListe := B.ErstelleListeallerMöglichenZüge();
  Für jeden Zug Z der ZugListe:
    B.FuehreZugAus(Z);
    Wenn B.LoesungGefunden Dann
       B.GibLoesungAus()
    Sonst
       FindeRekursiveLoesung(B);
    B.NimmZugZurueck(Z);
Ende