백준 9663 파이썬(Python) 문제풀이 N-Queen(N퀸)

문제링크:https://www.acmicpc.net/problem/9663

# limitation - 백트레킹 함수 > 퀸이 같은 행렬에 있으면 안됨, 퀸이 대각선에 있으면 안됨 false일시 그행 제외
# 입력 N은 NxN 체스판 row[0]*n 으로 사용
# result - > =+ 로 출력할 방법갯수 카운팅
# 출력 퀸을 놓을수있는 방법 출력
#
import sys

n = int(sys.stdin.readline())
row = [0] * n
cnt = 0

#퀸을 놓고 그 이후 놓기 불가능한 줄 찾기
def prommising(a):
    for i in range(a):
        if row[a] == row[i] or abs(row[a] - row[i]) == abs(a - i):
            return False
    return True


def queen(a):
    global cnt
    if a == n:  # <-- 재귀 탈출조건을 먼저 설계하는 것이 중요하다 마지막 줄에 다다르면 종료
        cnt += 1
        return
    else:
        for i in range(n):
            # 퀸을 [a,i]에 놓기
            row[a] = i
            if prommising(a):
                queen(a + 1)


queen(0)
print(cnt)