N-Queen

• 전형적인 N-queen 문제
• 최대 입력 사이즈가 15인데, 기본적인 백트래킹 구현만으로는 Python3의 시간제한을 맞추기 어렵다. 대칭을 이용한 속도 향상 테크닉이 들어가야만 통과 가능
• 그렇지만, 그냥 15까지의 모든 입력에 대한 답을 미리 구해놓고 그것을 그냥 출력해주는 꼼수로 52ms에 통과하는 것도 가능하다.

• N-Queens 참고

• 29076KB / 27556ms

"""Solution code for "BOJ 9663. N-Queen".

- Problem link: https://www.acmicpc.net/problem/9663
- Solution link: http://www.teferi.net/ps/problems/boj/9663
"""


def solve(N, first_col):
    is_occupied_col = [i == first_col for i in range(N)]
    is_occupied_up_diag = [i == first_col for i in range(N * 2 - 1)]
    is_occupied_down_diag = [i == -first_col + N - 1 for i in range(N * 2 - 1)]

    def solve_rec(row):
        if row == N:
            return 1
        count = 0
        for col in range(N):
            u_diag = row + col
            d_diag = row - col + N - 1
            if (is_occupied_col[col]
                or is_occupied_up_diag[u_diag]
                or is_occupied_down_diag[d_diag]):
                continue
            is_occupied_col[col] = True
            is_occupied_up_diag[u_diag] = True
            is_occupied_down_diag[d_diag] = True
            count += solve_rec(row + 1)
            is_occupied_col[col] = False
            is_occupied_up_diag[u_diag] = False
            is_occupied_down_diag[d_diag] = False
        return count

    return solve_rec(1)


def main():
    N = int(input())
    answer = 0
    for i in range(N // 2):
        answer += solve(N, i) * 2
    if N % 2:
        answer += solve(N, N // 2)
    print(answer)


if __name__ == '__main__':
    main()

• 29076KB / 15468ms

"""Solution code for "BOJ 9663. N-Queen".

Backtracking on permutation.
- Problem link: https://www.acmicpc.net/problem/9663
- Solution link: http://www.teferi.net/ps/problems/boj/9663
"""


def solve(N, first_col):
    cols = list(range(N))
    cols[0], cols[first_col] = cols[first_col], cols[0]
    is_occupied_up_diag = [i == first_col for i in range(N * 2 - 1)]
    is_occupied_down_diag = [i == -first_col + N - 1 for i in range(N * 2 - 1)]

    def solve_rec(row):
        if row == N:
            return 1
        count = 0
        for i in range(row, N):
            col = cols[i]
            u_diag = row + col
            d_diag = row - col + N - 1
            if is_occupied_up_diag[u_diag] or is_occupied_down_diag[d_diag]:
                continue            
            cols[row], cols[i] = cols[i], cols[row]
            is_occupied_up_diag[u_diag] = True
            is_occupied_down_diag[d_diag] = True
            count += solve_rec(row + 1)
            cols[row], cols[i] = cols[i], cols[row]
            is_occupied_up_diag[u_diag] = False
            is_occupied_down_diag[d_diag] = False
        return count

    return solve_rec(1)


def main():
    N = int(input())
    answer = 0
    for i in range(N // 2):
        answer += solve(N, i) * 2
    if N % 2:
        answer += solve(N, N // 2)
    print(answer)


if __name__ == '__main__':
    main()