Sudoku Logik

[hans ditter]

Moin moin,

ich habe mich gestern mal an einem Sudokuspiel versucht. Leider bekomme ich im Moment nichtmal das generieren eines neuen Sudokus hin...:?
Es hapert anscheinend ein wenig an der Logik, wie ich da ran gehe.

Für das Spielfeld benutzte ich ein Stringgrid. Ich dachte mir, ich schreib in das Feld[0,0] eine zufällige Zahl, dann schreib ich in das Feld[0,1] eine zufällige Zahl und überprüfe, ob diese mit irgendeiner anderen Zahl in der Reihe, Spalte oder dem Quadrat kolidiert.

Die Überprüfung des Quadrats hab ich noch nicht, weil ich bis jetzt nochnichtmal die Reihe / Spalte überprüft bekomme.

Digit: zufällige Zahl
Size: Größe (z.B. 4x4)
X, Y: Koordinaten des Felds[x,y] in das geschrieben werden soll

Delphi-Quellcode:

function DigitIsOK(X,Y,Size,Digit: integer):boolean;
var
  i: Integer;
begin
  Result:=false;

  if not(Digit = 0) then
  begin
    for i := 0 to Size do
    begin
      if Digit = StrToInt(Form1.Map.Cells[X,i]) then
        Result:=False
      else Result:=True;
      if Digit = StrToInt(Form1.Map.Cells[i,Y]) then
        Result:=False
      else Result:=True;
    end;
  end
  else
    Result:=false;
end;

Hoffe ihr könnt mir auf die Sprünge helfen...:)

bd, hans ditter

[himitsu]

Entweder vor der schleife das Result auf True setzt.
Sonst überschreibst du ständig den letzen Fund, außer es ist zufällig letzte Zahl der Spalte.

Oder du brichst die Schleife mit Break; ab, nachdem dort False gesetzt wurde.
Hierbei ebenfalls vorher auf True setzen (einmal reicht ja).

Oder mit Exit; die Funktion abbrechen und, falls die Schleife komplett durchlaufen werden konnte (also nix gefunden), dann nachher auf True setzen.

Delphi-Quellcode:

function DigitIsOK(X,Y,Size,Digit: integer):boolean;
var
  i: Integer;
begin
  if not(Digit = 0) then
  begin
    Result:=True;
    for i := 0 to Size do
      if (Digit = StrToInt(Form1.Map.Cells[X,i])) 
          or (Digit = StrToInt(Form1.Map.Cells[i,Y])) then
        Result:=False;
  end
  else
    Result:=false;
end;

Die Verwendung von Form1. gibt schonmal einen deutlichen Hinweis darauf, daß diese Funktion besser zu einer Methode der Form gemacht werden sollte.

[hans ditter]

