Autor |
Beitrag |
tirreg
Hält's aus hier
Beiträge: 4
|
Verfasst: 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
|
Verfasst: 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
Hält's aus hier
Beiträge: 4
|
Verfasst: 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
Beiträge: 113
Win XP
D6 Ent
|
Verfasst: So 27.02.05 14:13
|
|
tirreg
Hält's aus hier
Beiträge: 4
|
Verfasst: So 27.02.05 14:18
naja ich sagte ja ich hab das tutorial schon gefunden
|
|
uall@ogc
Beiträge: 1826
Erhaltene Danke: 11
Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
|
Verfasst: 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:
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
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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
Beiträge: 552
(D3/D7/D8) Prof.
|
Verfasst: 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.
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=0) or (dy=0) or (dx=dy) or (dx=-dy); end;
type TDamen = array [0..7] of 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
Hält's aus hier
Beiträge: 4
|
Verfasst: 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
Beiträge: 552
(D3/D7/D8) Prof.
|
Verfasst: Di 01.03.05 13:11
Delphi lernen lohnt sich immer
|
|