Sudoku Logik

[hans ditter]

Delphi-Quellcode:

function SetDigit(X,Y,Size: integer) : boolean
var ValidDigit: [0..Size] as array of integer;
    nr: integer;
begin
   if (X > Size) OR (Y > Size) then
      Result:=true;
   while ValidDigit > 0 do
   begin
      nr:=random(length(ValidDigit))
      if DigitIsOk(X,Y,nr) then
      begin
         StringGrid1.Cells[X,Y]:=nr;
         if SetDigit(X+1,Y,Size) then
            Result:=True;
      end
      else
         Delete(nr);
   end
   else
      Result:=false;
end

so, nun nochmal einige Anmerkungen:
- ich hab diesen Code noch nicht selbst getestet
- ... dass hab ich noch nicht, weil ich noch ein paar Schwierigkeiten hab
- ... diese liegen vor allem im Umgang mit dem Array, was ich hier erstellen wollte
- ... und als letztes noch in der Frage, ob es für eine while-Schleife auch einen else-Zweig gibt.

angenehme Nachtruhe,
hans ditter

[JasonDX]

Zitat von hans ditter:

Hi,
Wird versucht, in SetzeFeld das gesamte Sudoku zu füllen? Es sieht für mich gerade so aus, dass immer wieder SetzeFeld aufgerufen wird, wenn eine Entscheidung gültig war. Das würde dann aber bedeuten, dass ich am Anfang nur einmal sagen muss, dass er für Feld 1 SetzeFeld aufrufen soll, weil sich der Rest dann eh alleine erledigt... hab ich das richitg verstanden?

Ja Du rufst SetzeFeld für das 1. Feld auf, und das füllt dann durch die rekursiven Aufrufe das gesamte Sudoku.

Hier mal die Fehler die mir beim groben Überfliegen aufgefallen sind:

Zitat von hans ditter:

while ValidDigit > 0 do

Die Variable GültigeEntscheidungen aus dem PseudeCode ist eine Menge; Die Bedingung für die While-Schleife ist an die Anzahl der Elemente in dieser Menge geknüpft. Am einfachsten gehts hier tatsächlich mit einer Liste.

Zitat von hans ditter:

nr:=random(length(ValidDigit))

ValidDigit enthält ja alle noch gültigen Entscheidungen, aus der eine gewählt werden sollt. Folglich wäre das hier richtig:
nr:=ValidDigit[random(length(ValidDigit))]

Zitat von hans ditter:

Delphi-Quellcode:

if SetDigit(X+1,Y,Size) then
  Result:=True;

Zum einen: X+1 geht nur solange gut, bis X > Size wird; Dann muss die nächste Zeile genommen werden (Y+1). Zum anderen reicht ein result := true; nicht - Die Funktion muss komplett beendet werden.

Zitat von hans ditter:

Delete(nr);

Deswegen würde ich auf eine Liste zurückgreifen. Hier kann man dies einfacher implementieren.

Zitat von hans ditter:

- ... und als letztes noch in der Frage, ob es für eine while-Schleife auch einen else-Zweig gibt.

Nein Eine While-Schleife kennt kein else.

greetz
Mike

[hans ditter]

Eine superschnelle Antwort, danke!

Ich hab auch schon dran gedacht, dass das mit X+1 nicht ganz funkionieren kann, aber wie sollte ich das dann machen? Ich habe ja ein StringGrid, da muss ich ja sozusagen X- und Y-Koordinate angeben. Da funktioniert dass dann mit einem einfachen i irgendwie nicht so richtig, oder?
Sonst würde mir nur ein eindimensinales Array einfallen, dass die Zellen z.B. von oben-links nach unten-rechts eindimensional speichert, aber ob das performant ist...

Und dann noch zu deiner letzten Aussage, dass eine while-Schleife keinen else-Zweig besitzt:
Dann versteh ich in deinem Pseudo-Code aber die letzte Zeile nicht. Ich hab die so verstanden, dass wenn keine gültigen Zahlen mehr vorhanden sind, man false zurückgibt. Oder hab ich da was vermischt? Bin nur drauf gekommen, weil das result:=false auf der gleichen Höhe wie solange Anzahl etc. steht.

Auf einen kleinen Gedankenanstoß freue ich mich!

hans ditter

[implementation]

