Sudoku Logik

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

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... passiert mir irgendwie dauernd...

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