N Queen timer 1초 memory 64MB

체스에서 queen은 가로, 세로, 대각선 방향으로 어느 곳이나 한 번에 움직일 수 있다.

즉 다음과 같은 체스판에서 queen이 X라고 표시된 위치에 있을 때, 

그 다음 queen이 움직여 갈수 있는 부분은 어둡게 칠해진 부분 중의 하나이다.

N \times N 크기의 정방형 체스판이 주어졌다. 

우리는 거기에 N개의 queen을 배치하려고 하는데, 모든 queen들은 서로 잡아먹을 수 없어야 한다. 

그렇다면 queen들을 어떻게 배치해야만 할까? 

가능한 모든 경우의 개수를 출력한다.