N-Queen

https://www.acmicpc.net/problem/9663

• 한 행에 퀸이 꼭 하나씩 있어야 함

• 퀸을 놓는 한 경우의 수를 1차원 배열로 놓아서 인덱스가 행을 뜻하고, 해당 숫자는 어느 열에 놓을 것인지가 된다.

• 다음 행의 퀸을 정할 때마다 이미 같은 열에 있는지 검토하고, 기존의 것들과 대각선 위치에 맞는지 검토하면서 맞을 때만 집어넣고 다음 행을 향해 재귀

• 모든 행이 찼다면, return

• 체스판의 대칭성을 고려해 연산횟수 줄여줌

def recu(na):
    global cnt

    if len(na) == n:
        cnt += 1
        return

    for i in range(n):
        if i not in na:
            p = True

            for j in range(len(na)):
                if abs(na[j] - i) == abs(j - len(na)):
                    p = False
                    break

            if p:
                ta = []
                for j in range(len(na)):
                    ta.append(na[j])
                ta.append(i)
                recu(ta)


import sys
sys.stdin = open('note.txt', 'r')

n = int(input())

cnt = 0

# 짝수
if not n % 2:
    for i in range(n//2):
        a = [i]
        recu(a)
    print(2*cnt)

# 홀수
else:
    for i in range(n//2):
        a = [i]
        recu(a)
    cnt *= 2

    a = [n // 2]
    recu(a)
    print(cnt)