[Leetcode][python]N-Queens/N-Queens II/N皇后/N皇后 II

﹏ヽ暗。殇╰゛Y 2022-06-07 04:47 166阅读 0赞

# N-Queens #

## 题目大意 ##

经典的八皇后问题的一般情况  
注意点：  
皇后用”Q”表示，空白用”.”表示

## 解题思路 ##

回溯法，位运算等，见总结

## 代码 ##

### 回溯法 ###

**使用一位数组存储可能的解法例如\[1,3,0,2\]，最后再生成二位字符串图形**

如图理解：  
![这里写图片描述][SouthEast]

class Solution(object):
        def solveNQueens(self, n):
            """
            :type n: int
            :rtype: List[List[str]]
            """
            self.n = n
            result = []
            columns = [-1 for i in range(n)]  # [-1, -1, -1, -1]
            self.solve(columns, 0, result)
            return result
    
        # 绘出完整棋盘
        def make_string_list(self, columns):
            sol = []  # 一个完整的棋盘
            row = ['.' for i in range(self.n)]  # ['.', '.', '.', '.']
            for c in columns:
                new_row = row[:] 
                new_row[c] = 'Q'
                sol.append(''.join(new_row))  # 将row转为new_row, 将Q加入，然后转为字符串
            return sol
    
        # 判断是否符合要求
        def is_valid(self, columns, row, col):
            # print columns, 'hang', row, 'lie', col
            for r in range(row):
                c = columns[r]
                # print c, col
                if c == col:  # 在同一列，放弃
                    return False
                if abs(c - col) == row - r:  # 对角线，放弃
                    return False
            return True
    
        def solve(self, columns, row, result):
            if row == self.n:  # 所有列处理完毕
                # print 'columns:', columns # [1, 3, 0, 2], [2, 0, 3, 1]
                result.append(self.make_string_list(columns))
            else:
                for col in range(self.n):  # 依次遍历列,每个数字就代表每列皇后放在了第几行
                    if self.is_valid(columns, row, col):
                        columns[row] = col
                        self.solve(columns, row + 1, result)

### 位计算 ###

解决思路还是一行一行地查找。但是使用3个2进制数来存储列、左对角线、右对角线上不能下棋的位置。

如下图所示（1表示位置不合法）：  
![这里写图片描述][binary.png]

于是当前行所有不合法位置即为 row | ld | rd ，整体上加快了寻找合法位置的速度。

### 考虑问题的对称性 ###

将8皇后其中一个解垂直翻转后，可以得到一个新的解，故，可以只计算一半，从而加快时间。

# N-Queens II #

## 题目大意 ##

计算解的个数

## 解题思路 ##

不需要画图，有一个解就自增1

## 代码 ##

class Solution(object):
        def totalNQueens(self, n):
            """
            :type n: int
            :rtype: int
            """
            self.n = n
            self.result = 0
            columns = [-1 for i in range(n)]  # [-1, -1, -1, -1]
            self.solve(columns, 0, self.result)
            return self.result
    
        def is_valid(self, columns, row, col):
            # print columns, 'hang', row, 'lie', col
            for r in range(row):
                c = columns[r]
                # print c, col
                if c == col:  # 在同一列，放弃
                    return False
                if abs(c - col) == row - r:  # 对角线，放弃
                    return False
            return True
    
        def solve(self, columns, row, result):
            if row == self.n:  # 所有列处理完毕
                # print 'columns:', columns # [1, 3, 0, 2], [2, 0, 3, 1]
                self.result += 1
            else:
                for col in range(self.n):  # 依次遍历列,每个数字就代表每列皇后放在了第几行
                    if self.is_valid(columns, row, col):
                        columns[row] = col
                        self.solve(columns, row + 1, result)

## 总结 ##

代码我都尽量详细注释，并且把重要变量print出来便于理解

经典回溯法问题，解法很多，不过无外乎递归非递归等。  
看到用**位计算**的，以后学习参考，效率两道题目都是最高的。  
[https://github.com/zhsj/nqueen/blob/master/N%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98.md][https_github.com_zhsj_nqueen_blob_master_N_E7_9A_87_E5_90_8E_E9_97_AE_E9_A2_98.md]

[SouthEast]: /images/20220607/64c2bb3b190343b092f3b6272a021d79.png
[binary.png]: https://github.com/zhsj/nqueen/raw/master/binary.png
[https_github.com_zhsj_nqueen_blob_master_N_E7_9A_87_E5_90_8E_E9_97_AE_E9_A2_98.md]: https://github.com/zhsj/nqueen/blob/master/N%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98.md