LeetCode-N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

输入: 4 输出: [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ] 解释: 4 皇后问题存在两个不同的解法。

经典的N皇后问题，经典解法为回溯递归，一层一层的向下扫描，需要用到一个pos数组，其中pos[i]表示第i行皇后的位置，初始化为-1，然后从第0开始递归，每一行都一次遍历各列，判断如果在该位置放置皇后会不会有冲突(

判断列是否冲突，只需要看state数组中state[0…k-1] 是否有和state[k]相等；判断对角线是否冲突：如果两个皇后在同一对角线，那么|row1-row2| = |column1 - column2|，（row1，column1），（row2，column2）分别为冲突的两个皇后的位置

)，以此类推，当到最后一行的皇后放好后，一种解法就生成了，将其存入结果res中，然后再还会继续完成搜索所有的情况，代码如下：

class Solution(object): def solveNQueens(self, n): """ :type n: int :rtype: List[List[str]] """ if n <= 0: return [] if n == 1: return [["Q"]] res = [] pos = [-1]*n row = 0#从0行开始 self.NQueens(row, n, pos, res) return res def NQueens(self, row, n, pos, res): #放置第row行的皇后 if row == n: item=[] for i in range(n):#行 tmp = "" for j in range(n):#列 if pos[i] == j:#存的列一致 tmp += "Q" else: tmp += "." item.append(tmp) print(pos,item) res.append(item) else: for col in range(n): if self.isValid(pos, row, col): pos[row] = col#存列 self.NQueens(row+1, n, pos, res) pos[row] = -1 def isValid(self, pos, row, col): for i in range(row): #检查当前行和前面行是否冲突即可。 #检查是否同列很简单，检查对角线就是行的差和列的差的绝对值不要相等就可以 if col == pos[i] or abs(row-i) == abs(col-pos[i]): return False return True

非递归解法见：http://www.cnblogs.com/TenosDoIt/p/3801621.html

阅读更多

转载于:https://www.cnblogs.com/AcceptedLin/p/9778853.html

相关资源：JAVA上百实例源码以及开源项目