N-Queen Python (SW Expert Academy)

출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE

SW Expert Academy

1. 문제 설명

8*8 체스보드에 8개의 퀸을 서로 공격하지 못하게 놓는 문제는 잘 알려져 있는 문제이다.

퀸은 같은 행, 열, 또는 대각선 위에 있는 말을 공격할 수 있다. 이 문제의 한가지 정답은 아래 그림과 같다.

이 문제의 조금 더 일반화된 문제는 Franz Nauck이 1850년에 제기했다.

N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수는 몇가지가 있을까?

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


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 하나의 자연수 N(1 ≤ N ≤ 10)이 주어진다.


[출력]

각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

2. 코드

퀸을 놓는 N 크기의 배열(열 위치)를 만든 뒤 그 배열에 행의 위치를 저장시키는 방식을 사용하였습니다. 같은 값이 들어 가 있는 경우는 같은 행에 존재하는 것이므로 재귀를 종료시키고, 같은 대각선에 존재하는 경우 또한 간단한 계산을 통해 검사하며 재귀를 종료시켰습니다.

 

아래가 작성한 코드입니다.

# 이전까지 열에서 가능한지 검사하는 함수
def pos(k):
    # 같은 행에 존재하거나 대각선에 존재하면 False
    for i in range(k):
        if arr[k] == arr[i] or abs(arr[k] - arr[i]) == k - i:
            return False
    return True
 
# 가능한 퀸의 위치 개수를 찾는 함수
def queen(k):
    global result
    # 가능하면 결과값 +1
    if k == N:
        result += 1
    else:
        # 각 열마다 0 ~ N-1 행에 퀸을 배치
        for i in range(N):
            arr[k] = i
            # 가능한 경우 진행
            if pos(k):
                queen(k+1)
 
T = int(input())
for tc in range(1, T+1):
    N = int(input())
    result = 0
    # 각 열에 어느 행에 퀸이 존재하는지 표시할 배열
    arr = [0 for _ in range(N)]
    queen(0)
    print('#{} {}'.format(tc, result))