Sudoku Logik

[Jumpy]

Wenn man von rein Quadratischen Sudokus ausgeht, so ist Size bei dir ja die Größe des Hauptquarates. Die Wurzel aus Size gibt dir dann die größe der kleinen Quadrate und die Info wieviele davon in einer Reihe/Spalte stehen.

Deine X und Y Werte liefern dir wieder mit mod und div die Infos die du brauchst. Wenn Smallsize = Wurzel(Size) ist könnte es so gehen:

x div Smallsize = "X Nummer des kleinen Quadrats"
x mod Smallzise = "X Position deiner Zahl im kleinen Quadrat"

Beispiel oberste Reihe eines 9ers: 0,1,2 / 3,4,5 / 6,7,8. Nehmen wir Position 7:
7 div 3 = 2, d.h. Quadrat Nummer 2 (X richtung) (Zählung der Quadrate beginnt auch bei 0)
7 mod 3 = 1, d.h. Im kl. Quadrat steht die Zahl auf X-Position 1 (wieder beginnt Zählung bei null).

Y Funktioniert genauso. Im Beispiel, oberste Reihe, Y also 0:
0 div 3 = 0, d.h. Quadrat Nr. 0 (Y richtung)
0 mod 3 = 0, d.h. Steht im kl. Quadr. auf Y-Pos 0.

Die mit mod gewonnene Info ist aber unwichtig.

Somit muss jetzt ein Test das betroffene Quadrat durchlaufen:

Delphi-Quellcode:

for i = Smallsize*QuadratNummerX To Smallsize*QuadratNummerX+Smallzise
  for j = Smallsize*QuadratNummerY To Smallsize*QuadratNummerY+Smallzise
    if Grid(i,j)=digit and ((i<>X)and(j<>Y)) then
      return false,....

So könnte es in etwa anfangen

[hans ditter]

Okeeeee... werd's mal schauen, ob ich das umsetzten kann. Meld mich dann wieder.

Danke für deine Hilfe!

LG, hans ditter

[Jumpy]

Ein Gedanke, der mir dazu noch gekommen ist. Wenn man das so rekursiv ausbaut, hat man dann die Funktion nicht u.U. sehr oft aufgerufen und im Speicher? Z.B. bei einem 9er Soduko 81 mal?

Ist das nicht schlecht für die Performane? Bin ja selber noch neu beim Programmieren, kann also sein, dass ich das überschätze und sowas bei heutiger Rechenpower egal ist.

In die selbe Kerbe gehauen. Wäre es nicht besser die Zahlen nicht direkt in einem Gitter zu speichern, sondern in einem zweidimensionalen Array und dann nur zum Schluß das Gitter aus dem Array zu füllen? A) Kostet das zeichnen immer Zeit und B) ist man dann offen, wie man das Sudoku darstellt, muss ja nicht unbeding ein Gitter sein...

Letzter Vorschlag: Sollte man nicht statt von einem 4er Sudoku zu sprechen, von einem 2x2 Sudoku sprechen? Damit ist die Zahl der kleinen Quadrate in dem großen Quadrat gemeint. Dies hätte den Vorteil, das man mit der Funktion nicht nur Quadratische Sudokus bauen könnte, z.B.:
2x3 Sudoku: Ist ein 6er Sudoku, d.h. Size = 36. Hat 6 kleine Unter-Blöcke (rede nicht mehr von Quadraten), 2 solcher Blöcke nebeneinander und davon dann 3 untereinander.

Das macht die Sache viel flexibler.

[hans ditter]

Also ich denke, dass 81 Funktionsaufrufe nacheinander nicht so das Problem darstellen dürften... sollte heute schon funktionieren, zumindest wenn man mal den Preis betrachtet . . . :wink:

Ansonsten: Ja, wäre wohl besser, die Zahlen in einem Array zu speichern, aber soweit war ich einfach noch nicht. Ich wollte das Programm erstmal zum Laufen bringen und dann weitere Funktionen einbauen (z.B. Array).
Zum letzten, ja, wäre auch 'ne Möglickeit, muss aber ehrlich sagen, dass ich noch nie von einem 2 x 3 Sudoku gehört habe. Es muss ja jede Zahl in jedem Block, in jeder Reihe und in jeder Spalte einmal vorkommen. Und das geht bei einem 2x3 Sudoku imho nicht mehr.

LG, hans ditter

[hans ditter]

