"""
출처:프로그래머스,
https://school.programmers.co.kr/learn/courses/30/lessons/12952
"""

# 풀이 과정
def check(chess, n, queen):
    count = 0
    if n == queen:
        return 1

    for i in range(n):
        chess[queen] = i
        for j in range(queen):
            if chess[j] == chess[queen]:
                break
            if abs(chess[j] - chess[queen]) == (queen - j):
                break
        else:
            count += check(chess, n, queen + 1)
    return count


def solution(n):
    chess = [0] * n
    return check(chess, n, 0)