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)