Erstmal danke für deine Antwort... aber jetzt geht das Prog leider gar nicht mehr... :(

Wenn man jetzt auf neues Spiel klickt, dann hängt sich das Programm auf. Im TaskManager steht dann "Keine Rückmeldung". Bin mal mit dem Debugger rübergegangen, da haben auch alle Funktionen richtig funktioniert, aber leider war hing das Prgramm nach 10 min noch...

Vlt könntest du dir nochmal den Quelltext anschauen.

Delphi-Quellcode:

function CreateNewSudoku(Size: integer) : integer;
var
  x,y,nr: Integer;
begin
  Randomize;
  PrepareMap(Size);
  nr:=0;
  for x := 0 to Size - 1 do //for1
  begin
    for y := 0 to Size - 1 do //for2
    begin
      while not (DigitIsOk(x,y,Size-1,nr)) do
      begin
        nr:=random(4)+1;
      end;
      Form1.Map.Cells[y,x]:=IntToStr(nr);
    end; //for1
  end; //for2 
end;

function DigitIsOK(X,Y,Size,Digit: integer):boolean;
var
  i: Integer;
begin
  Result:=True;

  if not(Digit = 0) then
  begin
    for i := 0 to Size do
    begin
      if (Digit = StrToInt(Form1.Map.Cells[X,i])) OR
         (Digit = StrToInt(Form1.Map.Cells[i,Y])) then
        begin
          Result:=False;
          Break;
        end;
    end;
  end
  else
    Result:=false;
end;

[JasonDX]

Zitat:

Zitat von hans ditter (Beitrag 1069555)

Erstmal danke für deine Antwort... aber jetzt geht das Prog leider gar nicht mehr... :(

Wenn man jetzt auf neues Spiel klickt, dann hängt sich das Programm auf. Im TaskManager steht dann "Keine Rückmeldung". Bin mal mit dem Debugger rübergegangen, da haben auch alle Funktionen richtig funktioniert, aber leider war hing das Prgramm nach 10 min noch...

Ein Fehler im Code ist folgender:

Zitat:

Zitat von hans ditter (Beitrag 1069555)

Delphi-Quellcode:

nr:=random(4)+1;

Statt der 4 sollte ein Size hin, ansonsten würde das Generieren nur mit 4x4-Sudokus funktionieren.
Zudem fehlt das Backtracking in deinem Algorithmus. Mal angenommen du willst ein 4x4-Sudoku generieren, und dein Programm ist bei folgendem Sudoku angelangt:

Code:

1 2 3 4
2 3 1 x

Ist soweit alles gültig, bloß wird dein Programm hier für x keine Zahl finden, für die das Sudoku gültig ist. Also sucht der Algorithmus (per Zufall) ewig nach einer Zahl, die es nicht gibt.

Btw:

Zitat:

Zitat von hans ditter (Beitrag 1069479)

Leider bekomme ich im Moment nichtmal das generieren eines neuen Sudokus hin...:?

Das Generieren von Logikpuzzeln ist um Welten schwieriger als das Lösen ;)

greetz
Mike

[hans ditter]

Ah ja... hatte ich schon fast befürchtet, dass das in die Richtung geht.... -.-

Kannst du mir was zu Backtracking erzählen? Backtracking = zurück suchen ?? Ich würd mir drunter vorstellen, dass man alle Schritte irgendwie speichert und dann rückgehen schaut, ob das ganze funktionieren kann. Aber ich hab definitiv keine Ahnung wie das gehen soll!!

lg, hans ditter

[JasonDX]

Zitat:

Zitat von hans ditter (Beitrag 1069579)

Kannst du mir was zu Backtracking erzählen? Backtracking = zurück suchen ?? Ich würd mir drunter vorstellen, dass man alle Schritte irgendwie speichert und dann rückgehen schaut, ob das ganze funktionieren kann.

Grob beschrieben ist das Backtracking. Man trifft Entscheidungen, und wenn man an einen Widerspruch/Fehler gerät, ändert man eine (normalerweise die letzte) Entscheidung und probiert dann weiter. Wikipedia hat auch nen eigenen Eintrag dazu.
Auf Sudoku angewand würde das ca. so aussehn (der Einfachheit halber rekursiv beschrieben):

Code:

SetzeFeld(i)
  Wenn i > Size*Size
    return true; //Abbruchbedingung
  GültigeEntscheidungen = {1..Size}
  solange Anzahl(GültigeEntscheidungen) > 0
    Wähle zufällige, gültige Entscheidung x //(z.B. x=3, d.h. ins i-te Feld wird eine 3 geschrieben)
    Wenn EntscheidungGültig(i, x) //x ist auf dem i-ten Feld gültig
      Setze(i, x)
      Wenn SetzeFeld(i+1) //Probieren, das restliche Sudoku zu füllen
        return true;      //Sudoku konnte gefüllt werden, also Funktion "erfolgreich" beenden
    Entferne x aus GültigeEntscheidungen //Weil x keine gültige Entscheidung war
  return false //keine Gültige Entscheidung gefunden, also muss in den vorherigen Feldern was geändert werden

Das ist dann eine sehr einfache Implementierung von Backtracking. Dadurch, dass man Rekursion anwendet, muss man auch nicht ehemalige Entscheidungen speichern, bzw. der Compiler&Stack erledigen das für einen.
Wie schnell dieser Code dann läuft hängt sehr davon ab, wie man die Gültigkeit einer Entscheidung überprüft. Diese muss natürlich false zurückgeben, (genau dann) wenn die Zahl nicht gültig ist. Hier ist aber bspw. auch bereits viel Optimierungs-Potential drin. Im weiter oben genannten Beispiel könnte die Funktion auch bereits erkennen, dass die 1 im 7. Feld nicht gültig ist. Hierfür können dann die verschiedensten Methoden zum Einsatz kommen.

greetz
Mike

[hans ditter]

Danke Mike,

deine Beschreibung hört sich erstmal reichlich wirr an, werd mich aber mal ransetzten und probieren die umzusetzten. :zwinker: Ich poste dann mein Endergebnis hier, wenn man da dann nochmal rüberschauen könnte, wäre das klasse!

LG, hans ditter

[hans ditter]

Hi Mike,

hab mich mal mit deinem Beitrag beschäftigt. Da sind allerdings 2 Fragen aufgetaucht:
1.)

