PROBLEM STATEMENT
Now you are going to solve a special variant of the famous N-queen problem.
Ordinary queens can threaten other pieces vertically and horizontally (like
rooks) and diagonally (like bishops). Our super-queens can also threaten like
knights. As illustrated below, a knight moves two cells in one direction and
then one cell in an orthogonal (perpendicular) direction.
Here are four diagrams that show the set of cells on a chess board threatened
by Rooks, Bishops, Knights, and Super-Queens, respectively. R represents a
rook, B represents a bishop, K represents a Knight, S represents a super-queen,
X represents a cell on the chess board that is threatened, - represents a cell
that is unoccupied.
Rook Bishop Knight Super-Queen
- - - X - - - X - - - - - X - - - - - - - X - - X - - X
- - - X - - - - X - - - X - - - X - X - - - X X X X X -
- - - X - - - - - X - X - - - X - - - X - - X X X X X -
X X X R X X X + - - - B - - - + - - - K - - - = X X X S X X X
- - - X - - - - - X - X - - - X - - - X - - X X X X X -
- - - X - - - - X - - - X - - - X - X - - - X X X X X -
- - - X - - - X - - - - - X - - - - - - - X - - X - - X
Two super-queens threaten each other if:
They are on the same row OR
They are on the same column OR
They are on the same diagonal OR
They are a knight's move away from each other
Our game takes place on a chess board with dimensions NxN (boards above are
7x7). As one can imagine, chess boards are square boards divided in a grid of
cells of equal size, N in each direction. This effectively produces NxN cells.
You have an NxN chess board (as defined above) and your task is to calculate
the number of possible configurations of putting N super-queens on the board,
so as no two of them are threatening each other. Return the calculated number.
DEFINITION
Class name: SuperQueen
Method name: getCount
Parameters: int
Returns: int
Method signature (make sure your method is public):
int getCount (int N);
NOTES
Keep in mind that your solution must run in under 6 seconds on the TopCoder
testing machine.
TopCoder will ensure that:
* 0 < N < 16
EXAMPLES
N = 5 Result = 0
N = 10 Result = 4
N = 12 Result = 156