-
Currently Reading
Triangular N-Queens Challenge!
Posted on March 8, 2008
Filed Under Computer Science |
Note: I am competing in the CS Games in Canada, and will not be able to approve comments for the time being.
The Challenge
Triangular N-Queens
This is a problem that I faced in the 2006 ACM Greater New York Programming competition. I failed to solve it at the competition, but I was determined to do it at some point. When I was training for the 2007 competition the following year, I took a look at it again, and finally got it.
I particularly liked this problem because it has an easy obvious solution that runs too slow. It has another solution that seems like it works, but falls apart around a board size of 500. There is a third solution that is fast enough. And there may be more that I didn’t find.
The Basics of the Problem:
- You’re given how big the board is per side (1 <= n <= 1000)
- You know you can place floor[(2n+1)/3] queens on the triangular board
- You’re given how they attack
- You need to return a placement of all of the queens on the board
- You need to run this input file in under 2 minutes. This means that you need to be able to place the queens in less than 2 seconds on the board of size 1000
There are answers online. Don’t use them. Honor system!
Popularity: 16% [?]
Comments
One Response to “Triangular N-Queens Challenge!”
Leave a Reply
“It has another solution that seems like it works, but falls apart around a board size of 500″
I have an idea, but I’m afraid that it falls into that category. I’ll actually write the code and let you know.