Delphi-Quellcode:

Wenn i > Size * Size

--> wofür braucht man das? was bedeutet es?
2.)

Delphi-Quellcode:

Gueltige Entscheidung = {0..Size}

--> was ist das? ein Array? wie ist es aufgebaut?

Zu 2.: Ich dachte schonmal an ein Array of Array, dass man dann ein 4x4 Array z.B. anlegt, für jedes einzelne Feld im Sudoku und in dem Arrayfeld dann ein weiters Array oder Record speichert, für alle zulässigen Zahlen dieses Feldes. Wäre das praktikabel und sinnvoll?

LG, hans ditter

P.S.: Mein Quelltext zu deinem Post soll heute noch folgen, also vlt heute abend nochmal reinschauen... ;) würd mich freuen!

[JasonDX]

Zitat:

Zitat von hans ditter (Beitrag 1070505)

1.)

Delphi-Quellcode:

Wenn i > Size * Size

--> wofür braucht man das? was bedeutet es?

Das ist die Abbruchbedingung. i zählt mit, das wievielte Feld gerade gefüllt wird. Wenn i dann größer als Size*Size ist, dann hat man bereits alle Felder gefüllt.

Zitat:

Zitat von hans ditter (Beitrag 1070505)

2.)

Delphi-Quellcode:

Gueltige Entscheidung = {0..Size}

--> was ist das? ein Array? wie ist es aufgebaut?

Das ist eine Liste oder ein Array (in dem Fall eigentlich egal), und enthält, welche Entscheidungen gültig sind, bzw. noch nicht durchprobiert wurden.

Zitat:

Zitat von hans ditter (Beitrag 1070505)

Zu 2.: Ich dachte schonmal an ein Array of Array, dass man dann ein 4x4 Array z.B. anlegt, für jedes einzelne Feld im Sudoku und in dem Arrayfeld dann ein weiters Array oder Record speichert, für alle zulässigen Zahlen dieses Feldes. Wäre das praktikabel und sinnvoll?

Durchaus - allerdings muss man damit aufpassen, wenn man zu viel damit optimiert. Nehmen wir an der Algorithmus trifft eine Entscheidung, und deshalb ist eine Zahl in einem späteren Feld nicht mehr gültig. Die Entscheidung wird aber rückgängig gemacht - dann muss diese Zahl in dem späteren Feld wieder zu den gültigen Zahlen hinzugefügt werden. Entweder indem alle gültigen Zahlen erneut berechnet werden, oder indem man speichert, wegen welcher Entscheidung eine Zahl als ungültig markiert wurde.
Die beschriebene rekursive Methode vereinfacht diesen Prozess. Man kann dort, bevor man beginnt verschiedene Entscheidungen durchzuprobieren, offensichtlich ungültige Entscheidungen entfernen. Ums Zurücksetzen von Entscheidungen muss man sich dann nicht kümmern - das wird durch die Rekursion direkt erledigt.

