9663. N－Queen

업데이트 시간 : 2023-01-30 13:07:02 +0000

[Gold IV] N-Queen - 9663

문제 링크

성능 요약

메모리: 126836 KB, 시간: 11424 ms

분류

백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing)

문제 설명

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

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

입력

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

출력

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

💡 Solutions

📄 N－Queen.py

import sys

def dfs(n, y, col, diag1, diag2):
    global answer
    if y == n:
        answer += 1
        return

    for x in range(n):
        if x in col or (x + y) in diag1 or (x - y) in diag2:
            continue
        col.add(x)
        diag1.add(x + y)
        diag2.add(x - y)
        dfs(n, y+1, col, diag1, diag2)
        col.remove(x)
        diag1.remove(x + y)
        diag2.remove(x - y)


def solution(n):
    global answer
    col, diag1, diag2 = set(), set(), set()
    answer = 0
    dfs(n, 0, col, diag1, diag2)
    return answer  

print(solution(int(sys.stdin.readline())))