51.52.N皇后——经典问题,八皇后n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上,并且使皇后彼此之间不能相互攻击。上图为 8 皇后问题的一种解法。给定一个整数n,返回所有不同的n皇后问题的解决方案。每一种解法包含一个明确的n皇后问题的棋子放置方案,该方案中'Q'和'.'分别代表了皇后和空位。输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]解释: 4 皇后问题存在两个不同的解法。51和52的区别仅在于,52只要求结果的数量,51要求求出所有可能的排列方式解法:递归回溯,逐行的搜索在每一行中,皇后应该出现在哪。每一次尝试在一行中摆放皇后,看能不能摆下这个皇后,如果不能则回溯到上一行重新摆放上一个皇后如下递归树(1)在递归树中,从第一行开始检索,占领第一行第一个元素(2)开始检索第二行,第二行还有0,1,2,3下标四个元素,但是0下标元素跟第一行元素在同一列,1下标元素在第一行元素的对角线上,因此可以减掉0,1两个分支(3)以此类推,找到所有符合条件的摆放如何快速判断不合法的情况,如何快速剪枝:(1)横向:每一次都是在下一行检索,所以不会有行冲突的问题(2)竖向:用$this->col[$i]表示第 i 列被占用(3)对角线1:利用$
...
继续阅读
(16)