문제

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

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

입력

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

출력

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

풀이

import sys


def check(x):
    for y in range(x):
        if row[x] == row[y] or abs(row[x] - row[y]) == abs(x - y):
            return False

    return True


def queen(x):
    global count

    if x == N:
        count += 1
    else:
        for i in range(N):
            row[x] = i
            result = check(x)

            if result:
                queen(x + 1)

# Pypy3으로 풀어야 시간 초과 해결됨
if __name__ == '__main__':
    N = int(sys.stdin.readline())
    count = 0
    row = [0 for _ in range(N)]

    queen(0)
    print(count)