LeetCode 解题报告 (51)-- 回溯法解决 N 皇后问题

发表于 标签 ，

原题如下： >The n-queens puzzle is the problem of placing n queens on an n×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.

For example, There exist two distinct solutions to the 4-queens puzzle:

1
2
3
4
5
6
7
8
9
10
11
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

经典的 n 皇后问题，通过回溯法解决。

关键的地方有以下几点： 1）由于题目本身的特点，每一行只能放置一个皇后，因此每行只要找到第一个合适的位置便可跳到下一行找下一个皇后的合适位置。 2）由于遍历的顺序是从坐到又从上到下的，因此判断当前位置能否放置皇后时只需要判断当前位置上方的列、左上斜边、右上斜边是否有皇后即可。

实现的代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        solutions = []
        board = [['.' for i in range(n)] for j in range(n)] #生成n*n的原始矩阵
        self.helper(board, solutions,0 )
        return solutions


    def helper(self,board,solutions, row):
        n = len(board)
        if row==n:
            tmp=[]          
            for i in board:
                tmp.append(reduce(lambda x,y:x+y,i)) # reduce函数的作用是将['Q','.','.','.']转为'Q...'
            solutions.append(tmp)
            return

        for i in range(n):
            if self.is_valid(board,row,i):
                board[row][i] = 'Q'
                self.helper(board,solutions,row+1)
                board[row][i] = '.'


    def is_valid(self,board,i,j):
        n = len(board)
        # check column
        for k in xrange(n):
            if board[k][j] == 'Q':
                return False

        # check diagonal，只需要检查上面的两条边
        ri = i
        rj = j
        while 0<=i<=n-1 and 0<=j<=n-1:
            if board[i][j]=='Q':
                return False
            i-=1
            j-=1

        i = ri
        j = rj
        while 0<=i<=n-1 and 0<=j<=n-1:
            if board[i][j]=='Q':
                return False
            i-=1
            j+=1
        return True
上面的代码虽然结果正确，但是判断当前位置能否放置皇后的方法效率较低，判断的一次的平均时间复杂度为O(n)，n为棋盘的边的大小，下面主要介绍一种判断当前位置能否放置皇后的时间复杂度为O(1)的方法。

通过观察可发现，在同一条左斜边上的每个点的行值加上列值的结果相等，而在同一条右斜边上的每个点的行值减去列值的结果相等。如下图所示就是左斜线每个点的行值加上列值的情况：

右斜线每个点的行值减去列值的情况同理。

由于这些结果大小是连续的，因此我们可以使用数组的下标代表某一斜边，用该下标的对应的数组值（0 或 1）表示该斜边上是否有皇后。设棋盘的大小为 n*n。则左斜边的范围为 [0,2n-2], 长度为 2n+1；右斜边的范围为 [-n+1,n-1], 由于数组的下标不能为负，所以每个下标加上 n-1，将范围变为 [0,2n-2], 长度同样为 2n-1。

实现的代码如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        solutions = []
        board = [['.' for i in range(n)] for j in range(n)] #生成n*n的原始矩阵
        col = [0 for i in range(n)]
        left_dia =  [0 for i in range(2*n-1)]
        right_dia = [0 for i in range(2*n-1)]

        self.helper(board, solutions,0, col,left_dia,right_dia)
        return solutions


    def helper(self,board,solutions,row,col,left_dia,right_dia):
        n = len(board)
        if row==n:
            tmp=[]          
            for i in board:
                tmp.append(reduce(lambda x,y:x+y,i)) # reduce函数的作用是将['Q','.','.','.']转为'Q...'
            solutions.append(tmp)
            return

        for i in range(n):
            if col[i]==0 and left_dia[row+i]==0 and right_dia[i-row+n-1]==0:
                board[row][i] = 'Q'
                col[i],left_dia[row+i],right_dia[i-row+n-1]=1,1,1
                self.helper(board,solutions,row+1,col,left_dia,right_dia)
                board[row][i] = '.'
                col[i],left_dia[row+i],right_dia[i-row+n-1]=0,0,0