LeetCode51. N皇后问题

还是使用回溯法的套路来完成，具体代码如下，这个题目里的回溯其实就是把放了Q的，重置回'.'，也就是空棋，这里返回的是三维的，leetcode里需要是二维的，只要再把结果转换下就行，思路没差别

<?php 

class Solution {

    /**
     * @param Integer $n
     * @return String[][]
     */
    public $result = [];
 
    function solveNQueens($n) {
        $board = [];//step1. 初始化一个空的棋盘，里面都是"."
        for($i = 0; $i < $n; $i++){
            for($j = 0; $j < $n; $j++){
                $board[$i][$j] = '.';
            }
        }
        
        $this->test($board, 0);//棋盘, 行数
        
        return $this->result;
    }
    
    function test($board, $row){
        if($row >= count($board) ){
            $this->result[] = $board;
            return;
        }
        
        $n = count($board[$row]);
        for($col = 0; $col < $n; $col++){//为每列做选择
            if(!$this->valid($board, $row, $col)){
                continue;
            }

            //step1. 做选择
            $board[$row][$col] = 'Q';
            
            //step2. 到下一行做选择
            $this->test($board, $row + 1);
            
            //step3. 撤销选择，重要！！！！！
            $board[$row][$col] = '.';
            
        }
        
    }
    
    function valid($board, $row, $col){
        if(in_array('Q', $board[$row])){//如果行中已经有Q了，不通过
            return false;
        }
        
        for($i = 0; $i <= $row; $i++){//如果列中已经有Q了，不通过
            if($board[$i][$col] == 'Q'){
                return false;
            }
        }

        for($i = 0; $i <= $row ; $i++){//如果对角线中有Q了，不通过
            $newRow = $row - $i;
            $newColOne = $col - $i;
            $newCOlTwo = $col + $i;
            
            if(
                (isset($board[$newRow][$newColOne]) && $board[$newRow][$newColOne] == 'Q')
                || (isset($board[$newRow][$newCOlTwo]) && $board[$newRow][$newCOlTwo] == 'Q')   
            ){
                return false;
            }
        }
        
        
        return true;
    }
}


$obj = new Solution;
$x = $obj->solveNQueens(4);

foreach($x as $one => $v){
    foreach($v as $real){
        echo implode('', $real) . "\n";
    }
    echo "\n";
}