http://www.mathworks.com/matlabcentral/newsreader/view_thread/327950
MATLAB Central Newsreader  question about 8 queens puzzle
Feed for thread: question about 8 queens puzzle
enus
©19942014 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Sun, 31 Mar 2013 03:31:05 +0000
question about 8 queens puzzle
http://www.mathworks.com/matlabcentral/newsreader/view_thread/327950#901209
Johanes
I know how to find every time one solution but I want to find all of the 92, so I thouhgt running the function 92 times. How can I prevent same solutions return (same does not mean symatrical to previous solution)? <br>
thanks.<br>
By the was, is this the right forum for publishing this problem ?

Sun, 31 Mar 2013 05:54:10 +0000
Re: question about 8 queens puzzle
http://www.mathworks.com/matlabcentral/newsreader/view_thread/327950#901213
Roger Stafford
"Johanes " <eyenir@gmail.com> wrote in message <kj8alp$fhe$1@newscl01ah.mathworks.com>...<br>
> I know how to find every time one solution but I want to find all of the 92, so I thouhgt running the function 92 times. How can I prevent same solutions return (same does not mean symatrical to previous solution)? <br>
> thanks.<br>
> By the was, is this the right forum for publishing this problem ?<br>
       <br>
You can use recursion for this problem. Using a chessboard 8 x 8 matrix which is initially all zeros, at the first recursion level for the first queen start at the first position, and afterwards at successive positions, in the natural linear index ordering and then fill the matrix with ones at that position and all others attacked by this queen. Pass this matrix down to the next recursion level where again the second queen starts at the first unattacked position following the first queen and thereafter proceeds through successive unattacked positions. When it is placed, add ones wherever the second queen attacks and pass this matrix on to the third recursion level. This continues until either there are no available positions left or you succeed in placing the eight queen at the eight recursion depth. In this latter case you have found a solution. With this methodical approach you <br>
will find all solutions without any duplications. <br>
<br>
Note that if you wish to avoid recursive coding, you can accomplish the same thing using nested forloops eight deep.<br>
<br>
Roger Stafford

Sun, 31 Mar 2013 08:02:05 +0000
Re: question about 8 queens puzzle
http://www.mathworks.com/matlabcentral/newsreader/view_thread/327950#901215
Johanes
"Roger Stafford" wrote in message <kj8j22$75t$1@newscl01ah.mathworks.com>...<br>
> "Johanes " <eyenir@gmail.com> wrote in message <kj8alp$fhe$1@newscl01ah.mathworks.com>...<br>
> > I know how to find every time one solution but I want to find all of the 92, so I thouhgt running the function 92 times. How can I prevent same solutions return (same does not mean symatrical to previous solution)? <br>
> > thanks.<br>
> > By the was, is this the right forum for publishing this problem ?<br>
>        <br>
> You can use recursion for this problem. Using a chessboard 8 x 8 matrix which is initially all zeros, at the first recursion level for the first queen start at the first position, and afterwards at successive positions, in the natural linear index ordering and then fill the matrix with ones at that position and all others attacked by this queen. Pass this matrix down to the next recursion level where again the second queen starts at the first unattacked position following the first queen and thereafter proceeds through successive unattacked positions. When it is placed, add ones wherever the second queen attacks and pass this matrix on to the third recursion level. This continues until either there are no available positions left or you succeed in placing the eight queen at the eight recursion depth. In this latter case you have found a solution. With this methodical approach <br>
you <br>
> will find all solutions without any duplications. <br>
> <br>
> Note that if you wish to avoid recursive coding, you can accomplish the same thing using nested forloops eight deep.<br>
> <br>
> Roger Stafford<br>
<br>
Sorry for awakwardness but what do you mean by succesive positions and natural linear index ? something like this?: (Step 1)<br>
1 0 0 0 0 0 0 1<br>
1 0 0 0 0 0 1 0<br>
1 0 0 0 0 1 0 0<br>
1 0 0 0 1 0 0 0 <br>
1 0 0 1 0 0 0 0<br>
1 0 1 0 0 0 0 0<br>
1 1 0 0 0 0 0 0<br>
* 1 1 1 1 1 1 1<br>
<br>
V (step 2)<br>
1 1 0 0 0 0 1 1<br>
1 1 0 0 0 1 1 0<br>
1 1 0 0 1 1 0 0<br>
1 1 0 1 1 0 0 0<br>
1 1 1 1 0 0 0 0<br>
1 * 1 1 1 1 1 1<br>
1 1 0 0 0 0 0 0<br>
* 1 1 1 1 1 1 1<br>
<br>
etc?...<br>
Still I haven't understood how duplications are prevented?

Sun, 31 Mar 2013 16:56:06 +0000
Re: question about 8 queens puzzle
http://www.mathworks.com/matlabcentral/newsreader/view_thread/327950#901232
Roger Stafford
"Johanes " <eyenir@gmail.com> wrote in message <kj8qht$q7v$1@newscl01ah.mathworks.com>...<br>
> Sorry for awakwardness but what do you mean by succesive positions and natural linear index ? something like this?: (Step 1)<br>
> .......<br>
> Still I haven't understood how duplications are prevented?<br>
         <br>
If B is an 8 x 8 matrix of ones and zeros indicating positions on a chessboard that are either attacked or not, then by the linear index I mean the index ranging from 1 to 64 that would apply to the vector B(:). See a discussion of that ordering in the 'ind2sub' documentation.<br>
<br>
Duplications are prevented if subsequent recursions depths must retain an ascending order of linear indices. A queen can only be placed in that linear ordering after the queens that are already in place. That avoids permutations among the queens.<br>
<br>
Roger Stafford