LeetCode

Appearance

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.

 

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

 

Constraints:

  • 1 <= n <= 9
Related Topics
  • 数组
  • 回溯

  • 👍 2308
  • 👎 0

    • 思路 ​

    chess 中 queen 可攻击的范围是

    • 同一排（horizon）
    • 同一列 (vertical)
    • 对角逻辑 (digonal)
      • 对角分为 45度角 top-left 和135度角 top-right 两边

    本题是一个全排列问题，终止条件为遍历完整个棋盘方可记录结果。可以通过棋盘存储结果，当遍历到最后一行时，记录结果

    剪枝操作

    • 同列，不同方向的对角线进行剪枝
    • 同行排列无需剪枝，因为每一行中只会进入到回溯逻辑中一次，不存在进入回溯逻辑两次

    解法 ​

    python
    class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        chess_board = [['.' for _ in range(n)] for _ in range(n)]
        def backtrack(row, board):
            if row == n:
                res.append([''.join(r) for r in board])
                return

            for j in range(n):
                if isValid(row, j, board):
                    board[row][j] = 'Q'
                    backtrack(row + 1, board)
                    board[row][j] = '.'
                else:
                    continue


        def isValid(row, col, used):

            # check for vertical
            for i in range(row):
                if used[i][col] == 'Q':
                    return False

            i, j = row - 1, col + 1
            while i >= 0 and j < len(used):
                if used[i][j] == 'Q':
                    return False
                else:
                    i -= 1
                    j += 1

            while row >= 0 and col >= 0:
                if used[row][col] == 'Q':
                   return False
                else:
                    row -= 1
                    col -= 1

            return True


        backtrack(0, chess_board)

        return res

    复杂度分析 ​

    • 时间复杂度 O(N* N!)
    • 空间复杂度 O(N * N)

    解法二 ​

    剪枝优化 如何判断元素是否在同一列，同一对角线？

    • 同一列 Col 值相同
    • 同一对角线
      • 45度对角线 row - col 值相同
      • 135度对角线 row + col 值相同

    可以使用 Set 存储已使用过的Col 和 对角线 回溯结束后，需要将 Set 的存储复位

    此时剪枝操作复杂度由O(N) 降低为 O(1)

    py
    # leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        chess_board = [['.' for _ in range(n)] for _ in range(n)]
        col_set = set()
        dig1_set = set()
        dig2_set = set()
        def backtrack(row, board):
            if row == n:
                res.append([''.join(r) for r in board])
                return

            for col in range(n):
                if col not in col_set and (row - col) not in dig1_set and (row + col) not in dig2_set:
                    col_set.add(col)
                    dig1_set.add(row - col)
                    dig2_set.add(row + col)

                    board[row][col] = 'Q'
                    backtrack(row + 1, board)
                    # remove col
                    board[row][col] = '.'
                    col_set.remove(col)
                    dig1_set.remove(row - col)
                    dig2_set.remove(row + col)
                else:
                    continue



        backtrack(0, chess_board)

        return res
        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度 O(N!)
    • 空间复杂度 O(N)