N 皇后
输入:4
输出:[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
提示:
- 皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同一条横行、纵行或斜线上。
这是一道比较经典的回溯算法题
本题的思路通过循环N项,依次判断是否可放置Q,通过hasQueen判断纵行和左上,右上斜线是否存在Q,不存在则放置Q继续回溯下一行放置Q位置直到N项都放满,存在则跳过当前行列
public $NQueens = [];
function solveNQueens($n) {
$arr = array_fill(0,$n,array_fill(0,$n,'.'));
$this->flashBack($arr,$n,0);
return $this->NQueens;
}
function flashBack($arr,$n,$i)
{
if ($i == $n){
$tmp = [];
foreach($arr as $item){
$tmp[] = implode('', $item);
}
$this->NQueens[] = $tmp;
return;
}
for ($j=0;$j<$n;$j++){
if ($this->hasQueen($n,$arr,$i,$j)){
continue;
}
//回溯
$arr[$i][$j] = 'Q';
$this->flashBack($arr,$n,$i+1);
$arr[$i][$j] = '.';
}
}
public function hasQueen($n,$arr,$row,$col)
{
// 同一行不存在冲突,无需处理
// 左下和右下此时为空,无需处理
// 同一列
for ($i=0;$i<$n;$i++){
if ($arr[$i][$col] == 'Q'){
return true;
}
}
// 右上,row - 1, col + 1
$i = $row - 1;
$j = $col + 1;
for (; $i >= 0 && $j < $n; --$i, ++$j) {
if ($arr[$i][$j] == 'Q') return true;
}
// 左上, row - 1, col - 1
$i = $row - 1;
$j = $col - 1;
for (; $i >= 0 && $j >= 0; --$i, --$j) {
if ($arr[$i][$j] == 'Q') return true;
}
return false;
}
本作品采用《CC 协议》,转载必须注明作者和本文链接