|
Seite 1 von 1
|
[ 5 Beiträge ] |
|
Autor |
Nachricht |
chrisi1698
Registriert: 10/2007 Beiträge: 23 + 3
|
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 |
|
|
Godwin
Registriert: 11/2009 Beiträge: 26 + 2 Wohnort: wochentags Wien 17
Studium: (alt) Bachelor Technik und Naturwiss.
|
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 |
|
|
chrisi1698
Registriert: 10/2007 Beiträge: 23 + 3
|
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 |
|
|
SOADdict
Registriert: 10/2007 Beiträge: 28 + 204 Wohnort: 1040 Wien // Waldviertel
|
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... 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 |
|
|
ABotond
Registriert: 04/2010 Beiträge: 21
|
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 |
|
|
|
Seite 1 von 1
|
[ 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.
|
|