Also, ich hab deinen Rechenweg noch ein wenig verändert. So wie du ihn hier beschrieben hast, war der nicht ganz richtig...(warum, weiß ich auch nicht so genau, war einfach so... :stupid:)
Hier der Code:

Delphi-Quellcode:

Smallsize:=Trunc(sqrt(Size));

    X:=i div SmallSize;
    Y:=i div SmallSize;

    for j := (SmallSize * X) to (SmallSize * X) do
    begin
      for k := (SmallSize * Y) to (SmallSize * Y) do
      begin
        if (Form1.Map.Cells[j,k] = IntToStr(digit)) AND ((j<>X) AND (k<>Y)) then
        begin
          Result:=false;
          Break;
        end;
      end;
    end;

Komischerweise hängt sich das Programm beim dritten erzeugten Sudoku auf. Weiß auch nicht warum, es scheint komplett fertig generiert zu sein und plötzlich hängt das Programm... Hast du 'ne Idee?

LG, hans ditter

[Jumpy]

Ich nehme an, du hast den Testcode für das Quadrat da eingebaut, wo du auch zuvor die Zeile und Spalte getestet hast? Zeig mal das Ganze, vllt. kommt es da zu Konflikten.

Deine Schleifen können aber nicht richtig sein:
for j := (SmallSize * X) to (SmallSize * X) do

Start und Endwert sind immer gleich. Da wird ja nur einmal was gemacht, das kann auch nicht richtig sein. Ich dachte meine Schleifen wären OK gewesen, da man damit durch das entsprechende Quadrat iteriert. Schau mir das aber nachher noch mal in Ruhe an.

[Jumpy]

Fehler gefunden. Es fehlt mal wieder eine -1:

Delphi-Quellcode:

for i = Smallsize*QuadratNummerX To Smallsize*QuadratNummerX+Smallzise-1
  for j = Smallsize*QuadratNummerY To Smallsize*QuadratNummerY+Smallzise-1

So sollte es gehen,

Jumpy

[schlecki]

Zitat:

Zitat von hans ditter (Beitrag 1074750)

[...] muss aber ehrlich sagen, dass ich noch nie von einem 2 x 3 Sudoku gehört habe. Es muss ja jede Zahl in jedem Block, in jeder Reihe und in jeder Spalte einmal vorkommen. Und das geht bei einem 2x3 Sudoku imho nicht mehr.

doch, doch, das geht ;)
Sind halt leichtere Sudokus (für Anfänger). Es gibt in diesen 2x3er Sudokus nur die Zahlen von 1-6...

[Jumpy]

Hier mal als Beispiel was es so gibt.

http://www.roqa.de/html/sudoku.html

[hans ditter]

@Jumpy: 'Tschuldige, ich hatte viel zu tun die Tage. Ich häng nochmal das gesamte Projekt ran (ist nicht viel. Nur die Exe, die Projektdateien und die SudokuLogic-Unit, in der du dann auch die Überprüfun findest).

Würde mich freuen, wenn du da mal rüberschauen könntest! :)

[Jumpy]

Sieht schon ganz gut aus. Fehlerhaft ist mMn nur in der DigitIsOK der part der auf die Quadrate prüft. Hab mal Kommentare reingeschrieben, wie es mMn geändert werden müsste.

Jumpy

Delphi-Quellcode:

function DigitIsOK(i,Digit: integer):boolean;
var
  j,k: Integer;
  X,Y,SmallSize: integer;
begin
  X:=i mod Size;
  Y:=i div Size;
  Smallsize:=Trunc(sqrt(Size));
  //Hier reicht Smallsize:=sqrt(Size);
  //Da alles quadratisch ist. Wenn da irgendwas komisches rauskäme,
  //würde es eh nicht klappen, da nützt dann auch Trunc nichts.

  Result:=True;

  if not(Digit = 0) then
  begin
    for j := 0 to Size - 1 do //Reihen, Spalten
    begin
      if (Digit = StrToInt(Form1.Map.Cells[X,j])) OR
         (Digit = StrToInt(Form1.Map.Cells[j,Y])) then
        begin
          Result:=False;
          Break;
        end;
    end;
   //Der Part ist mMn OK.

    X:=i div SmallSize;
    Y:=i div SmallSize;
    for j := (SmallSize * X) to (SmallSize * X) do
   //Wenn du dir die Exe anguckst, siehst du, das die Quadrate nicht passen.
   //Das kommt daher, das die Schleife so nicht zählt, da Start und Ende gleich sind.
   //for j:= (SmallSize*X) to (SmallSize*X + SmallSize-1) //So müsste es richtig lauten
    begin
      for k := (SmallSize * Y) to (SmallSize * Y) do
      //Analog:
      //for k:= (SmallSize*Y) to (SmallSize*Y + SmallSize-1)
      begin
        if (Form1.Map.Cells[j,k] = IntToStr(digit)) AND ((j<>X) AND (k<>Y)) then
        begin
          Result:=false;
          Break;
        end;
      end;
    end;
  end
  else
    Result:=false;
