N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
def queen(x):
global cnt
if x == n:
cnt += 1
return
for j in range(n):
if v1[j] == v2[x+j] == v3[x-j] == 0:
v1[j] = v2[x+j] =v3[x-j] = 1
queen(x+1)
v1[j] = v2[x+j] =v3[x-j] = 0
n = int(input())
cnt = 0
v1, v2, v3 = [0] * n, [0]*(2*n), [0]*(2*n)
queen(0)
print(cnt)