N-Queen

문제

문제

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

입력

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

출력

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

solution

import sys

def check(n):
    for i in range(n):
        if queen[i] == queen[n] or abs(queen[i] - queen[n]) == n - i:
            return False
    return True

def Nqeens(n):
    global count
    if n == N:
        count = count + 1
    else:
        for i in range(N):
            queen[n] = i
            if check(n):
                Nqeens(n+1)
            
N = int(sys.stdin.readline())
count = 0
queen = [0] * N
Nqeens(0)
print(count)