Hello CF.
Can somebody help me with this problem?
# | User | Rating |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 161 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 152 |
8 | pajenegod | 146 |
9 | BledDest | 144 |
10 | Um_nik | 143 |
Name |
---|
It can be done by simple recursion with cutoffs.
Let use recursive function
int rec(int col)
. Herecol
means that we have already placed one Queen in every column beforecol
(and store positions somewhere in memory) and now we are iterating rows where we can place Queen in columncol
. It's very important not to place a Queen at position it will be attacked by other Queens to the left. Also we have to ignore reserved positions.If recursion reach 9-th column, it mean that we have found new Queen placement and we have to increase some answer counter.
How many recursion iterations will be done?
There is a simpler problem about Rook placement where all squares are free. We can use same method to solve this problem.
It can be noticed that recursion will never visit combinations that lead to some conflicts (when two Rooks thread each other), so number of recursion iterations will be equal to number of combinations of Rook placement (there are
8! ~ 4*10^4
combinations of Rook placement).It is clear that set of all Queen placements is a subset of Rook placement, so solving your problem will not require more iterations.
Thank you. I understood. For some reason I thought that it would be a long time.
Sorry that I'm writing so late. I found bug on your solution. You said that on one column we can put only one queen. But we can put many queens if between them have restriction. Or am I wrong?
And now how I can solve this problem?
Nope, you are wrong. It was mentioned (in problem statement): "However, the reserved squares do not prevent queens from attacking each other."
Oh, so this problem so easy! Sorry for my dumb approval! next time I will read statement carefully!