greetz
Mike

[hans ditter]

Hi,
danke für deine Antwort.

Ich sehe jetzt schon deutlich klarer. Aber eine Sache ist noch nicht ganz "aus dem Nebel aufgetaucht"...:wink:
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?

So, dann mach ich mich wohl mal an den Quelltext ran... :D

LG, hans ditter

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

Zitat von hans ditter (Beitrag 1070542)

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:

Zitat von hans ditter (Beitrag 1070544)

Delphi-Quellcode:

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:

Zitat von hans ditter (Beitrag 1070544)

Delphi-Quellcode:

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:

Delphi-Quellcode:

nr:=ValidDigit[random(length(ValidDigit))]

Zitat:

Zitat von hans ditter (Beitrag 1070544)

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:

Zitat von hans ditter (Beitrag 1070544)

Delphi-Quellcode:

Delete(nr);

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

Zitat:

Zitat von hans ditter (Beitrag 1070544)

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

Zitat von hans ditter (Beitrag 1070552)

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:

Zitat von hans ditter (Beitrag 1070555)

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

hans ditter

[implementation]

Zitat:

Zitat von hans ditter (Beitrag 1071087)

i mod 4 = 2 mod 4 = 0... x müsste aber 2 sein...

:wiejetzt:
Weißt du, was mod bedeutet?

Sieh's als Division mit Rest:
2 durch 4 = 0 Rest 2

Der Rest ist das Modulo:
2 div 4 = 0 <-- Y
2 mod 4 = 2 <-- X

[hans ditter]

[edit]
Ich hab grad nochmal ein wenig rumgerechnet... Wenn ich jetzt für i=2 setzte ergibt sich mit deiner Rechenweise folgendes Ergebnis:
X: 2 mod 4 = 2--> hier müsste eig. 1 stehen
Y: 2 div 4 = 0

Bei i=12 folgendes:
12 mod 4 = 0 --> steht für nichts... bei 12 kommt keine Koordinate 0 vor
12 div 4 = 3 --> steht hier für X, statt für Y

Wo ist denn schon wieder der Fehler??:glaskugel: Ich glaub ich sitzt zu dicht vor meinem Problem... :coder2:, seh praktisch den Wald vor lauter Bäumen nicht mehr.:pale:
[/edit]

:cyclops::feuerchen: ich danke dir!! Jetzt hab ich's verstanden.
Also bedeutet mod, den Rest, der noch gebraucht wird...

Bei 2 div 4 sagt uns das, 4 passt kein Mal in 2, deswegen Ergebnis=0
Bei 2 mod 4 heisst das, dass 4 immer noch nicht in 2 passt, aber ein Rest von (eigentlich -)2 überbleibt und deswegen Ergebnis=2.

[hans ditter]

Ich denke, ich konnte das Problem jetzt lösen... soll heissen, dass ich's noch nicht als Quelltext probiert hab!

Die Nummerierung i der Felder muss bei NULL anfangen, da war mein Fehler, meines Erachtens!

Code:

_|_0_|_1_|_2_|_3_|
0| 0 | 1 | 2 | 3 |
1| 4 | 5 | ...
2|
3|

Ich hatte die Nummerierung immer bei 1 angefangen. Jetzt kommen auch alle Rechungen hin! :thumb:

2 Beispiele:

i = 2
X = 2 mod 4(Size) = 0 --> richtig
Y = 2 div 4 = 2 --> richtig

i = 5
X = 5 mod 4 = 1 --> richtig
Y = 5 div 4 = 1 --> richtig

Es funktioniert!! :thumb::thumb:

