heute ist der Geburtstag von
Pierre-Simon Laplace (28.03.1749 - 05.03.1827)


Auf das Thema antworten  [ 5 Beiträge ] 
36 n Queens Problem 
Autor Nachricht

Registriert: 10/2007
Beiträge: 23 + 3
Mit Zitat antworten
Beitrag 36 n Queens Problem
hat sich schon wer druebergetraut?
ich haett zwar ein paar dinge, unter anderem das hier: http://www.maplesoft.com/support/help/M ... k/Continue gefunden, aber ich bezweifel, dass sie einem das gelten lassen, weils nicht nach dem in der angabe beschriebenen alg. geht... allerdings versteh ich die angabe einfach nicht, was ist mit "alle soehne" gemeint bei "Fuer das Element s[1] werden nun alle Soehne erzeugt und diese hinten in die Sequenz eingereiht,.."
lg :)


Mi 08-12-2010 22:33:12
Diesen Beitrag melden
Profil

Registriert: 11/2009
Beiträge: 26 + 2
Wohnort: wochentags Wien 17
Studium: (alt) Bachelor Technik und Naturwiss.
Mit Zitat antworten
Beitrag Re: 36 n Queens Problem
Die Söhne eines nxn Spielfeldes mit k aufgestellten Damen sind alle gültigen Spielfelder mit einer aufgestellten Dame mehr, und zwar in der k+1. Zeile. (Da du die Damen ja zeilenweise von oben nach unten aufstellst.)

d.h. angenommen du hast zB auf einem 8x8 Feld 3 Damen aufgestellt, dann stehen diese aufgrund der Funktionsweise des Algorithmus in den ersten 3 Zeilen. Die Söhne dieser konkreten Aufstellung sind dann alle Möglichkeiten, eine vierte Dame in die vierte Zeile zu stellen.

lg

_________________
Wissen ist Macht. Ich weiß nichts. Macht nichts.
------
Man kann niemanden überholen, indem man in dessen Fußstapfen tritt.


Do 09-12-2010 00:53:00
Diesen Beitrag melden
Profil

Registriert: 10/2007
Beiträge: 23 + 3
Mit Zitat antworten
Beitrag Re: 36 n Queens Problem
dh s[1] = nullmatrix 8 x 8
s[1] = [ [Q 0 0 0 0 0 0 0] [ 0 000...],[,,,]]
s[2] = [ [0 Q 0 0 0 0 0 0] [ 0 000...],[,,,]]
s[3] = [ [0 0 Q 0 0 0 0 0 0] [ 0 000...],[,,,]]
s[9] = [ [0 0 0 0 0 0 0 0 Q] [ 0 000...],[,,,]]
s[10] = [[erste zeile von s2],[Q 0 0 0 0 0 0 0],[000...],[...]...] nicht konfliktfrei, also doch nicht
s[10] = [[erste zeile von s2],[0 Q 0 0 0 0 0 0],[000...],[...]...] nicht konfliktfrei, also doch nicht
s[10] = [[erste zeile von s2],[0 0 Q 0 0 0 0 0],[000...],[...]...] geht, also okay
s[11] = [[erste zeile von s3],[Q 0 0 0 0 0 0 0],[000...],[...]...] nicht konfliktfrei, also doch nicht
s[11] = [[erste zeile von s3],[0 Q 0 0 0 0 0 0],[000...],[...]...] nicht konfliktfrei, also doch nicht
s[11] = [[erste zeile von s3],[0 0 Q 0 0 0 0 0],[000...],[...]...] nicht konfliktfrei, also doch nicht
s[11] = [[erste zeile von s3],[0 0 0 Q 0 0 0 0],[000...],[...]...] geht, also okay
usw usf
...?
kanns das sein...? hab ich den alg. richtig verstanden wie die ihn da in der angabe wollen?


Do 09-12-2010 01:19:00
Diesen Beitrag melden
Profil
Benutzeravatar

Registriert: 10/2007
Beiträge: 28 + 204
Wohnort: 1040 Wien // Waldviertel
Mit Zitat antworten
Beitrag Re: 36 n Queens Problem
Ich denke du hast es verstanden:
nur dass die erste königin auf A[1,1] sitzt ist natürlich auch nicht für alle zeiten festgeschrieben...

Zitat:
s[11] = [[erste zeile von s3],[0 0 0 Q 0 0 0 0],[000...],[...]...] geht, also okay
stimmt so nicht, die königin von der ersten zeile von s3 bedroht diese königin. [SIEHE 3)]

Baut man den Algorithmus der Angabe entsprechend auf, so muss man nur noch beachten, dass man die folgenden Bedrohungen beachtet:
1) horizontal nach rechts
2) vertikal nach unten
3) bis zum rand schräg nach rechts
4) bis zum rand schräg nach links

_________________
Why do Computer Scientists get Halloween and Christmas mixed up?
Because: oct 31 = dec 25


I wish to complain about this parrot that I purchased not half an hour ago from Fachschaft TM.


Do 09-12-2010 02:18:49
Diesen Beitrag melden
Profil

Registriert: 04/2010
Beiträge: 21
Mit Zitat antworten
Beitrag Re: 36 n Queens Problem
Vielleicht hilft es jemanden:

Code:
nDame:=proc(n::posint)
local Q,ZeilenSumme,FuegeDama,GenerateSohne,ErsteNichtUnendlich,nn,s;

ZeilenSumme:=proc(z::posint,M::Matrix)
  local i,zsum;
  zsum:=0;
  for i from 1 to n do
   zsum:=zsum+M(z,i);
  od;
  RETURN(zsum);
end;

FuegeDama:=proc(x,y::posint,MM::Matrix)
local i,M;
M:=copy(MM);
for i from 1 to n do
  if (M(x,i)<>infinity) then M(x,i):=1; fi;
  if (M(i,y)<>infinity) then M(i,y):=1; fi;
  if (y-x+i)>0 and (y-x+i)<=n then
    if (M(i,y-x+i)<>infinity) then  M(i,y-x+i):=1; fi;
  fi;
  if (-i+y+x)>0 and (-i+y+x)<n then
   if (M(i,-i+y+x)<>infinity) then M(i,-i+y+x):=1; fi;
  fi;
od;
M(x,y):=infinity;
RETURN(M);
end;

GenerateSohne:=proc(MM::Matrix,z::posint,Q::queue)
local FF,i;
for i from 1 to n do
FF:=copy(MM);
if (FF(z,i)=0) then FF:=FuegeDama(z,i,FF); enqueue(Q,FF); fi;
od;
end;

ErsteNichtUnendlich:=proc(MM::Matrix)
local i;
i:=1;
while ((i<=n) and ZeilenSumme(i,MM)=infinity) do i:=i+1; od;
  RETURN(i);
end;
Q:=new(Matrix(n,n));

nn:=ErsteNichtUnendlich(front(Q));
while (nn<>n+1) do
  GenerateSohne(dequeue(Q),nn,Q);
  nn:=ErsteNichtUnendlich(front(Q));
od;
s:=[];
while not empty(Q) do s:=[op(s),dequeue(Q)]; od;
RETURN(s);
end;


Do 09-12-2010 22:52:46
Diesen Beitrag melden
Profil
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Auf das Thema antworten   [ 5 Beiträge ] 


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast


Du darfst neue Themen in diesem Forum erstellen.
Du darfst Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
Powered by phpBB © phpBB Group.  |  Designed by STSoftware for PTF  |  © Czechnology 2007 - 2024  |  Deutsche Übersetzung durch phpBB.de