Entwickler-Ecke
Algorithmen, Optimierung und Assembler - damenproblem
tirreg - Sa 26.02.05 21:00
Titel: damenproblem
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
tirreg - 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?
tirreg - So 27.02.05 14:18
naja ich sagte ja ich hab das tutorial schon gefunden ;)
uall@ogc - 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 - 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.
Spaceguide - 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.
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=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 - 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 - Di 01.03.05 13:11
Delphi lernen lohnt sich immer ;)
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!