N-Queen

면접 대비

시간 제한10초메모리 제한128 MB

요약

15보다 작은 N을 입력받아 N행 N열 보드에 서로 공격하지 않는 퀸 N개를 두는 경우의 수를 셉니다.

문제

N-Queen 문제는 $N \times N$ 크기의 체스판에 퀸 $N$ 개를 서로 공격하지 못하게 놓는 문제이다. 퀸은 자신과 같은 행, 같은 열, 같은 대각선에 놓인 다른 퀸을 공격한다.

$N$ 이 주어졌을 때, 퀸 $N$ 개를 놓는 방법의 수를 구하는 프로그램을 작성하시오. 회전하거나 뒤집어서 서로 같아지는 배치도 각각 다른 방법으로 센다.

첫째 줄에 $N$ 이 주어진다. ( $1 \le N < 15$ )

첫째 줄에 퀸 $N$ 개를 서로 공격하지 못하게 놓는 방법의 수를 출력한다.