백준 9663번 풀이 python

 

문제

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

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

입력

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

출력

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

 

//예제 입력 1
8
//예제 출력 1
92

 

import sys

input = sys.stdin.readline()
n = int(input)
colArr = [0] * n
result = 0

def promising(x):
    flag = True
    for i in range(x):
        # 같은 열에 있거나 대각선 라인에 있는지 판별
        if(colArr[x] == colArr[i] or abs(colArr[x]-colArr[i]) == abs((x-i))):
            flag=False
    return flag

def n_queens(x):
    if( x == n ): # 마지막 depth까지 왔다
        global result
        result += 1
    else:
        for j in range(n):
            colArr[x] = j
            if(promising(x)):
                n_queens(x+1)

n_queens(0)
print(result)