N-Queens

N x N 체스말판이 있다. Queen N개가 서로 공격받지 않도록 말판에 배치하는 방법을 구하는 문제이다. 완전탐색, 백트래킹, dfs 등 여러가지로 문제유형을 부를 수 있다. 아래 소개하는 문제는 각각 방법들, 방법의 수, 그리고 조금 복잡한 조건이 더해질 경우의 방법의 수를 구하는 문제이다.

N=4일 경우의 부분해 (CPH p.50)

https://leetcode.com/problems/n-queens/

N-Queens - LeetCode

https://leetcode.com/problems/n-queens-ii/

N-Queens II - LeetCode

https://cses.fi/problemset/task/1624

CSES - Chessboard and Queens

 

접근법

이 문제를 풀 때는 기존의 가능한 위치를 모두 담은 채로 재귀를 한다는 것을 각오하고, 이때 어떻게 하면 기존의 놓인 위치를 효율적으로 표현할 것인지에 대해 추가로 고민하면 좋을 것 같다. 그 방법이 바로 이전 queen의 위치를 column, rising diagonal, falling diagonal로 표현하는 것이다.

이전 queen이 해당 위치에 놓였는지를 나타내는 행렬 (CPH p.51)

즉, 각 행마다 queen이 놓일 수 있는 위치를 고민할때, 이전의 행들에서 해당 위치가 속한 열, 대각선 1, 2에 queen을 놓았었는지 여부를 확인하는 것이다. 맨 첫 줄부터 보면, 만일 현재 0번 column에 queen을 놓았다면 이것은 column[0] = True로 표시한 뒤 다음 행에 대해 재귀를 한다. 호출된 재귀함수에서는 0번 column에 놓아도 되는지를 고민할 때 column[0] 이 참인지를 체크하고, 만일 그렇다면 해당 옵션은 제외하고 더이상 탐색하지 않는다. 1, 2, 3번 column인 경우를 탐색할 것이다.

이렇듯, 내가 어떤 수를 놓을 때 그것이 valid한지를 확인하기 위해서 column, diag1, diag2를 모두 고려하는 것이다. diag들에 대해서는 만일 N이 행이나 열의 수라면 2N-1 개 만큼의 가지수가 존재할 것이다. 배열에 말판에 대한 행, 열 변수를 저장할 때 우리는 위에서부터 부여하므로, 그럴 경우 diag1은 f(x, y) = f(x-1, y+1) 의 규칙을 가지며 x+y를 계산하면 그 값이 대각선의 위치를 나타내게 된다. diag2는 조금 더 복잡한데, 주대각선(그림에서 3)은 배열 첨자로서 x 와 y 가 같은 경우이며, 그 바로 아래 대각선은 x = y + 1, 즉 -1 = y - x 인 상태로, 그보다 값이 1개 적어 2가 된다. 즉, x==y 일 때 N-1을 줘야 하는 상태에서 출발해, x가 y대비 초과한 만큼 그 상태에서 감소하므로, y-x+N-1을 하면, 예를 들어 맨 첫줄의 4의 위치에 해당하는 x=0, y=1의 경우 4가 나오려면, 1-0+4-1=4 가 된다. 그러나 해당 falling diagonal을 unique하게 표시하기만 하면 되므로  아래 코드처럼 x-y로 해도 상관없다.

코드 (N-queens II)

class Solution:
    def totalNQueens(self, n: int) -> int:
        d1 = [0] * (2*n-1)
        d2 = [0] * (2*n-1)
        c = [0] * n
        ans = 0
        def dfs(r): # place queen in r-th row
            if r == n:
                nonlocal ans
                ans += 1
                return
            else:
                for i in range(n):
                    if c[i] or d1[r + i] or d2[i - r + n-1]: continue
                    c[i] = d1[r + i] = d2[i - r + n-1] = 1
                    dfs(r + 1)
                    c[i] = d1[r + i] = d2[i - r + n-1] = 0
                    
        dfs(0)
        return (ans)

 

참고문헌

[CPH] Competitive Programmer’s Handbook, Antti Laaksonen, Draft August 19, 2019