Sudoku Array of Array vergleichen

[Marcel2906]

irgendwie hab ich ne Blockade
habs jetzt so versucht:

Delphi-Quellcode:

Procedure TForm2.BtPruefenClick(Sender: TObject);
Type
   THilfsArray = Array[1..9] Of Integer;
Var
   x, y, xx, yy: Integer;
   HilfsArray: THilfsArray;

//...

   //Wenn eine Zahl doppelt, Fehlermeldung
   Function ZahlDoppelt: boolean;
   Var
      i: Integer;
      doppelt: boolean;
   Begin
      For I := 1 To 9 Do
         If HilfsArray[i] > 1 Then
            Result := true;
   End;

//...


Begin
   //Zeile prüfen
   For y := 0 To 8 Do Begin
      HilfsArrayLeeren;
      For x := 0 To 8 Do
         AddHilfsArray(aSudoku[y, x]);
      If ZahlDoppelt = true Then
         ShowMessage(' einer Zeile');
   End;
   //Spalte prüfen
   For x := 0 To 8 Do Begin
      HilfsArrayLeeren;
      For y := 0 To 8 Do
         AddHilfsArray(aSudoku[y, x]);
      If ZahlDoppelt = true Then
         ShowMessage(' einer Spalte');
   End;
   //Feld prüfen
   For xx := 0 To 2 Do
      For yy := 0 To 2 Do Begin
         HilfsArrayLeeren;
         For y := yy * 3 To yy * 3 + 2 Do Begin
            For x := xx * 3 To xx * 3 + 2 Do
               AddHilfsArray(aSudoku[y, x]);
         End;
         If ZahlDoppelt = true Then
            ShowMessage(' einem Feld');
      End;
End;

[Blup]

Delphi-Quellcode:

   Function ZahlDoppelt: boolean;
   Var
      i: Integer;
   Begin
      For i := 1 To 9 Do
      Begin
         If HilfsArray[i] > 1 Then
         Begin
            Result := True;
            Exit; // Ergebnis steht fest
         End;
      End;
      Result := False;
   End;

//... niemals einen Boolean-Wert mit True vergleichen
      If ZahlDoppelt Then
         ShowMessage(' einer Zeile');

[Sir Rufo]

Also ich würde das gesamte Konzept anders angehen

SuDoKu (3x3) besteht ja aus 81 Feldern, welche in (3x9) 27 Blöcken organisiert sind.
Jedes Feld ist dabei immer in 3 Blöcken enthalten ( Reihe, Spalte, Quadrant )

Wenn du beim Aufbau des Spielfeldes diese Strukturen erzeugst, dann wird die Abfrage zum Kinderspiel:

Delphi-Quellcode:

TSuDoKuBlock = class;

TSuDoKuField = class
private
  // Liste der Blöcke, zu dem dieses Feld gehört
  _Items : array[0..2] of TSuDoKuBlock;
  _Value : Integer;
  procedure SetValue( aValue : Integer );
public
  function CanSetValue( aValue : Integer ) : Boolean; override;
  property Value : Integer read _Value write _Value;  
end;

TSuDoKuBlock = class( TSuDoKuBase )
private
  // Liste der Felder, die in diesen Block gehören
  _Items : array[0..8] of TSuDoKuField;
public
  function CanSetValue( aValue : Integer ) : Boolean; override;
end;

...

function TSuDoKuBlock.CanSetValue( aValue : Integer ) : Boolean;
var
  idx : integer;
begin
  Result := True;
  if ( Value > 0 ) then
    for idx := 0 to 8 do
    begin
      Result := Result and ( _Items[ idx ].Value <> aValue );
      // Wir können aufhören, wenn wir eine Abbruchbedingung gefunden haben
      if not Result then
        Break;
    end;
end;

function TSuDoKuField.CanSetValue( aValue : Integer ) : Boolean;
var
  idx : integer;
begin
  Result := True;
  if ( Value > 0 ) then
    for idx := 0 to 2 do
    begin
      Result := Result and _Items[ idx ].CanSetValue( aValue );
      // Wir können aufhören, wenn wir eine Abbruchbedingung gefunden haben
      if not Result then
        Break;
    end;
