[Leetcode 51] - N-Queens w/ Python

 

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.

You may return the answer in any order.

 

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 x n크기의 체스판이 있을때 n개의 퀸이 한 판에 같이 있을 수 있다

이런 경우 퀸들이 체스판에 있을 위치의 조합을 리턴하는 문제

 

 

 

 

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

 

 

 

 

---

 

 

 

 

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"]]

 

 

 

---

 

 

 

확실히 이런 유형의 문제는 한번 풀어보면 다음에 휠씬 나아지는것 같다

 

백트래킹으로 퀸이 놓였을때 놓지 못하는 자리를 저장한

다음 재귀로 넘어가는 형식으로 구현했다

 

 

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        col = set()
        posDiag = set()
        negDiag = set()
        
        ans = []
        board = [["."] * n for i in range(n)]

        def backtrack(r):
            if r == n:
                ans.append(["".join(row) for row in board])
                return
            
            for c in range(n):
                if c in col or (r + c) in posDiag or (r - c) in negDiag:
                    continue
                
                col.add(c)
                posDiag.add(r + c)
                negDiag.add(r - c)
                board[r][c] = "Q"

                backtrack(r + 1)
                
                col.remove(c)
                posDiag.remove(r + c)
                negDiag.remove(r - c)
                board[r][c] = "."
            
            return
        
        backtrack(0)
        return ans