https://www.acmicpc.net/problem/9663

• 백트레킹의 전형적인 문제
• 각 행을 순회하면서 열에 퀸을 넣어 본다.
• 이 때, 대각선 or 같은 열 or 같은 행일 경우 해당 위치는 제외

• row 배열 추가
  • row[x]: x 행의 퀸의 열의 위치
• x를 1씩 늘려가면서 재귀적으로 검사
  • x == n이면 탈출(모든 행 검사 완료)
• 들어간 퀸에 대해서, 이전 행의 퀸의 위치와 비교 필요
  • 대각선 or 같은 열에 있을 경우, 다음행으로 진입 불가
  • 아닐 경우 다음행 진입

n = int(input())
row = [0] * n
count = 0

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

def n_queen(x):
    global count
    if x == n:
        count += 1
        return
    
    for i in range(n):
        row[x] = i
        if is_valid(x):
            n_queen(x+1)
            
n_queen(0)
print(count)