[Sani93]

ähm sorry das ich frag, aber ich bin ganz neu hier und hab KEINE ahnung wie man ein eigenes thema erstellt. ich bin hier am verzweifeln -.-
wäre sehr nett, wenn mir jmd sagen könnte (am besten via nachricht) wie ich das mache :)

[LWChris]

Zitat:

Zitat von Sani93 (Beitrag 1072484)

ähm sorry das ich frag, aber ich bin ganz neu hier und hab KEINE ahnung wie man ein eigenes thema erstellt. ich bin hier am verzweifeln -.-
wäre sehr nett, wenn mir jmd sagen könnte (am besten via nachricht) wie ich das mache :)

Geh ins Allgemeine Forum, wähle das zu deiner Frage passende Unterforum aus, und klicke dort auf den großen Button "Neues Thema erstellen".

Zur Topic: ich hab mal einen ganz anderen Ansatz für euch, den ich mir mal für das automatisierte Lösen von Sudokus bis 9x9 überlegt habe: Ihr erzeugt entsprechend der Größe des Sudokus ein mehrdimensionales Array of String, in den String schreibt man alle möglichen Werte, und löscht sie beim Setzen aus den anderen Feldern raus. Sobald ein Feld leer ist, ist die Erstellung des Sudokus gescheitert.

So könnte man das Sudoku rekursiv füllen: Setze Feld für Feld einen der möglichen Werte zufällig ein. Versuche dann, den nächsten Wert zu setzen. Stellst du fest, dass es nicht mehr lösbar ist, breche ab mit Ergebnis false. Wähle in diesem Fall (wieder in der übergeordneten Ebene) einen anderen der noch möglichen Werte aus. Ist kein Wert mehr möglich, breche wieder ab mit Ergebnis false.

Delphi-Quellcode:

type TSudoku: Array[1..9] of Array[1..9] of String[9];

procedure NeuesSudoku(var Sudoku: TSudoku);
var a, b: Integer;
begin
  for a:=1 to 9 do
    for b:=1 to 9 do
      Sudoku[a][b]:='123456789';
end;

function FeldIstGesetzt(var Sudoku: TSudokuZeile, Spalte: Integer): Boolean;
begin
  result:=Length(Sudoku[Zeile][Spalte])=1;
end;

procedure BlockeWertInFeld(var Sudoku: TSudoku; Zeile, Spalte: Integer; Wert: Char);
begin
  Feld:=Sudoku[Zeile][Spalte];
  Sudoku[Zeile][Spalte]:=Copy(Feld,1,Pos(Wert,Feld)-1)+Copy(Feld,Pos(Wert,Feld)+1,Length(Feld));
end;

function Erstellbar(var Sudoku: TSudoku): Boolean;
var a, b: Integer;
begin
  result:=true;
  for a:=1 to 9 do
    for b:=1 to 9 do
      if Length(Sudoku[a][b])=0 then
        result:=false;
end;

function Erstellt(var Sudoku: TSudoku): Boolean;
var a, b: Integer;
begin
  result:=true;
  for a:=1 to 9 do
    for b:=1 to 9 do
      if Length(Sudoku[a][b])>1 then
        result:=false;
end;

function SetzeFeld(var Sudoku: TSudoku; Zeile, Spalte: Integer; Wert: Char): Boolean;
var a, b: Integer;
begin
  if Pos(Wert,Sudoku[Zeile][Spalte])>0 then
    begin
      Sudoku[Zeile][Spalte]:=Wert;
      // Wert für alle Felder in Zeile und Spalte blocken;
      for a:=1 to 9 do
        begin
          BlockeWertInFeld(a,Spalte,Wert);
          BlockeWertInFeld(Zeile,a,Wert);
        end;
      // Wert für Quadrat blocken
      Zeile:=((Zeile-1) DIV 3)*3+1;
      Spalte:=((Spalte-1) DIV 3)*3+1;
      for a:=Zeile to Zeile+2 do
        for b:=Spalte to Spalte+2 do
          BlockeWertInFeld(a,b,Wert);
      result:=true;
    end
  else
    result:=false;
