BACKTRACKING

[SIrRonBird]

Guten Tag Leute ich habe ein Problem und zwar soll ich das Damenproblemmit BackTracking lösen und habe auch schon angefangen mit der idee immer eine dame zusetzten und die Felder di enicht mehr belegt werden können mit einem 'X' zu makieren bisher bin ich soweit:

Code: Alles auswählen

procedure TForm1.Button1Click(Sender: TObject);
var  n,i,s,z,z1,s1:integer;
begin
n:=0;
s1:=0;
z1:=0;
if StringGrid1.Cells[n,0]='' then
StringGrid1.Cells[n,0]:='D';
for s:=0 to StringGrid1.ColCount -2 do
begin
  StringGrid1.Cells[s+1,0]:='X';
end;
for z:=0 to StringGrid1.RowCount -2 do
Begin
  StringGrid1.Cells[0,z+1]:='X';
End;
for i:=0 to StringGrid1.RowCount-2 do
begin
  StringGrid1.Cells[s1+1,z1+1]:='X';
  s1:=s1+1;
  z1:=z1+1;
 
end;
end;

Nun weiß ich nicht weiter... Bitte um Hilfe...

MfG SirRonBird

[corpsman]

Google ist dein freund : http://moritz.faui2k3.org/de/backtracking

was genau versteht du denn nicht ? Versuche dein Problem bitte so zu schildern, dass wir dir auch helfen können.

[Christian]

Ich finds schön, das in offenbar immer mehr schulen Lazarus eingesetzt wird.

[SIrRonBird]

Finde ich gar nicht gut

[theo]

Finde ich gar nicht gut

Hehe, dann löse die Aufgabe halt in Java (ist aber bestimmt nicht einfacher). Wir helfen dir dann beim übersetzen nach Pascal.

[Christian]

Stimmt mit Lazarus bist du super dran
Erklär doch einfach was du genau nicht verstehst wir helfen dir gern.
Alternativ kann man natürlich im Unterricht aufpassen

[SIrRonBird]

Hallo Laute, ich weiß nicht wie ich weiter machen soll !!! Und unser Lehrer sagt einfach macht mal und erklärt nichts !!!

MfG SRB

[martin_frb]

Du solltest versuchen detailliertere fragen zu stellen. Im Moment könnte ich nicht mal sagen, ob du weist (oder nicht weist) was Backtracking ist. Oder ob du an der Implementation (Pascal source schreiben) scheiterst.

http://de.wikipedia.org/wiki/Backtracking
Allerdings brauchst du 90% von dem was dort steht nicht.

"Versuch und Irrtum". Das heißt du setzt eine Dame, nach der anderen. Solange bis ein Fehler auftritt. Ein Fehler heißt hier eine nicht erlaubte Situation, also zum Beispiel 2 Damen die sich gegenseitig bedrohen.

Wenn ein Fehler auftritt musst du was anderes Versuchen. Beim Backtracking, heißt das einen Schritt zurück. Also die zuletzt gesetzte Dame entfernen, und woanders wieder Versuchen.

Frage an dich:
Was nun wenn du z.b 5 Damen hast, und du hast nach dem obigen Prinzip die 6te Dame auf *ALLEN* noch freien Feldern versucht hast, aber auf jedem Feld eine eine unerlaubte Situation entstand. Du kannst also zu diesen 5 Damen keine 6te legale Position finden. Was dann?

---
Andere Frage: Habt ihr "Rekursion" gemacht?

Und WAS habt Ihr mit Rekursion gemacht?

[SIrRonBird]

In Rekursion haben wir Fakultät berechnet !!! Das haben wir geschafft !

jetzt habe ich einen anderen Ansatzt:

Code: Alles auswählen

 
unit Unit1;
 
{$mode objfpc}{$H+}
 
interface
 
uses
  Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, Grids,
  StdCtrls;
 
type
 
  { TForm1 }
 
  TForm1 = class(TForm)
    Button1: TButton;
    Button2: TButton;
    StringGrid1: TStringGrid;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure Damesetzten(x,y:integer);
  private
    {rocedure Damesetzten(z,s:integer; VAR l:integer) }
  public
    { public declarations }
  end;
 
var
  Form1: TForm1;
 
implementation
 