end;

[hans ditter]

Super. Danke das du nochmal drüber geschaut hast.
Das mit Trunc() hab ich gemacht, weil Delphi mir sagte, dass Smallsize vom Typ Extended (oder so ähnlich) sein müsste. Deshalb Trunc(). Die Umwandlung einer Float zu einem Integer.

Das Andere probier ich nochmal aus!

LG, hans ditter

[Jumpy]

Du hast recht. Ich hab mir die Wurzelfunktion noch nie angesehen und wußte nicht, dass sie einen Float-Wert zurückliefert, wobei das ja Sinn macht, sind doch die wenigsten Zahlen Quadratzahlen.

[hans ditter]

@Jumpy: Also ich hab deinen code mal getestet. Aber es will immer noch nicht funktionieren... :cry:

Ich häng das Projekt mal dran. Hab neben dem Feld nochmal 2 Listen gepackt, die die Werte von j und k anzeigen. Utopisch hohe Werte und vor allem total durcheinander.

Vielleicht magst du nochmal drüber schauen.....??

LG, hans ditter

[Jumpy]

Wo hast du das denn hingepackt?

[hans ditter]

ups... hab ich wohl vor lauter Aufregung vergessen... :oops: passiert mir irgendwie dauernd... :shock:

[Jumpy]

Hallo Hans,

in DigitIsOK, an der Stelle, wo das testen auf die kleinen Quadrate losgeht steht diese Zuweisung:

Delphi-Quellcode:

X:=i div SmallSize;
Y:=i div SmallSize;

Diese muss lauten (Hab ich vorher übersehen, sorry.):

Delphi-Quellcode:

X:=X div SmallSize;
Y:=Y div SmallSize;

Denn weiter oben (als du die Reihen und Spalten getestet hast) wird aus i die Position des Feldes, also X und Y berechnet. Abhängig von der Position (also X und Y) wird nun ermittelt in welchem Quadrat das Feld steht. Also die X und Y Position des Quadrates. Mit der obigen Änderung müsste das klappen. Da du von i statt von X oder Y ausgegangen bist, kamen auch die komischen Werte raus.

X und Y haben also für den Reihen- und Spaltentest und den Quadrattest unterschiedliche Bedeutung. Der übersicht halber solltest du sie daher anders nennen, z.B. qX und qY oder so:

Delphi-Quellcode:

qX:=X div SmallSize;
qY:=Y div SmallSize;

Natürlich das dann auch im darauf folgenden Quelltext ändern...

Damit sollte es doch jetzt klappen,
Jumpy

[Deep-Sea]

Sry, ich habe mir jetzt nicht den ganzen Thread durchgelesen. Darum eine Frage, die sonst vlt. klar wäre: Wo genau liegt das Problem?

Ich habe vor einiger Zeit schon einmal ein Tool geschrieben, was Sudokus mit Hilfe von Kandidatenlisten löst. Auch ein komplett leeres Sudoku würde es natürlich lösen - mischt man vor jedem Feld die Kandidatenliste, kommt ein fertiges, gültiges und zufälliges Sudoku heraus. Man müsste nur noch die gewünschte Anzahl an Feldern leeren, die der "Benutzer" ausfüllen soll.
Hat das was mit dem Problem zu tun oder hab ich jetzt totalen OT geschrieben? :?

[Jumpy]

Hallo Deep-Sea,

im Prinzip will Hans glaub ich was ähnliches erreichen wie du es beschreibst. Da er aber dabei lernen will geht er Schritt für Schritt an die Sache ran, d.h. er will keine fertige Lösung (Behaupte ich jetzt mal dreist).
Ich könnte mir aber vorstellen, dass er, wenn er fertig ist, deine Variante gerne mal sehen würde, um zu sehen was man alles anders und evtl. besser machen kann. Ich für meinen Teil würd deinen Ansatz auf jeden Fall gerne sehen, da ich auch noch viel lernen will (z.B. was Kandidatenlisten sind). Kann ich das hier im Forum finden? Mach mich heut Abend mal auf die Suche.

