Leetcode 51. 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. 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-Queen 퍼즐은 n * n 크기의 체스판에 n개의 체스를 두는 방법을 찾는 퍼즐이다.
가능한 모든 경우의 수를 리턴하시오.

예시

• 4 * 4 그리드에서 가능한 NQUEEN 의 예시

풀이법

• 이 문제는 사실상 주어진 row, col에 퀸을 둘수 있는지를 검사하는 코드만 잘 짜도 가능하다.
• 백트래킹이 어렵다면 스도쿠를 먼저 풀어보길 추천한다!
  https://leetcode.com/problems/sudoku-solver/description/

같은 col에 존재하는 여부

• 이건 이전에 두었던 퀸의 col위치를 파악해 쉽게 알수 있다.

같은 대각선에 존재하는지 여부

• 이 부분이 살짝 헷갈릴수 있는데, 퀸의 대각선에 퀸이 위치한다면 두 퀸의
  row + col 혹은 row - col 이 같다는 것이다!
• 이를 set과 같이 빠르게 찾아낼수 있는 자료구조에 저장해놓고 검사에 사용한다.

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        ans = []
        board = [['.'] * n for _ in range(n)]

        cols = set()
        diag1 = set()
        diag2 = set()

        def backtracking(row):
            if row == n:
                ans.append([''.join(i) for i in board])
                return

            for col in range(n):
                if col in cols or row - col in diag1 or row + col in diag2:
                    continue

                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)
                board[row][col] = 'Q'

                backtracking(row + 1)

                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)
                board[row][col] = '.'




        backtracking(0)
        return ans