# Checker Challenge

This topic is 4627 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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 on other sites
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 queenFirst queen placementQ********Second queen in a 3x3Q******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 gridQ***************place 2nd queenQ********Q******place 3rd queenQ********Q******No valid positions in column 3 for a queen... return to previous queens placement and move the queen to its next valid positionQ************Q**place 3rd queenQ*****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.

1. 1
2. 2
Rutin
20
3. 3
khawk
17
4. 4
A4L
14
5. 5

• 12
• 16
• 26
• 10
• 44
• ### Forum Statistics

• Total Topics
633759
• Total Posts
3013715
×

## Important Information

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!