33. N皇后问题
中文Englishn皇后问题是将n个皇后放置在n*n的棋盘上,皇后彼此之间不能相互攻击(任意两个皇后不能位于同一行,同一列,同一斜线)。
给定一个整数n,返回所有不同的n皇后问题的解决方案。
每个解决方案包含一个明确的n皇后放置布局,其中“Q”和“.”分别表示一个女王和一个空位置。
样例
例1:
输入:1
输出:
[["Q"]]
例2:
输入:4
输出:
[
// Solution 1
[".Q..",
"...Q",
"Q...",
"..Q."
],
// Solution 2
["..Q.",
"Q...",
"...Q",
".Q.."
]
]
挑战
你能否不使用递归完成?
输入测试数据 (每行一个参数)如何理解测试数据?DFS(回溯) + 验证是否合法 + 绘制函数(cols每一个代表着各行的皇后符合的所在列)
class Solution: """ @param: n: The number of queens @return: All distinct solutions """ def solveNQueens(self, n): # write your code here #dfs(回溯) + 验证是否合法 + 最后合法绘制 results = [] cols = [] self.dfs(results, cols, n, 0) return results #递归的定义 #传入参数,第一个参数results最终返回结果 #第二个参数cols,代表着列数列表,每一行分别占一个列col,多个col表示多个行 #第三个参数,合计的n #第四个参数,row,代表的当前正在回溯的第几行,每一行都会进行一次for循环列数判断,是否合法,合法,则当前行通过 def dfs(self, results, cols, n, row): #递归的出口,如果符合条件,则绘制 #每一次都是一次完整的cols,会有n个col写进来,然后在进行绘制 if (len(cols) == n): #得到一个绘制图,则在这里append进来 board = self.draw(cols) results.append(board) return #递归的拆解 #后面是会dfs,回溯继续判断是否符合条件,注意:这里是列的循环,行的话合法每一行都会进行回溯判断 for i in range(n): #判断是否符合条件 if self.isValid(cols, i): #当前列符合,加进来 cols.append(i) self.dfs(results, cols, n, row + 1) cols.pop() #传入两个参数,一个是当前的cols列数[],以及当前的行数 def isValid(self, cols, col): row = len(cols) #第一个是行,第二个是列 #如果是同列的话,False for r, c in enumerate(cols): if (c == col): return False #如果是斜方向相等的话,False if abs(r - row) == abs(c - col): return False return True #传入的参数:cols,列数 def draw(self, cols): board = [] n = len(cols) #绘制行 for i in range(n): #绘制列 cur_board = '' for j in range(n): #当前行的列cols[i],放置皇后,cols[i]是当前行的皇后的位置 if (cols[i] == j): cur_board = cur_board + 'Q' else: cur_board = cur_board + '.' board.append(cur_board) return board
绘制函数draw另一种简便写法:
#传入的参数:cols,列数 def draw(self, cols): board = [] n = len(cols) #绘制行 for i in range(n): #绘制列 #当前行的列cols[i],放置皇后,cols[i]是当前行的皇后的位置 cur_board = ['Q' if cols[i] == j else '.' for j in range(n)] board.append(''.join(cur_board)) return board