Auch geht es zunächst nur um ein Programm zum erstellen eines Sudokus, nicht zum lösen, wobei das Programm mit einigen minimalen Änderungen Sudokus auch lösen könnte, wenn es fertig ist und man ihm die schon bekannten Startwerte mitgibt (ahh:idea: sind das die Kandidatenlisten?).

[Deep-Sea]

Ah ok.
Ich habe den Sourcecode von meinem Tool einfach mal angehängt. Es ist in D2009 geschrieben, aber ich habe glaube ich keine all zu außergewöhnlichen Dinge genutzt, so das es auch relativ problemlos mit anderen Delphi-Versionen laufen sollte.
Der Quelltext ist nicht kommentiert - falls also etwas unklar ist, fragt mich :-D
Wie gesagt, das Tool ist eig. zum lösen gedacht. Wenn ihr ein neues Sudoku erstellen wollt, müsst ihr das alte löschen und dann auf "Auflösen" klicken.

So, nun zur Theorie:
Mit Kandidatenlisten meine ich, dass ich mir zu jedem freien Feld eine Liste mache, in der die möglichen Kandidaten stehen - also die Zahlen, die nach den Regeln für dieses Feld möglich wären. Anschließend nehme ich das Feld mit der kürzesten Kandidatenliste - die im Idealfall nur einen Eintrag enthält - und schreibe den ersten Eintrag ins Feld. Und das Spiel beginnt von vorne.
Sollte ich im Verlauf der Auflösung auf ein Feld stoßen, dass frei ist, aber kein Kandidat in frage kommt, so gehe ich einen Schritt rückwärts (klassisches Backtracking).
Für das erstellen habe ich die Funktion "ShuffleCandidates" eingeführt, damit die Kandidaten zufällig ausgewählt werden und nicht der Reihe nach.

[hans ditter]

Hallo alle zusammen,

sorry, dass ich erst jetzt schreib. Die Schule frisst einen auf...:roll:
Ich hab den Quellcode nach euren Angaben verbessert. Jetzt scheint es auch zu funktionieren. Allerdings kommt zwischendurch mal ein Sudoku, wo die letzte Reihe nur mit Nullen gefüllt ist. Ich häng das Projekt nochmal ran.

Wenn ihr möchtet, könnt ihr ja gerne auch nochmal testen, ob das bei euch auch funktioniert... :wink: würde mich freuen!

LG, hans ditter

[Deep-Sea]

Was gibt es neues an der Sudoku-Front? :-D

[Jumpy]

In der letzten Version gibt es einen Logikfehler irgendwo, aber ich konnte ihn nicht finden.
Hab mal die Ideen von Hans in einer abgewandelten Version eingebaut. Kommt nicht an deine damalige Version dran, aber Hans (und mir auch) ging es glaub ich um den Lerneffekt. Meine Variante scheint zu laufen, drum häng ich sie mal hier an.

[hans ditter]

Hm, ja, scheint wirklich zu laufen. Das mit dem logischen Fehler hab ich auch schon entdeckt, aber ich weiß nicht, wo der Fehler ist... hast du ja auch nicht rausgefunden.
Ich werd mir deine Version und meine die Tage nochmal anschauen. Hoffe, ich finde den Fehler.

LG und danke für die Hilfe,

hans ditter

[Jumpy]

Manchmal hilft es scheinbar, wenn man den ganzen Kram 3 Wochen liegen läßt und dann nochmal draufguckt. Hab den Fehler mMn gefunden: 3. Zeile von unten.
Zudem hab ich mal die Bestimmung von X,Y aus der Schleife rausgenommen. Das muss ja nicht jedes mal neu berechnet werden, da es sich ja nicht ändert.

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;

      X:=i mod Size; //hierhin verschoben
      Y:=i div Size;

{.....................................................................}
  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
      begin
        Result:=True;
        Exit;
      end;
    end
    else
      ValidDecision.Delete(ValidDecision.IndexOf(dig));
  end;

  ValidDecision.Free;
  Form1.Map.Cells[0,0]:=dig;//Das ist der Fehler!!! Es muss nicht die 0/0 Zelle gestzt werden,
                            //sondern die X/Y Zelle muss auf 0 gesetzt werden:
  Form1.Map.Cells[X,Y]:='0';
  Result:=False;
end;

Das müsste es doch gewesen sein, oder?

[hans ditter]

@Jumpy
Ich glaube nicht, dass da der Fehler liegt. Ich hatte das (um ehrlich zu sein) bei mir nichtmal in der Unit drin. Weiß nicht, wo das bei dir hergekommen ist. Braucht man ja eigentlich auch nicht, oder?

