Backdrop

백준 온라인 저지 ▸ 9663

N-Queen
IV

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1

8

예제 출력 1

92

풀이

python

코드

def f(n, array=[]):
    if n == len(array):
        return 1
 
    a = len(array)
    count = 0
    for b in range(n):
        for x, y in enumerate(array):
            if b == y or a - x == abs(b - y):
                break
        else:
            array.append(b)
            count += f(n, array)
            array.pop()
 
    return count
 
 
n = int(input())
 
print(f(n))