Sign in to follow this  
VB_master

Checker Challenge

Recommended Posts

VB_master    196
I am member of USACO and I am stuck on one of the problems there - Checker Challenge. You need to place N queens on NxN checkboard so queens do not attack each other. I am pretty confused about it, so I would like to ask you for a suggestion on solving that and some algorithm help... Thank you, VBmaster

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
This is basically done by recursion.

Place a queen in a valid position, first placement would normally be placed in a corner. Call the recursive function again and place another queen in a valid position in the next column. For instance:


Q - a queen
First queen placement
Q**
***
***

Second queen in a 3x3
Q**
***
*Q*

place 3rd queen in a valid position in the 3rd column.
Q**
***
*Q*
Oops, there is no valid position. stop the recursion and go back to the previous queen and move that queen to its next position.

Q**
***
*Q*

We exhausted the positions in that column. return to previous position.

Q**
***
***

We need to move the first queen to its next valid position.

***
Q**
***

Place a queen in column 2... oops no possibilities. return to previous queen and move it to the next location.

***
***
Q**

Place Next Queen in column 2
*Q*
***
Q**

Place Next Queen in column 3
*Q*
***
Q**

Exhausted all the valid positions in a 3x3 grid... No solution.





4x4 grid
Q***
****
****
****
place 2nd queen
Q***
****
*Q**
****
place 3rd queen
Q***
****
*Q**
****
No valid positions in column 3 for a queen... return to previous queens placement and move the queen to its next valid position
Q***
****
****
*Q**
place 3rd queen
Q***
**Q*
****
*Q**
place 4th queen... no valid placements... return to the first queen's placement since we have exhausted all the other queens positions.

Move 1st queen to its next valid position.
****
Q***
****
****
place next queen
****
Q***
****
*Q**
So far so good... place the next queen at the first valid position in the second column
**Q*
Q***
****
*Q**
place 4th queen
**Q*
Q***
***Q
*Q**

We placed 4 queens, we found a solution. If we needed to find the other solutions we would back up and move the queen to the next valid position in the 3rd column, which there is no more. so we move to the previous column and move the queen and so forth until we place another 4 queens on the board. Keep in mind that there is no solutions for a 2x2 and a 3x3 grid. I am not sure how many more have no solutions.

This is basically a Depth-First Search of a tree which the nodes do not really exist until you need them. Some pseudo code can be found here... http://www.ics.uci.edu/~eppstein/161/960215.html




Hope this helps.


Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this