알고리즘 도전기 - 47

9663 N-Queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력

8

예제 출력

92

코드

import sys

N = int(sys.stdin.readline().rstrip())
result = 0


def is_available(col_row, arr):
    global N
    for i in range(len(arr)):
        if col_row - N * (len(arr) - i) - (len(arr) - i) == arr[i] or \
                col_row % N == arr[i] % N or \
                col_row - N*(len(arr) - i) + (len(arr) - i) == arr[i]:
            return False
    return True


def move_queen(arr):
    global result
    if len(arr) == N:
        result += 1
        return
    else:
        for i in range(N):
            if is_available(len(arr) * N + i, arr):
                arr.append(len(arr) * N + i)
                move_queen(arr)
                arr.pop()


move_queen([])
print(result)