end;

function ErstelleSudoku(var Sudoku: TSudoku; Zeile, Spalte: Integer): Boolean;
var Klon: TSudoku; a, b: Integer; M: String; Wert: Char;
begin
  result:=false;
  if Erstellbar(Sudoku) then
    begin
      if Spalte=10 then
        begin
          Spalte:=1;
          Inc(Zeile);
        end;
      if Zeile=10 then
        result:=true // Alle Zeilen und Spalten voll
      else
        begin
          M:=Sudoku[Zeile][Spalte]; // Mögliche Werte
          while (M<>'') and (not result) do
            begin
              for a:=1 to 9 do
                for b:=1 to 9 do
                  Klon[a][b]:=Sudoku[a][b];
              Wert:=M[Math.Random(Length(M))];
              SetzeFeld(Klon,Zeile,Spale,Wert);
              M:=Copy(M,1,Pos(Wert,M)-1)+Copy(M,Pos(Wert,M)+1,Length(M));
              result:=ErstelleSudoku(Klon,Zeile,Spalte+1);
            end;
          if result then
            for a:=1 to 9 do
              for b:=1 to 9 do
                Sudoku[a][b]:=Klon[a][b];
        end;
    end;
end;

procedure ErstelleNeuesSudoku(var Sudoku: TSudoku);
begin
  NeuesSudoku(Sudoku);
  ErstelleSudoku(Sudoku,1,1);
end;

Das ist mein Beitrag, ungetestet, rein auf Logik und theoretischer Vorstellung basierend. Eurer Part wäre es jetzt, das Ding zu prüfen, ggf. zu reparieren und/oder variabel hinzubiegen und auf die StringGrid anzupassen. :D

Chris

[Kalakmul]

Zu dem Themenkomplex Backtracking-Algorithmus/Sudoku-Solver gibt es übrigens hier http://academicearth.org/lectures/ba...ing-pseudocode eine wie ich finde sehr interessante Vorlesung der Stanford University als Video.

Als Programmiersprache wird zwar nicht Delphi verwendet, sondern zumeist einfache Java- bzw. Pseudocodekonstrukte, die sich aber in jede Sprache leicht übertragen lassen sollten. Auch die anderen Videos sind sehenswert.

[hans ditter]

Hi Chris.

Interessanter Ansatz! Daran hab ich auch schonmal gedacht, ein Array of Array zu erzeugen. Aber so wie es im Moment ist, ist es erstmal einfacher für mich. Das muss ich erstmal hinbekommen, dann versuch ich mich vielleicht an deiner Idee... :zwinker:

Denn wie es hesst es so schön:
Immer langsam mit den jungen Pferden! :D

LG, hans ditter

[hans ditter]

Also, ich hab gerade festgestellt, dass mein Turbo Delphi kein return für Funktionen kennt. Oder hab ich vergessen, irgendeine Unit einzubinden?

Ich wollte das machen:

Delphi-Quellcode:

function SetCell(i: integer) : boolean;
begin
  if i > Size * Size then
    return true;

[Kalakmul]

Hallo Hans,

den Befehl "Return" hast Du wohl aus irgend einer anderen Programmiersprache. In Delphi wird der Rückgabewert mit

Code:

Result := True

zurückgegeben. Alternativ kann man auch den Namen der Funktion nehmen also:

Code:

SetCell := True

.

Ich bevorzuge die erste Variante, da der Code dann leichter zu warten ist (z. B. bei späterer Änderung des Funktionsnamens).

Als Fan von Online-Videos darf ich vielleicht noch ein schönes Video von Nick Hodges dazu empfehlen:
http://video.embarcadero.com/pix/nic...rocedures.html

[hans ditter]