{$R *.lfm}
 
{ TForm1 }
 
procedure TForm1.Button1Click(Sender: TObject);
var  n,i,s,z,z1,s1:integer;
begin
n:=0;
s1:=0;
z1:=0;
if StringGrid1.Cells[n,0]='' then
StringGrid1.Cells[n,0]:='D';
for s:=0 to StringGrid1.ColCount -2 do
begin
  StringGrid1.Cells[s+1,0]:='X';
end;
for z:=0 to StringGrid1.RowCount -2 do
Begin
  StringGrid1.Cells[0,z+1]:='X';
End;
for i:=0 to StringGrid1.RowCount-2 do
begin
  StringGrid1.Cells[s1+1,z1+1]:='X';
  s1:=s1+1;
  z1:=z1+1;
 
end;
end;
 
procedure TForm1.Button2Click(Sender: TObject);
var x,y:integer;
begin
for y:=0 to StringGrid1.ColCount -1 do
    for x:=0 to StringGrid1.RowCount -1 do
        if StringGrid1.Cells[x,y]='' then
           begin
             StringGrid1.Cells[x,y]:='D';
             Damesetzten(x,y)
           end;
end;
 
procedure TForm1.Damesetzten(x,y:integer);
begin
for x:=0 to StringGrid1.RowCount -1 do
if StringGrid1.Cells[0,x]<>'X' then
else StringGrid1.Cells[0,x]:='D'
 
end;
end.

Allerdings Passiert dann volgendes:

Unbenannt.png (7.45 KiB) 1760 mal betrachtet

MfG SRB

[martin_frb]

Ok erst mal allgemeines bevor ich in Details gehe:

1) (Geringfügig) Lege dich auf s/z ODER x/y fest. Mal so and mal anders ist verwirrend (weil mit x/y lese ich z als 3te Dimension)

2) Du testest Zellen auf '' (leer) X oder Dame? Warum 3 Möglichkeiten?

Es scheint das "X" bedeutet: Hier darf keine Dame hin, weil dann 2 Damen sich bedrohen.
Die Idee ist zwar einleuchtend, hat aber Tücken.

Dir ist klar das Versuch und Irrtum bedeutet, das du auch wieder eine Dame entfernen musst?

D X X X
x X D X
X - X -

Wenn du eine "D" entfernst, dann musst du viel Aufwand betreiben wil das kleine "x" von beiden "D" gehalten wird.
Dazu später mehr.

3) procedure Damesetzten
hat ein leeres "then"

Diese Funktion macht bestimmt nicht was du vorhattest.

Code: Alles auswählen

 
if StringGrid1.Cells[0,x]<>'X' then
else StringGrid1.Cells[0,x]:='D'
 

ist gleich

Code: Alles auswählen

 
if StringGrid1.Cells[0,x] = 'X' then  // vegleich umgekehrt / statt <> jetzt =
 StringGrid1.Cells[0,x]:='D'
 

Ändere alle X in ein D

4) Warum 2 Button? Es könnte alles in nur einem Button laufen.

-------------

Soweit so gut.

Fuer das Problem in 2, gibt es mehrere gute Loesungen, doch dazu spaeter.

Du setzt die erste Dame, dann suchst du eine freie Möglichkeit fuer die 2te Dame, dann fuer die 3te....
Aber was wenn du keien Moeglichneit findest, weil 5 Damen bereits alle Felder mit X füllen?

Was machst du dann?

Ich wecde die Felder statt als x/y, einfach als 0 bis 63 bezeichnen (links nach rechts, dann naechste Zeile). Dann brauch mas nur eine Nummer pro Zelle, das ist einfacher.

Ueberleg mal:
- Die erste Dame kann man setzen wo man will. Es gibt immer eine Loesung.
- Die 2te Dame muss auf eines der freien Felder (frei = nicht X). Aber nicht all freien Felder gehen. Bei manchen lassen sich dann spaeter nicht alle 8 DAmen setzen.
- Die n-te Dame ... (genau wie 2te)

Also wenn du nach 4 Damen, noch 9 Felder hast, die nicht "X" sind, und du setzt die 5te Dame auf Feld 30 (das erste noch freie Feld), aber dann gibt es 0 (NULL) freie felder fuer die 6te Dame. Was dann?