题目描述

n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击(任意两个皇后不能位于同一行，同一列，同一斜线)。

给定一个整数n，返回所有不同的n皇后问题的解决方案。

每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。

测试样例

输入:1

输出:

  [["Q"]]

输入:4

输出:

[

  // Solution 1

  [".Q..",

  "...Q",

  "Q...",

  "..Q."

  ],

  // Solution 2

  ["..Q.",

  "Q...",

  "...Q",

  ".Q.."

  ]

]

解题思路

使用DFS，每次对每行可用的列进行搜索，并使用一个list记录下对应已使用的列，这里记为used_cols，使用过的列按其所在行的顺序被加入到其中。每次搜索时，先判断下len(used_cols)是否等于n，如果是，则说明每一行都已选择过了，这时候需要生成解决方案，终止搜索。

此题的另一个重点在于对每一行可用的列进行搜索时，怎么判断某一列可用呢？

题目要求是 任意两个皇后不能位于同一行、同一列、同一斜线，对这个规则转换下，对应变为当前搜索的这一列没有被其它行使用过、当前当前行、列的和以及差都没有出现过。

代码

class Solution:

    """

    @param: n: The number of queens

    @return: All distinct solutions

    """

    def solveNQueens(self, n):

        if n == 1:

            return [["Q"]]

        boards = []

        self.dfs(n, [], boards)

        return boards

    def dfs(self, n, used_cols, boards):

        # used_cols里记录的是使用过的列

        # 每行对应有一个

        if len(used_cols) == n:

            boards.append(self.draw(n, used_cols))

            return

        # used_cols的长度可作为当前行数（从0开始）

        cur_row = len(used_cols)

        for col in range(n):

            if not self.is_valid(used_cols, cur_row, col):

                continue

            self.dfs(n, used_cols + [col], boards)

    def draw(self, n, cols):

        board = []

        for col in cols:

            row_str = ''.join(['Q' if c == col else '.' for c in range(n)])

            board.append(row_str)

        return board

    def is_valid(self, used_cols, cur_row, cur_col):

        """检查列数、行列和、行列差有无被使用过"""

        if cur_col in used_cols:

            return False

        for row, col in enumerate(used_cols):

            if cur_row + cur_col == row + col:

                return False

            if cur_row - cur_col == row - col:

                return False

        return True