Also, schau mal bitte in diesen Beitrag.... Da wird definitiv return benutzt (und ja sogar erklärt...).

Kann aber auch sein, dass unser lieber Jason da was durcheinander gebracht hat. :zwinker:

[JasonDX]

Zitat:

Zitat von hans ditter (Beitrag 1073335)

Also, schau mal bitte in diesen Beitrag.... Da wird definitiv return benutzt (und ja sogar erklärt...).

Kann aber auch sein, dass unser lieber Jason da was durcheinander gebracht hat. :zwinker:

Ich habe das ganze in Pseudo-Code geschrieben. ;)

greetz
Mike

[hans ditter]

Oh...:oops: das hab ich dann wohl etwas missverstanden... :oops:

Naja, dann muss ich also retunr doch selber "ausschreiben"... :D

Danke!

[hans ditter]

Also, ich hab jetzt gerade mal den Pseudocode umgesetzt in meinem Programm. Ob er funktioniert, kann ich noch nicht sagen, da er mir (unverständlicherweise) an einer Stelle sagt, dass " '' ist kein gültiger Integerwert".

Hier mal der Code, mit dem alle Zellen gefüllter werden (sollen):

Delphi-Quellcode:

function SetCell(i: integer) : boolean;
var ValidDecision: TStringList;
  j,X,Y: Integer;
  dig: string;
begin
  if i > (Size * Size) - 1 then
  begin
    Result:=true;
    Exit;
  end;
{.....................................................................}
  ValidDecision:=TStringList.Create;
  for j := 1 to Size do
    ValidDecision.Add(IntToStr(j));
{.....................................................................}
  while ValidDecision.Count > 0 do
  begin
    dig:=ValidDecision[random(ValidDecision.Count)];
    if DigitIsOk(i,StrToInt(dig)) then //hier kommt der Fehler!
    begin
      X:=i mod Size;
      Y:=i div Size;
      Form1.Map.Cells[X,Y]:=dig;
      if SetCell(i + 1) then
      begin
        Result:=True;
        Exit;
      end
      else
      begin
        ValidDecision.Delete(ValidDecision.IndexOf(dig));
        dig:=ValidDecision[random(ValidDecision.Count)];
      end;
    end
    else
      ValidDecision.Delete(ValidDecision.IndexOf(dig));
  end;

  ValidDecision.Free;

  Result:=False;
end;

Und dann noch die Überprüfung der Zahl:

Delphi-Quellcode:

function DigitIsOK(i,Digit: integer):boolean;
var
  j: Integer;
  X,Y: integer;
begin
  X:=i mod Size;
  Y:=i div Size;

  Result:=True;

  if not(Digit = 0) then
  begin
    for j := 0 to Size do
    begin
      if (Digit = StrToInt(Form1.Map.Cells[X,i])) OR
         (Digit = StrToInt(Form1.Map.Cells[i,Y])) then
        begin
          Result:=False;
          Break;
        end;
    end;
  end
  else
    Result:=false;
end;

Der Fehler kommt so zwischen der 4. und 5. Zelle. Ich kann mir das nicht so richitg erklären, weil hier die Sprache davon ist, dass i='' ist. Aber wieso? Hoffentlich könnt ihr mir nochmal aus der Patsche helfen.

LG, hans ditter

[Notxor]

Scheint so als hättest du statt "j" ein "i" (oder umgekehrt).

[hans ditter]