Überlege mal genau, was eine While-Schleife tut.

Sie wiederholt Anweisungen solange, bis die Bedingung nicht mehr eintrifft.

Demnach:

Delphi-Quellcode:

while Bedingung do
begin
  // Bedingung trifft zu
end;
// Bedingung trifft nicht mehr zu

Also braucht eine solche Schleife schonmal gar kein else.

Alles, was passieren soll, wenn die Bedingung nicht zutrifft, kann einfach hinter der Schleife platziert werden.

[hans ditter]

Hm, ja, ist eigentlich auch richtig.
Ich fand es nur komisch, dass ganz am Ende einfach mal gesagt wird: "Das Ergebnis ist jetzt falsch!".
Deswegen war ich etwas verwirrt. Aber dann gehört das wohl so...

hans ditter

[JasonDX]

Zitat von hans ditter:

Ich hab auch schon dran gedacht, dass das mit X+1 nicht ganz funkionieren kann, aber wie sollte ich das dann machen? Ich habe ja ein StringGrid, da muss ich ja sozusagen X- und Y-Koordinate angeben. Da funktioniert dass dann mit einem einfachen i irgendwie nicht so richtig, oder?

Es geht sowohl mit einem einfachen i, als auch mit einem (X,Y)-Paar.
Mit einer einzelnen Variable würde es so funktionieren, dass man aus der Variable dann die X und Y-Koordinaten berechnet (Mit mod und div). Andernfalls kann man auch einfach nur die Unterscheidung zu Beginn der Funktion machen: Wenn X > Size, dann X := 1 und inc(Y).

Zitat von hans ditter:

Hm, ja, ist eigentlich auch richtig.
Ich fand es nur komisch, dass ganz am Ende einfach mal gesagt wird: "Das Ergebnis ist jetzt falsch!".
Deswegen war ich etwas verwirrt. Aber dann gehört das wohl so...

Hm, ich glaube am verwirrendsten ist das return. return true entspricht in Delphi folgendem:

Delphi-Quellcode:

result := true;
Exit();

Wenn also eine richtige Belegung gefunden wurde, wird die Funktion bereits in der Schleife beendet.

greetz
Mike

[hans ditter]

achso... also bedeutet das, dass bei return := true das Ergebnis der Funktion auf Wahr gesetzt und die Funktion gleichzeitig verlassen wird? Dann ist mir einiges klarer geworden.

Bin jetzt erstmal essen und dann Theorie... kommt aber nochmal ein überarbeiteter Quellcode dann.

Danke und LG,

hans ditter

[hans ditter]

Also, ich knabber im Moment noch ein wenig an der Auswahl des Feldes...
Da ich das ja mit einem einfachen 'i' machen soll (was ja auch Sinn ergibt), müsste man das dann ja wohl umrechnen. Nur leider will mir nicht richtig in den Kopf, wie das gehen soll.

Also, meine bisherigen Überlegungen:

Ich habe ein Spielfeld der Größe 4 x 4. Die Beschriftung der Felder ist (hier nur sporadisch) so:

1 - 2 - 3 - 4
5 - 6 - 7 - 8
usw.

Nun gebe ich für i=2 an:
(i mod 2) = 0 richtig!
i div 2 - 1 = 1 auch richtig!

Für i=10
(10 mod i) - 1 = 1 korrekt!
10 div i = 2 auch korrekt!

Aber, ist euch bestimmt aufgefallen, die beiden Rechnungen stimmen nicht überein. Hab das z.T. mal rot markiert. Aber wo ist mein Denkfehler?

Was würde denn passieren, wenn man 2 mod 4 nimmt? Dann müsste ja eig null rauskommmen, genauso wie bei 2 div 4, oder?

Ich brauch nochmal eure Hilfe!

hans ditter

[BUG]

Code:

yx| 00 01 02 03
---------------
0 | 00 01 02 03
1 | 04 05 06 07
2 | 08 09 10 11
3 | 12 13 14 15

Delphi-Quellcode:

x := i mod 4;
y := i div 4;

[hans ditter]

aber wie würdest du die X-Koordinate für i=2 herausfinden?
i mod 4 = 2 mod 4 = 0... x müsste aber 2 sein...

also irgendwie ist das auch noch nicht ganz ausgereift... Wie macht man das bloß, es sind Ferien, ich merks...

hans ditter