N-Queens Problem using python

In [1]:

import numpy as np
import sys, copy, time
sys.path.append("/home/swyoo/algorithm")
from utils.verbose import logging_time

51. N-Queens

leetcode

이 문제를 스스로 풀진 못해서, 푸는과정을 분석해 봄.

Idea 1. 2D에서 모든 cases를 탐색

dfs를 exploration하면서 변하는 queens은 다음과 같은 의미를 지니게 디자인 되었다.

• 길이는 row를 탐색하는 것을 뜻함.
• 각 row에 들어있는 숫자는 column index를 의미한다.

일단 $n$ 개의 queen의 위치는 row별로 하나씩 밖에 두지 못한다는 사실을 이용하자.
그때, row별 queen의 위치를 column index로 하고,
각 row에 대해 모든 column 위치에 queen을 두는 방식으로
모든 row를 보면 모든 cases를 1번씩 탐색해볼 수 있다.

row를 depth로 두고, column을 adjacent list로 생각하면 된다.

visualization해보면 다음 그림과 같다.

따라서, $O(n^n)$ 존재.

In [2]:

class Solution(object):
    @logging_time
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        vis = np.zeros(shape=(n, n), dtype=str)
        def dfs(queens:list):
            """ explore all cases."""
            # visualization of exploration
            print("\r{}{:<50}".format(queens,""), end='')
            time.sleep(0.1)
            
            if len(queens) == n:
                result.append(queens)
                return
            for qidx in range(n):
                dfs(queens+[qidx])
        result = []
        dfs([])
        print("{0:}**{0:}={1:} cases exist".format(n, len(result)))
        
sol = Solution()
sol.solveNQueens(4, verbose=True)

[3, 3, 3, 3]                                                  4**4=256 cases exist
WorkingTime[solveNQueens]: 34211.43961 ms

Idea 2. 모든 case를 볼때, Pruning을 하자.

이전 row들에 queen들의 공격범위에 들어오는 부분은 새로운 queen을 두지 못한다.
공격범위 내에 들어오지 못하는 acceptable한 queen위치에 대해서만 exploration하자.
다음과 같이 구현한다.
새로운 row에 대해 queen을 두고자 할때 공격범위에 들어오는 부분에 대해서는 recursion하지 않고 skip함으로서 pruning을 한다.

어떤 방법으로든, check하는 함수 ($O(n)$이 걸림)를 만들 수 있지만, 참고한 코드에서 좀 예쁜? 방식으로 했기때문에 그를 바탕으로 설명하겠다.

Key point: 위에서 부터 queen방향을 두고, 아래로 탐색하기 때문에 이전에 둔 queen들에 대한 공격범위만 고려하면 된다.

먼저 현재 depth인 row위치를 기준으로 위쪽에서 queen을 두었다면, 밑 방향에 대해서 새로운 queen을 두지 못한다.
따라서, 이전에 row들에 대한 column위치를 저장하도록

이 코드에서는 가로, 세로에 대해 공격범위에 들어오는 부분을 check하는 것을 i - j, i + j 를 이용하였다.

c.f., check하는 것을 i - j, i + j 를 이용한 방식은 나중에도 유용하게 사용가능할 것 같다.

예를 들면,
i + j 를 이용하면 다음과 같이 된다. (/ 방향 check)

0 1 2 3
1 2 3 4
2 3 4 5
3 4 5 6

i - j 를 이용하면 다음과 같이 된다. (\ 방향 check)

0 -1 -2 -3
1 0 -1 -2
2 1 0 -1
3 2 1 0

이렇게 pruning 함으로 n개의 queen을 두려면 어떤 row에서 모든 column중에 무조건 하나의 queen을 두어야하는데,
모든 column에 대해 공격범위가 적용되서 queen을 둘수없으면 len(queens) < n 이 된 상태로 dfs가 finish 된다.

따라서, 경우를 search하는 과정에서 len(queens) == n(모든 row에 대해 각각 하나의 queen을 둘 수 잇는 경우)가 되는 경우만 res에 append한다.

Implementation

In [3]:

class Solution(object):
    @logging_time
    def solveNQueens(self, n):
        """ 
        :type n: int
        :rtype: List[List[str]]
        """

        def dfs(queens, slope1, slope2):
            """ queens, slope1, slope2에서 
            각 index 에 해당하는 value는 각 row위치에서 허용하지 않는 공격범위를 의미한다. (순서가 중요)
            예를 들면, queens=[0, 2] slope1=[0, -1] slope2=[0, 3] 인 경우, 
                row index 0, 1 에 대해 각각 다음 row에서 column 위치에 대해 queen을 놓을 수 없는 index를 체크 가능.
                queens=[0,2]이니까, 0과 2 위치에 둘 수 없다. 또한, 다음 row에 대해 (depth=3이니까 )
                3 - x = 0 또는 -1 인 column index `x`에 대해 queen을 놓을 수 없다. 
            따라서, list를 사용하는것이 적절하다."""
            i = len(queens)
            if i == n:
                res.append(queens)
                return
            for j in range(n):
                if j not in queens and i - j not in slope1 and i + j not in slope2:
                    # queens자체를 바꾸지 않도록 주의. 
                    dfs(queens + [j], slope1 + [i - j], slope2 + [i + j])

        res = []
        dfs([], [], [])
        return [["." * i + "Q" + "." * (n - i - 1) for i in sol] for sol in res]

In [4]:

sol = Solution()
n = 4
ans = sol.solveNQueens(n, verbose=True)
for i, res in enumerate(ans):
    print("=== {}-th sol ===".format(i+1))
    for line in res:
        print(np.array(line))

WorkingTime[solveNQueens]: 0.02480 ms
=== 1-th sol ===
.Q..
...Q
Q...
..Q.
=== 2-th sol ===
..Q.
Q...
...Q
.Q..