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

문제

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

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

입력

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

출력

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

소스코드

n = int(input())
ans = 0
# 세로, 대각선(/), 대각선(\)
arr1, arr2, arr3 = [0]*n, [0]*(2*n-1), [0]*(2*n-1)

def nqueen(x): # x는 현재 행
    global ans
    if x == n: # n개의 행에 퀸을 하나씩 둬야 하므로, x가 n이 되었다면 퀸을 다 둔 것
        ans += 1
        return
    for i in range(n):
        if arr1[i] or arr2[x+i] or arr3[x-i+n-1]: # 열이나 대각선에 이미 퀸이 놓아져있다면 그 경우는 생략
            continue
        arr1[i] = arr2[x+i] = arr3[x-i+n-1] = 1
        nqueen(x+1)
        arr1[i] = arr2[x+i] = arr3[x-i+n-1] = 0

nqueen(0)
print(ans)

풀이

n*n개의 체스판 위에 퀸 n개를 놓아두므로 퀸은 한 행에 하나씩 있어야 한다.
때문에 배열 arr1으로 각 행에 퀸이 어디있는지 나타낼 수 있음.
퀸은 대각선으로도 이동하므로, arr2와 arr3으로 어느 대각선에 퀸이 있는지 나타낸다.

그런데 대각선 배열을 어떻게 만들어야 할지 엄청 헷갈렸는데 제목 없음 이런 식으로 하면 되는 거였음. (arr2의 경우)
예를 들어 arr2 = [0, 1, 0 , 0, 0, 0, 0, 0] 이라면 저 1번 대각선에 퀸이 있는 것.
arr3은 맨 오른쪽 위가 0번이다.