Leetcode: N Queens

The n-queens puzzle is the problem of placing n queens on an n x 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.

 
Example 1:


Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:

Input: n = 1
Output: [["Q"]]

 

유명한 N Queens 문제이다. N * N의 체스판이 있을 때에, N개의 퀸을 서로 공격할 수 없는 위치에 놓는 방법을 찾는 것으로, 대표적인 dp & 백트래킹 알고리즘 문제이다. 

N * N의 array를 선언하고 퀸의 위치를 마킹하는 방법도 있겠지만, 한 행에 단 하나의 퀸만 있을 수 있으므로, 일차원 array로도 풀 수 있다. 이 경우, quuen_idx[i] = j 가 의미하는 것은, i번째 행의 j번째 열에 queen이 놓여있는 상태라는 의미이다.

0번째 행부터 n-1번째 행까지 순서대로 queen을 놓는다. 각 행에서는 0~n-1번째 열까지 queen을 놓는다. 이 때, 현재 queen이 놓인 자리가 valid하다면 다음 행에 대하여 dfs를 호출하고, 백트래킹 알고리즘들이 그렇듯 이후 queen_idx[i]를 리셋한다. 다만, 이 풀이방법에서는 1차원 array를 사용하므로 에서는 다음 for문이 돌면서 기존에 둔 queen의 위치를 지워버리기 때문에 굳이 리셋하지 않아도 된다. 이차원어레이를 사용했다면 반드시 리셋하는 과정이 필요하다. 

 

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        queen_idx = [0 for _ in range(n)] # queen_idx[i] = x -> matrix[i][x]에 queen이 놓여있다
        answer = []

        # i-1번째 행까지 queen이 놓여있다는 가정 하에 i번째 행에 queen을 놓는다.
        def isValid(i: int) -> bool:
            for k in range(i):
                if queen_idx[k] == queen_idx[i] or abs(k-i) == abs(queen_idx[k]-queen_idx[i]): return False
            return True

        def dfs(i: int):
            if i == n:
                answer.append(list(map(lambda x: "".join(["Q" if x == idx else "." for idx in range(n)]), queen_idx)))
                return

            for j in range(n):
                queen_idx[i] = j
                if isValid(i):
                    dfs(i+1)

        dfs(0)
        return answer

 

 

 

링크: leetcode.com/problems/n-queens/

N-Queens - LeetCode