# [Leetcode][python]N-QueensN-Queens IIN皇后N皇后 II

xiaoxiao2021-02-28  9

# N-Queens

## 代码

### 回溯法

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)

# N-Queens II

## 代码

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)