Sudoku Logik

[implementation]

Zitat von hans ditter:

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

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?? Ich glaub ich sitzt zu dicht vor meinem Problem... , seh praktisch den Wald vor lauter Bäumen nicht mehr.
[/edit]

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!

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!!

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

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.

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

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

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.