Sudoku Array of Array vergleichen

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

[Sir Rufo]

Ein Busserl umständlich mit den case-Anweisungen, geht sowas doch auch schön mit div und mod

[Bjoerk]

Ist mir nix Gescheites eingefallen, laß mal rüberwachen..

[Bummi]

statt

Delphi-Quellcode:

  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;

beispielsweise

Delphi-Quellcode:

VX := (Block MOD 3) * 3;
VY := Block div 3 * 3;

[/delphi]

[Bjoerk]

Das sieht schon sehr viel besser aus. Danke Thomas.