[알고리즘] N-Queens 문제

문제링크

20분 문제 풀이 실패한 문제. 퀸을 배치할 수 있는 모든 경우의 수를 생각하려고 하니 어려웠다.

🤔 Thinking

핵심이 되는 것은 퀸의 특성에 있다.

퀸은 가로, 세로, 대각선을 이동할 수 있기에 매번 새로 퀸을 배치 할 때마다 조건을 확인한다.

체스판을 2차원 배열로 생각하면 같은 행에는 퀸은 한개만 배치가 가능하다.

따라서 행을 기준으로 하나의 열을 선택하면 다음 행을 찾아 비교한다.

---

만약 행마다 퀸이 배치되어 있어야하기 때문에 행에서 조건을 전부 만족하는 경우가 없는 경우 답이 될 수 없다(non-promising). 따라서 다음 행을 이어서 탐색하지 않고 백트래킹을 수행하여 다음 가능한 행을 선택한다.

위와 같은 경우 3번째 행의 탐색을 종료하고 2번째행을 이어서 탐색한다.

1번째 행의 1번 열부터 n번열까지 선택을 했을 때 다음 행의 1번열부터 n번열까지 탐색을 하면서 카운트한다.

코드

위의 예시와 같이 행을 기준으로 코드를 작성한다.
colList[row] = i 에서 colList는 row 행을 기준으로 했을 때 열의 위치 i 를 의미한다.

여기서 구현하기 까다로운 것은 조건을 확인하는 것이다.
우선 행은 이미 한개의 기물만 배치하고 있기 때문에 확인해야할 조건은 다음과 같다.

• 모든 기물이 같은 열에 있으면 안된다.
• 모든 기물이 대각선으로 만나면 안된다.

1. 모든 기물이 같은 열에 있으면 안된다.
같은 열에 있는 지 확인하는 것은 단순히 배치하고자 하는 기물의 열과 기존에 배치한 기물의 열이 같은지만 확인하면 된다.
colList 의 값이 열에 해당하기 때문에 전체 반복문을 돌면서 확인한다.

2. 모든 기물이 대각선으로 만나면 안된다.
대각선으로 확인하는 과정은 x 증가량과 y 증가량이 같은 경우로 생각할 수 있다.
예를 들어 (1, 1) 과 (2, 2) 는 같은 대각선 상에 존재한다. (1, 2) 와 (3, 4) 는 x 증가량과 y 증가량이 2로 같은 경우여서 대각선에 위치한다.

거꾸로 (1, 2) 와 (2, 1) 은 x 증가량은 1 , y 증가량은 -1 이지만 절댓값은 같은 것을 확인할 수 있다.
다른 경우에서도 마찬가지로 x의 변화량과 y의 변화량이 같은 경우 같은 대각선 상에 위치한다.

ans = 0

def promising(row, colList):
    for i in range(row):	# 현재까지의 모든 행을 확인하면서 조건체킹
        if (colList[row] == colList[i]  # 열 체크
            or abs(colList[row] - colList[i]) == abs(row-i)):   # 대각선 체크
            return False
    return True

def n_queens(n, row, colList):
    global ans
    if row == n:	# 모든 행에 기물이 배치 된 경우 카운트
        ans += 1
        return
    
    for i in range(n):
        colList[row] = i	# row 행에 i 번째열에 기물 배치
        if promising(row, colList):		# 기물 배치가 가능하면 다음 행 탐색
            n_queens(n, row+1, colList)

n = int(input())
colList = [0] * n
n_queens(n, 0, colList)
print(ans)

📕 참고 문헌

다음의 링크를 참고했습니다.
파이썬으로 배우는 알고리즘 기초: 19. n-Queens 문제의 구현