Ich hab gerade überlegt, ob es möglicherweise woanders dran liegen könnte: Wenn jetzt ein Teilsudoku erstellt wird, bei dem ab einer bestimmten Stelle einfach keine Lösung mehr möglich ist, dann bricht der ja nicht ab. Vlt müsste man da was einstellen, dass wenn die Funktion false zurückliefert man die nochmal von vorne aufruft...

Ich komm auch mit dem Teil noch nicht ganz klar:

Delphi-Quellcode:

while ValidDecision.Count > 0 do
  begin
    dig:=ValidDecision[random(ValidDecision.Count)];
    if DigitIsOk(i,StrToInt(dig)) then
    begin
      Form1.Map.Cells[X,Y]:=dig;
      if SetCell(i + 1) then // müsste hier nicht noch ein else-Zweig rein?
      begin
        Result:=True;
        Exit;
      end;
    end
    else
      ValidDecision.Delete(ValidDecision.IndexOf(dig));
  end;

Bei dem Kommentar, müsste da nicht noch ein else-Zweig rein, was passiert, wenn die Funktion false zurückgibt? Denn wenn sie das tut, wird darauf imho nicht reagiert...

LG, hans ditter

[hans ditter]

HA! Ich glaub ich hab ihn gefunden, den Fehler. Wobei, war weniger ein Fehler als mehr was vergessen...

Also, die Funktion CreateNewSudoku wird ja vom HA aufgerufen und steuert dann die ganze Erzeugung etc.

Delphi-Quellcode:

procedure CreateNewSudoku(PlaygroundSize: integer);
begin
  Size:=PlaygroundSize;
  Randomize;
  PrepareMap(Size);
  if NOT(SetCell(0))
    then SetCell(0);
end;

Ich hab jetzt mal bei SetCell(0) eine if-Bedingung eingebaut. Falls das Sudoku nicht komplett erzeugt werden konnte, wird die Funktion einfach nochmal aufgerufen. Ich halte es eher für unwahrscheinlich, dass zweimal hintereinander ein Sudoku erzeugt wird, was nicht aufgeht.
Bei den Probeläufen hat es jetzt funktioniert! Ausserdem beachte noch den vorigen Post, dass hab ich drin gelassen. Glaube dass das da auch rein muss... Was sagst du?

Häng das Prog jetzt auch nicht ran, ausser du willst es nochmal testen, dann kann ich's nochmal machen...

LG; hans ditter

[Jumpy]

Hallo Hans,

du hast in sofern recht, das mein gefundener Fehler gar nicht bei dir im Programm war. Das hab ich vor 3 Wochen, als du #61 hochgeladen hast, da eingefügt, weil ich dachte, dass es den Fehler beheben würde (es muss, wenn die Fkt. false zurück gibt, auch die Zelle an der Position wieder auf 0 gesetzt werden.

Leider hab ich mich da beim Schreiben vertan und es hat nix gebracht, da ich gerade das auf null setzten da nicht gemacht habe. Mt der Korrektur oben funktioniert es dann aber, ...immer !!!

Was du gemacht hast ist schlecht. Du bekämpft nicht das Problem, sondern du "vertuschst" es. Du läßt das Programm sooft laufen, bis ein Sudoku ohne die Nullen entsteht. Das geht zwar auch, aber hat viele Nachteile:
- Längere Laufzeit (OK fällt bei 2x2 nicht auf, aber bei 4x4)
- Zudem werden auch falsche Sudokus generiert, wo zwar alle Nullen weg sind, aber trotzdem z.B. zwei 4ren in einer Reihe sind. Mach es mal oft genug, dann wirst du so eine Variante sehen.

Denk nochmal drüber nach, wie das rekursive Programm genau abläuft. Dann wird dir auch auffallen, dass du keinen Else-Zweig brauchst!!! Mach mal Gedanklich einen "Schreibtischtest" was an irgendeiener Stelle des Sudokus passiert.

[hans ditter]

Hm, tja, ich fürchte, ich muss wohl das ganze nochmal überarbeiten. Bin fast am überlegen, ob ich die Funktion zum Erstellen des Sudokus nicht einmal komplett lösche und dann neu machen, gleich vernünftig mit array etc. und mir dann vorher überlege, wie die Logik dahinter ist.

Werd's mir auf jeden Fall nochmal anschauen und: Danke für deine Hilfe!

LG; hans ditter