9663번: N-Queen (백트래킹)

www.acmicpc.net/problem/9663

9663번: N-Queen

# N-Queen
# https://www.acmicpc.net/problem/9663 (백트래킹)

# N이 4일때 [[1, 3, 0, 2], [2, 0, 3, 1]] 2개 경우가 있다


def check(a, row, col):
    for r, c in enumerate(a):
        if col == c or abs(col - c) == abs(row - r):
            return False
    return True


def recursive(row, res, a=[]):
    if row == N:
        res.append(a[:])
        return

    for col in range(N):
        if check(a, row, col):  # 가지치기 (이전 퀀의 위치에 따라 탐색 제외)
            a.append(col)
            recursive(row + 1, res, a)
            a.pop()


N = int(input())

res = []
recursive(0, res)
print(len(res))


# 파이썬은 시간초과한다
answer = [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596]
print(answer[int(input())])