end;

Jetzt braucht man nur noch das Feld selber fragen und bekommt die passende Antwort:

Delphi-Quellcode:

if SuDoKuGame.Field[ 3, 7 ].CanSetValue( 6 ) then
  SuDoKuGame.Field[ 3, 7 ].Value := 6;

[Bjoerk]

Sir Rufo,

was meinst du mit 27 Blöcken, sind es nicht immer 9?

[Sir Rufo]

Zitat von Bjoerk:

Sir Rufo,

was meinst du mit 27 Blöcken, sind es nicht immer 9?

Ja, 9 Reihen, 9 Spalten, 9 Quadranten ergibt 27 Blöcke

[Bjoerk]

Achso, ich hatte diese Blöcke als Quadranten verstanden.

[Bjoerk]

Hab’s mal ausprobiert, allerdings etwas anders. Die Quadranten nenne ich hier Blöcke. Als Grundlage der Suche benutze ich eine Pemutliste. Geht recht flott so, < 2 sec..

Delphi-Quellcode:

function BlockToRowCol(Block, Index: integer): TPoint;
var
  VX, VY: integer;
begin
  // Block 0..8, Index 0..8
  // Result.X = Row 0..8, Result.Y = Col 0..8
  VX:= 0;
  VY:= 0;
  case Block of
    0: begin VX:= 0; VY:= 0; end;
    1: begin VX:= 3; VY:= 0; end;
    2: begin VX:= 6; VY:= 0; end;
    3: begin VX:= 0; VY:= 3; end;
    4: begin VX:= 3; VY:= 3; end;
    5: begin VX:= 6; VY:= 3; end;
    6: begin VX:= 0; VY:= 6; end;
    7: begin VX:= 3; VY:= 6; end;
    8: begin VX:= 6; VY:= 6; end;
  end;
  with Result do
  begin
    X:= 0;
    Y:= 0;
    case Index of
      0: begin X:= VY;   Y:= VX;   end;
      1: begin X:= VY;   Y:= VX+1; end;
      2: begin X:= VY;   Y:= VX+2; end;
      3: begin X:= VY+1; Y:= VX;   end;
      4: begin X:= VY+1; Y:= VX+1; end;
      5: begin X:= VY+1; Y:= VX+2; end;
      6: begin X:= VY+2; Y:= VX;   end;
      7: begin X:= VY+2; Y:= VX+1; end;
      8: begin X:= VY+2; Y:= VX+2; end;
    end;
  end;
end;

procedure TForm1.SetSudokuBlock(I: integer; Numbers: TIntegerList);
var
  Result: TIntegerList;
  J, N, Index: integer;
  T: TPoint;
  A, B, C: boolean;
begin
  Result:= TIntegerList.Create;
  try
    Result.FillUp(9);
    N:= 0;
    repeat
      A:= true;
      B:= true;
      C:= true;
      for J:= 0 to 8 do
      begin
        Index:= FPermutList.Item[N*9+J];
        Result.Item[J]:= Numbers.Item[Index];
        T:= BlockToRowCol(I, J);
        A:= A and FRow[T.X].CanHaveValue(Result.Item[J]);
        B:= B and FCol[T.Y].CanHaveValue(Result.Item[J]);
        C:= C and FBlock[I].CanHaveValue(Result.Item[J]);
      end;
      Inc(N);
    until (A and B and C);
    for J:= 0 to 8 do
    begin
      T:= BlockToRowCol(I, J);
      FRow[T.X].Item[T.Y]:= Result.Item[J];
      FCol[T.Y].Item[T.X]:= Result.Item[J];
      FBlock[I].Item[J]:= Result.Item[J];
    end;
  finally
    Result.Free;
  end;
end;

procedure TForm1.BuildSudoku;
var
  Numbers: TIntegerList;
  I, J: integer;
begin
  Numbers:= TIntegerList.Create;
  try
    Numbers.FillUp(9, 1, 1);
    Numbers.Mix;
    SudokuNull;
    for I:= 0 to 8 do // Blöcke
      SetSudokuBlock(I, Numbers);
  finally
    Numbers.Free;
  end;
end;