Sudoku Logik

[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