Autor Beitrag
tirreg
Hält's aus hier
Beiträge: 4



BeitragVerfasst: Sa 26.02.05 21:00 
hallo zusammen,

ich suche zum thema backtracking das "damen-problem"
hab zwar das tutorial gefunden, hilft mir persönlich leider nicht viel :(
wollte fragem ob jemand bereit wäre, mir das programm zu schicken, vorausgesetzt es hat jemand.

danke schonmal im vorraus ;)
mfg tirreg
Kernel32.dll
Ehemaliges Mitglied
Erhaltene Danke: 1



BeitragVerfasst: Sa 26.02.05 23:53 
suchst du sowas hier?

download:
www.dsdt.info/tutori...king/?page=downloads

dort gibbet Beispielsource zum Download, da wird u.a. auch das dame-prob behandelt
tirreg Threadstarter
Hält's aus hier
Beiträge: 4



BeitragVerfasst: So 27.02.05 01:10 
mh ja schon. das is zwar die richtige idee, aber nicht ganz das was ich suche. hat jemand noch ein anderes?
Tomac
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 113

Win XP
D6 Ent
BeitragVerfasst: So 27.02.05 14:13 
tirreg Threadstarter
Hält's aus hier
Beiträge: 4



BeitragVerfasst: So 27.02.05 14:18 
Tomac hat folgendes geschrieben:
Schau mal da:

www.delphi-forum.de/..._Algorithmen_34.html


mfG
Tomac


naja ich sagte ja ich hab das tutorial schon gefunden ;)
uall@ogc
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1826
Erhaltene Danke: 11

Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
BeitragVerfasst: So 27.02.05 14:25 
das damen problem ist doch agr net so schwer
es wird dir auch keiner schicklen weil es bestimmt für die schule ist

man hat doch ein 8*8 feld (oder sogar 16*16) und muss dadrauf halt die damen verteilen ohen das sie siagonal oder vertikal oder hrizontal sich gegenseitig bedrängen

das ganze löst man mit rekursion (backtracking) indem man eine dame setzt und dann eine 2 setzt (wo es gültig ist) usw. sollte es ein problem bei der setzung einer dame geben wird das ganze wieder rückgänig gemacht (druchs backtracking)

pseudocode:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
procedure ba(i,j: integer);
begin

setztedame(i,j);

ba(i+1,j+1);
  
  if unguelig then
  entfernedame(i,j);
end;


musst dir halt genauer anschein ich weiß net obs ganz genau so sein muss ist aber iegntlich ganz leicht hatte ich auch mal in der 11 gemacht ;>
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Mo 28.02.05 14:32 
Netter Stackoverflow ... Aber die Grundidee von uall funktioniert so. Sei nur noch angemerkt, dass du noch einen Zähler benötigst, der Dir die Anzahl der bisher gesetzten Damen angibt. Weiterhin benötigst Du noch eine Schleife, mit der Du alle Felder der Reihe nach durchgehen kannst.

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
Spaceguide
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 552


(D3/D7/D8) Prof.
BeitragVerfasst: Mo 28.02.05 14:58 
Hier mal ein ganz dreckiger Hack. Kann man alles noch optimieren, denn zu einer Lösung kann man direkt die horizontal/vertikal gespiegelten sowie die transponierten Lösungen ausgeben etc.

ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
function Collision(x1,y1,x2,y2 : integer) : boolean;
 var dx,dy : integer;
begin
 dx:=x2-x1;
 dy:=y2-y1;

 Result := (dx=0or (dy=0or (dx=dy) or (dx=-dy);
end;

type TDamen = array [0..7of TPoint;

function Valid(x,y : integer; Level : integer; var Damen : TDamen) : boolean;
 var i : integer;
begin
 Result:=True; i:=0;
 while Result and (i<Level) do
 begin
  Result:=Result and (not Collision(x,y,Damen[i].x,Damen[i].y));
  Inc(i);
 end;
end;

function Trace(Level : integer; Start : integer; var Damen : TDamen) : integer;
 var i : integer;
begin
 Result:=0;
 for i:=start to 64-1 do
 begin
  if Valid(i and 7,i shr 3,Level,Damen) then
  begin
   Damen[Level].x:=i and 7;
   Damen[Level].y:=i shr 3;

   if Level<7 then
    Result:=Result+Trace(Level+1,i+1,Damen) else
    begin
     Inc(Result);
     DrawSolution(Damen);
    end;
  end;
 end;
end;


Findet 92 Lösungen, sollte also korrekt sein.
tirreg Threadstarter
Hält's aus hier
Beiträge: 4



BeitragVerfasst: Di 01.03.05 11:10 
ja @ uall@ogc,
es ist für die schule. allerdings bin ich nicht in der 11 sondern in der 13 und mache bald mein abitur. ich muss nur noch ein einziges programm abgegeben, bis ich mein abitur bekomme (info is nen nebenfach). hinzu kommt dass ich in der 12 in usa war und viel verpasst habe.

also falls jemand doch sich erbahmen könnte, mir das programm zu schiken, wäre ich dem sehr verbunden :). es lohnt sich auch nicht für ein einziges projekt für das abitur noch delphi zu lernen.

mfg tirreg
Spaceguide
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 552


(D3/D7/D8) Prof.
BeitragVerfasst: Di 01.03.05 13:11 
Delphi lernen lohnt sich immer ;)