SuperQueen

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