8-Dame wiedermal

[Jarmen_Kell]

Ja hallo zusammen.

Für alle, die es nicht kennen:
Ziel ist es, 8 Damen auf ein 8x8-Schachbrett zu platzieren, ohne, dass diese sich gegenseitig bedrohen.


Ich hatte mir dazu einiges überlegt und dann folgenden Code getippselt:

Delphi-Quellcode:

unit main;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, ExtCtrls, Buttons, Grids;

const Damen=7; // +1!

type
  Tmainform = class(TForm)
    Grid: TDrawGrid;
    btnlos: TBitBtn;
    procedure btnlosClick(Sender: TObject);
    procedure GridDrawCell(Sender: TObject; ACol, ARow: Integer;
      Rect: TRect; State: TGridDrawState);
  private
    { Private declarations }
  public
    Feld: Array[0..Damen,0..Damen] of Boolean;
    ZeileBelegt: Array[0..Damen] of Boolean;
    Diag1Belegt: Array[0..Damen*2] of Boolean;  { /  x+y }
    Diag2Belegt: Array[-1*Damen..Damen] of Boolean;  { \ x-y }
    function IstFrei(x,y:Integer):Boolean;
    procedure Klir; // Clear
    procedure SetzeDame(x,y:Integer);
    procedure EntferneDame(x,y:Integer);

    { Public declarations }
  end;

var
  mainform: Tmainform;


implementation

{$R *.dfm}

function TMainform.IstFrei(x,y:Integer):Boolean;
begin
  Result:=true;
  if ZeileBelegt[y] then Result:=false;
  if Diag1Belegt[x+y] then Result:=false;
  if Diag2Belegt[x-y] then Result:=false;
end;

procedure Tmainform.EntferneDame(x,y:Integer);
begin
  ZeileBelegt[y]:=false;
  Diag1Belegt[x+y]:=false;
  Diag2Belegt[x-y]:=false;
end;

procedure TMainform.Klir;
var
  I,I2:Integer;
begin
  for I:=0 to Damen do
    for I2:=0 to Damen do
      Feld[I,I2]:=false;
  for I:=0 to Damen do ZeileBelegt[I]:=false;
  for I:=Low(Diag1Belegt) to High(Diag1Belegt) do Diag1Belegt[I]:=false;
  for I:=Low(Diag2Belegt) to High(Diag2Belegt) do Diag2Belegt[I]:=false;
end;

procedure Tmainform.btnlosClick(Sender: TObject);
var
  I:Integer;
begin
  for I:=0 to Damen do SetzeDame(0,I);
  Grid.Repaint;
end;

procedure TMainform.SetzeDame(x,y:Integer);
var
  I:Integer;
begin
  If IstFrei(x,y)
    then
      begin
        //for I:=0 to Damen do Feld[x,I]:=false;
        Feld[x,y]:=true;
        ZeileBelegt[y]:=true;
        Diag1Belegt[x+y]:=true;
        Diag2Belegt[x-y]:=true;
        if x<Damen
          then
            for I:=0 to Damen do SetzeDame(x+1,I);
      end;

end;

procedure Tmainform.GridDrawCell(Sender: TObject; ACol, ARow: Integer;
  Rect: TRect; State: TGridDrawState);
begin
  Grid.Canvas.Brush.Color:=clblack;
  Grid.Canvas.Brush.Style:=bssolid;
  Grid.Canvas.Pen.Color:=clblack;
  if Feld[ACol,ARow] then Grid.Canvas.FillRect(Rect);
end;

end.

Das Problem an der Sache ist nun, dass nur die Damen bis zur 5. Spalte gesetzt werden. Dann scheint es nicht mehr weiter zu funktionieren und das Backtracking will nicht so recht einsetzen.

Die Forensuche brachte mir einen Verweis auf folgendes:
http://www.dsdt.info/tutorials/backtracking/?page=11

Der Grundlösungsweg ist also der selbe (bloß, dass dort Zeilen und nicht Spalten durchgegangen werden)
Doch brachte mich das ganze nicht wirklich weiter.


Irgendwo muss ich also noch die EntferneDame-Prozedur einfügen...
Ist die Prozedur soweit korrekt und vor allem: Wo ist sie aufzurufen?

Für Ideen wäre ich sehr dankbar.


Edit: Hatte Mist geschrieben, stimmt jetzt hoffentlich soweit (bis auf den genannten Fehler)

[malo]

Klir könnte für eine eingedeutschte Version von "Clear" stehen :mrgreen:
Demnach würde ich das an den Anfang setzen. Denn es setzt ja nur alle Einträge der Boolean-Arrays auf false ;)

[Jarmen_Kell]

Hatte etwas Unsinn geschrieben, Tschuldigung.

"Klir" ist in der Tat meine Version von "Clear". Ich wollte das "damals" nicht so nennen.
Die räumt nur das Feld auf und ist eigentlich irrelevant.
Die eigentliche Prozedur ist "EntferneDame"