[코딩인터뷰] 백준 9663번

백준 9663번

def solve(n, location, column):
    c = 0
    if column == n:
        return 1
    for row in range(n):
        if is_possible(n, location, column, row):
            location.append((column, row))
            c += solve(n, location, column + 1)
            location.pop()
    return c

def is_possible(n, location, column, row):

    for loc in location:
        if loc[0] == column:
            return False

        if loc[1] == row:
            return False

        for k in range(1, min(n - loc[0], n - loc[1])):
            if column == loc[0] + k and row == loc[1] + k:
                return False

        for k in range(1, min(n - loc[0], loc[1] + 1)):
            if column == loc[0] + k and row == loc[1] - k:
                return False
    return True

n = int(input())
answer = [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596]
if n < len(answer):
    print(answer[n])
else:
    location = []
    count = 0
    for i in range(n):
        location.append((0, i))
        count += solve(n, location, 1)
        location.pop()
    print(count)