Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
question about 8 queens puzzle

Subject: question about 8 queens puzzle

From: Johanes

Date: 31 Mar, 2013 03:31:05

Message: 1 of 4

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)?
thanks.
By the was, is this the right forum for publishing this problem ?

Subject: question about 8 queens puzzle

From: Roger Stafford

Date: 31 Mar, 2013 05:54:10

Message: 2 of 4

"Johanes " <eyenir@gmail.com> wrote in message <kj8alp$fhe$1@newscl01ah.mathworks.com>...
> 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)?
> thanks.
> By the was, is this the right forum for publishing this problem ?
- - - - - - - -
  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
will find all solutions without any duplications.

  Note that if you wish to avoid recursive coding, you can accomplish the same thing using nested for-loops eight deep.

Roger Stafford

Subject: question about 8 queens puzzle

From: Johanes

Date: 31 Mar, 2013 08:02:05

Message: 3 of 4

"Roger Stafford" wrote in message <kj8j22$75t$1@newscl01ah.mathworks.com>...
> "Johanes " <eyenir@gmail.com> wrote in message <kj8alp$fhe$1@newscl01ah.mathworks.com>...
> > 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)?
> > thanks.
> > By the was, is this the right forum for publishing this problem ?
> - - - - - - - -
> 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
> will find all solutions without any duplications.
>
> Note that if you wish to avoid recursive coding, you can accomplish the same thing using nested for-loops eight deep.
>
> Roger Stafford

Sorry for awakwardness but what do you mean by succesive positions and natural linear index ? something like this?: (Step 1)
1 0 0 0 0 0 0 1
1 0 0 0 0 0 1 0
1 0 0 0 0 1 0 0
1 0 0 0 1 0 0 0
1 0 0 1 0 0 0 0
1 0 1 0 0 0 0 0
1 1 0 0 0 0 0 0
* 1 1 1 1 1 1 1
||
V (step 2)
1 1 0 0 0 0 1 1
1 1 0 0 0 1 1 0
1 1 0 0 1 1 0 0
1 1 0 1 1 0 0 0
1 1 1 1 0 0 0 0
1 * 1 1 1 1 1 1
1 1 0 0 0 0 0 0
* 1 1 1 1 1 1 1

etc?...
Still I haven't understood how duplications are prevented?

Subject: question about 8 queens puzzle

From: Roger Stafford

Date: 31 Mar, 2013 16:56:06

Message: 4 of 4

"Johanes " <eyenir@gmail.com> wrote in message <kj8qht$q7v$1@newscl01ah.mathworks.com>...
> Sorry for awakwardness but what do you mean by succesive positions and natural linear index ? something like this?: (Step 1)
> .......
> Still I haven't understood how duplications are prevented?
- - - - - - - - - -
  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.

  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.

Roger Stafford

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us