[9663] N-Queen

문제

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

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

 

입력

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

 

출력

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

 

예제 입력 1

8

 

예제 출력 1

92

 

풀이

n-queen은 사이서울에서 한번 구현한 적이 있어서 이미 알고 있는 문제였다 그때는 2차원배열로 구현했어서 이번에는 인덱스를 이용해서 일차원 배열을 활용하여 n-queen을 구하려고했다. 그런데 자꾸 시간초과가 나서.. pypy로 했더니 시간초과가 나지 않는다.. 흠 어떤게 문제인지 모르겠으나 추후에 시간이 날때 pypy랑 python3의 차이를 알아봐야겠다

 

구현 방법은 윗행부터부터 오른쪽으로 한칸씩 배치해놨다고 가정한 후, 같은 열에 이미 queen이 있는지와 왼쪽 대각선 위, 오른쪽 대각선 위에 queen 이 있는지 검사해줬다. 2차원 배열로 그것도 c언어로 구현할때 꽤나 길게 작성했던 것 같은데 파이썬으로 짜니까 훨씬 간단했다.

 

n = int(input())
queen = [0 for _ in range(n)]
cnt = 0

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

def n_queen(x):
    global cnt
    if x == n:
        cnt +=1
        return
    
    for y in range(n):
        queen[x] = y
        if is_possible(x):
            n_queen(x+1)
n_queen(0)
print(cnt)