hm, ich hab's grade mal geändert (hattest übrigens recht, das i sollte ein j sein), hat aber nichts geändert.
Ich glaube eher, dass dig irgendwie '' ist. Aber ich weiß nicht warum.
Könntet ihr dahingehend nochmal durchschauen? Such auch schon seit ein paar Stunden nach dem Fehler... :(

[Notxor]

Ich glaub da fehlt ein " -1 ", also

Delphi-Quellcode:

dig:=ValidDecision[random(ValidDecision.Count -1 )];

.

[hans ditter]

Hast du absolut Recht... das fehlte!
Aber leider behebt es immer noch nicht mein Problem. Ich glaube fast, dass es irgendwie einen falschen Zugriff auf eine falsche TStringList gibt.
Oh man, ich komm einfach nicht weiter...:roll:

[Notxor]

Da fehlt noch (mindestens) ein "-1" (glaub ich jedenfalls), und zwar in der

Delphi-Quellcode:

DigitIsOk

bei

Delphi-Quellcode:

for j := 0 to Size -1 do

[Jumpy]

Wie lösche ich den Post wenn ich gerade Müll geschrieben habe????

Egal, versuch ich was evtl. sinnvolles:

Aus der Hilfe: Random gibt eine Zufallszahl im Bereich 0 <= X < Range zurück.

Also ist die -1 in

Delphi-Quellcode:

dig:=ValidDecision[random(ValidDecision.Count -1 )];

doch eher falsch, da random so Zahlen kleiner ValidDecision.Count-1 zurückliefert und nicht kleiner ValidDecision.Count, wie es eigentlich sein soll.
Somit eher wieder:

Delphi-Quellcode:

dig:=ValidDecision[random(ValidDecision.Count)];

[hans ditter]

Also, ich hab jetzt beides nochmal überprüft.
@Notxor
Ich hab's geändert. Hat auch schonmal was gebracht. Da hat's dann jedesmal funktioniert. Jedes andere 2te Mal kam aber die Fehlermeldung, dass der Litenindex überschritten wurde.

@Jumpy
Ich glaube löschen geht nicht! :D
Ich hab das auch bei dir geändert. Hat dann dazu geführt, dass ich ca. 10-15 Mal ein Sudoku erzeugen konnte. Aber auch dann kam die Fehlermeldung mit dem überschrittenem Listenindex.

EDIT!!!!

Hier die Fehlerstelle:

Delphi-Quellcode:

function SetCell(i: integer) : boolean;
var ValidDecision: TStringList;
  j,X,Y: Integer;
  dig: string;
begin
  if i > (Size * Size - 1) then
  begin
    Result:=true;
    Exit;
  end;
{.....................................................................}
  ValidDecision:=TStringList.Create;
  for j := 1 to Size do
    ValidDecision.Add(IntToStr(j));
{.....................................................................}
  while ValidDecision.Count > 0 do
  begin
    dig:=ValidDecision[random(ValidDecision.Count)];
    if DigitIsOk(i,StrToInt(dig)) then
    begin
      X:=i mod Size;
      Y:=i div Size;
      Form1.Map.Cells[X,Y]:=dig;
      if SetCell(i + 1) then //hier kommt der Fehler!!!
      begin
        Result:=True;
        Exit;
     (* end
      else
      begin
        ValidDecision.Delete(ValidDecision.IndexOf(dig));
        dig:=ValidDecision[random(ValidDecision.Count)]; *)
//hier ist der Fehler. Der else-Zweig ist total überflüssig!!
      end;
    end
    else
      ValidDecision.Delete(ValidDecision.IndexOf(dig));
  end;

  ValidDecision.Free;

  Result:=False;
end;

[Edit2]
Jetzt bräuchte ich nur nochmal Hilfe mit den Quadraten. Wie kann ich die möglichst dynamisch abfragen?
Hab grad schonmal ein bisschen mit Formeln rumjonliert.. ;) ist aber nicht wirklich was bei rausgekommen.
Man müsste ja auf jeden Fall wissen, wie groß das Spielfeld ist. Das ist wohl auch nicht das Problem.
Vielmehr ist dann die Frage, wie man die einzelnen (von der Anzahl her ja auch noch variierenden) Quadrate überprüft.
Gibt es da irgendeinen mathematischen Weg oder muss man das mit lauter if-Schleifen abfragen? Wenn 2teres: Wie macht man das "dynamisch"?