题解 | #N皇后问题#

<?php
function ceshi($qipan,$n,$row,$col){//这是判断一个棋子放在指定位置合理性的函数
    
    //检测同列有没有棋子 如果有 棋子放在这个位置不合理 返回false
    for($i=0;$i<$n;$i++){
        if ($qipan[$i][$col]=="Q")return false;
    }

    //检测左上方45度对角有没有棋子 如果有 棋子放在这个位置不合理 返回false
    for($i=1,$j=1;$i<=$col&&$j<=$row;$i++,$j++){
        if ($qipan[$row-$i][$col-$j]=="Q")return false;
    }
    //检测右上方45度对角有没有棋子 如果有 棋子放在这个位置不合理 返回false
    for($i=1,$j=1;$i<=$row&&($col+$j)<$n;$i++,$j++){
        if ($qipan[$row-$i][$col+$j]=="Q")return false;
    }
    //不检测同行棋子合法性是因为放了个棋子之后会马上换一行 所不需要判断同行 不检测下方是为了空间时间复杂度优化 因为是从第一行步进向下的所以不需要检测下方的 上方所有判断都合规 证明这个落子是合规的 棋子可以放在这里 返回true
    return true;
}
function digui($qipan,$n,$row,$shuliang){//这是棋盘递归方法
    
    if($row>=$n){
        //如果递归到了最后一排 代表整个棋盘都递归完了 
        $shuliang++;
        //加一个可以摆放方式技术
        return $shuliang;
        //返回计数给上一层
    }
    for($i=0;$i<$n;$i++){
        //从第一列开始从左到右
        if(ceshi($qipan,$n,$row,$i)){//如果棋子放在这里合理的话
            //将棋子放在这里
            $qipan[$row][$i]='Q';
            //递归自己 将行数加一 检测下一排棋子应该放在哪
            $shuliang=digui($qipan,$n,$row+1,$shuliang);
            //回溯了后 把之前放在这里的棋子拿起啦
            $qipan[$row][$i]='.';
        }
    }
    //返回计数给上一层
    return $shuliang;
}
function Nqueen( $n )
{
    //创建一个数组
    $qipan=[];
    //按照棋盘的长宽创建一个棋盘
    $qipan=array_pad($qipan,$n,array_pad($qipan,$n,'.'));
    //从棋盘的第一行第一列开始递归查询
    $shuliang=digui($qipan,$n,0,0);
    //返回计数
    return $shuliang;
}