N 皇后

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 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!