经典的八皇后问题的一般情况
注意点:
皇后用”Q”表示,空白用”.”表示
方法很多,见总结
class Solution(object): def solveNQueens(self, n): """ :type n: int :rtype: List[List[str]] """ self.n = n # 由于之后还要用到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)
每个方法我都尽量详细注释,并且把重要变量print出来便于理解。