N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

어떻게 풀면 좋을까?

일단 퀸은 오와 열, 대각선 방향으로 칸 수에 상관없이 움직일 수 있다.

이 말은 곧 한 행에 하나의 퀸만 놓을 수 있다는 뜻이 된다.

행을 기준으로 생각하며 놓아보자. (n=5인 경우)

(0,0)에 퀸 하나를 놓는다.

그럼 1행에 놓을 수 있는 경우의 수는 (1,2), (1,3), (1,4) 세가지로 줄어든다.

2행, 3행.. 마지막 행까지 1) 같은 열에 퀸이 하나 이상 존재하지 않고 (각 행에는 퀸을 하나씩만 놓을 것이므로 따로 검사하지 않아도된다.) 2) 대각선 방향에도 퀸이 하나 이상 존재하지 않는 모든 행렬을 생성하면 될 것이다.

DFS와 백트래킹을 이용해서 구현해보겠다. (=모든 경우의 수를 고려하되, 가지치기로 경우의 수를 줄여나간다.)

class Solution:
    def dfs(self, ans, board, columns, r=0) :
        
        n = len(board)
        
        # 퀸을 n개 모두 놓았을 경우.
        if r == n :
            ans.append(["".join(row) for row in board])
            return
        
        for c in range(n) :
            
            # 유효한 경우에만 다음 행으로 이동.
            if self.isValid(board, columns, r, c) :
                board[r][c] = "Q"
                columns[r] = c
                self.dfs(ans, board, columns, r+1)
                board[r][c] = "."
            
        
    def isValid(self, board, columns, r1, c1) :
        
        for r2 in range(r1) :
            
            c2 = columns[r2]
            
            # |
            if board[r2][c1] == "Q":
                return False
            # / \
            if abs(c2-c1) == r1-r2:
                return False
            
        return True
        
    def solveNQueens(self, n: int) -> List[List[str]]:
        
        if n == 0 :
            return []
        
        ans = []
        board = [["."]*n for i in range(n)]
        
        columns = [-1]*n # 퀸의 좌표를 저장.
        self.dfs(ans, board, columns)
        
        return ans
            

비슷하지만 유효성을 판별하는 방법을 살짝 변경해보자.

col에는 이미 방문한 열의 번호를 저장하고 d1, d2에는 이미 방문한 대각선 방향의 정보를 저장해둔다.

코드로 표현해보면 다음과 같다.

class Solution:
    def dfs(self, n, r, col, d1, d2, curr=[], ans=[]):
        
        if r == n :
            res = ["."*i+"Q"+"."*(n-1-i) for i in curr]
            ans.append(res)
            return
        
        for c in range(n) :
            
            i = c # |
            a = r+c # /
            b = r-c # \
            
            if i in col or a in d1 or b in d2 :
                continue
            
            curr.append(i)
            col.add(i)
            d1.add(a)
            d2.add(b)
            
            self.dfs(n, r+1, col, d1, d2, curr, ans)
            
            curr.pop()
            col.remove(i)
            d1.remove(a)
            d2.remove(b)
        
    def solveNQueens(self, n: int) -> List[List[str]]:
        
        col = set()
        d1 = set()
        d2 = set()
        
        res = []
        self.dfs(n, 0, col, d1, d2, [], res)
        
        return res
        

문제 :

leetcode