N-Queens
题目大意
经典的八皇后问题的一般情况 注意点： 皇后用"Q"表示，空白用"."表示
解题思路
回溯法，位运算等，见总结
代码
回溯法
使用一位数组存储可能的解法例如[1,3,0,2]，最后再生成二位字符串图形
如图理解：
网络异常，图片无法展示
|
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表示位置不合法）： [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0v7UDbv8-1615631437348)(github.com/zhsj/nqueen…)]
于是当前行所有不合法位置即为 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出来便于理解
经典回溯法问题，解法很多，不过无外乎递归非递归等。 看到用位计算的，以后学习参考，效率两道题目都是最高的。github.com/zhsj/nqueen…
