[BOJ] 👸 N-Queens / 파이썬

👸 N-Queens

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

😃 나의 풀이

def nqueen(sol, n):
    global count

    if len(sol) == n:    # 정답 배열(sol)의 길이가 n과 같아지면, count 증가
        count += 1
        return 0
    candidate = list(range(n))    # 0부터 n-1까지를 후보 배열로 만든다.
    for i in range(len(sol)):
        if sol[i] in candidate:    # 같은 열에 있는 지 확인
            candidate.remove(sol[i])    # 같은 열에 있다면 후보에서 제외
        distance = len(sol) - i
        if sol[i] + distance in candidate:    # 같은 대각성 상(+)에 있는 지 확인
            candidate.remove(sol[i] + distance)    # 같은 대각선 상에 있다면 후보에서 제외
        if sol[i] - distance in candidate:    # 같은 대각선 상(-)에 있는 지 확인
            candidate.remove(sol[i] - distance)    # 같은 대각선 상에 있다면 후보에서 제외
    if candidate != []:
        for i in candidate:
            sol.append(i)    # 후보의 요소를 정답 배열의 i+1로 추가
            nqueen(sol, n)    # 재귀적으로 다음 행도 확인
    else:
        return 0

count = 0
num = int(input())

for i in range(num):    # 첫 행의 경우의 수
    nqueen([i], num)

print(count)

N-Queens는 백트랙킹 알고리즘의 예시로 자주 이용되는 문제이다. 백트랙킹 알고리즘은 노드의 유망성 점검 후, 유망하지 않으면 그 노드의 부모로 되돌아간 후 다른 자식 노드를 검색하는 알고리즘이다.

우선, 첫 행의 경우의 수를 산정하고 nqueen 함수에 넣는다. 그리고 각 행의 후보군을 만들어 위에 설명한 백트랙 알고리즘의 유망성이 있는 자식노드와 유망성이 없는 자식 노드를 구분하여 한 행씩 추가하면서, 완성된 정답 배열을 만들어 나간다.

4X4 크기의 N-Queens 문제

참고자료

• 여덟 퀸 문제