51. N皇后

题意：

图解：

解题思路：

思路：
1. 枚举每一个位置，并将该位置放入竖，撇，捺数组中；
2. 枚举下一个位置之前，看该位置对应的竖，撇，捺是否已经有值；
3. 如果有值，则表示冲突，跳过，继续尝下下一个位置，直到遍历到最后一个位置；
4. 继续下一层枚举；

PHP代码实现：

class Solution {
    public $cols = [];//列
    public $pie = [];
    public $na = [];
    public $res = [];
    function solveNQueens($n) {
        $this->solve([], $n, 0);
        return $this->generateAnswer($n);
    }
    function solve($answer, $n, $i) {
        if ($i == $n) {
            array_push($this->res, $answer);
            return;
        }
        for ($j = 0; $j < $n; $j++) {
            if (in_array($j, $this->cols) || in_array($i + $j, $this->pie) 
                || in_array($i - $j + $n, $this->na)) continue;
            array_push($this->cols, $j);
            array_push($this->pie, $i + $j);
            array_push($this->na, $i - $j + $n);
            $answer[$i] = $j;
            $this->solve($answer, $n, $i + 1);
            array_pop($this->cols);
            array_pop($this->pie);
            array_pop($this->na);
        }
    }
    function generateAnswer($n) {
        $ret = [];
        foreach ($this->res as $v) {
            for ($i = 0; $i < $n; $i++) {
                $str = "";
                foreach ($v as $v1) {
                    if ($v1 == $i) $str .= "Q";
                    else $str .= ".";
                }
                array_push($ret, $str);
            }
        }
        return array_chunk($ret, $n);
    }
}

GO代码实现：

func solveNQueens(n int) [][]string {
    if n == 0 { return nil}
    res := make([][]int, 0)
    cols := make(map[int]bool, n)
    pie := make(map[int]bool, n)
    na := make(map[int]bool, n)
    dfs([]int{}, n, cols, pie, na, &res)
    return generate(res, n)
}
func dfs(rows []int, n int, cols, pie, na map[int]bool, res *[][]int) {
    row := len(rows)
    if row == n {
        temp := make([]int, len(rows))
        copy(temp, rows)
        (*res) = append((*res), temp)
        return
    }
    for col := 0; col < n; col++ {
        if !cols[col] && !pie[row + col] && !na[row - col] {
            cols[col] = true;
            pie[row + col] = true;
            na[row - col] = true
            dfs(append(rows, col), n, cols, pie, na, res)
            cols[col] = false
            pie[row + col] = false
            na[row - col] = false
        }
    }
}
func generate(res [][]int, n int) (result [][]string) {
    for _, v := range res {
        var s []string
        for _, val := range v {
            str := ""
            for i := 0; i < n; i++ {
                if i == val {
                    str += "Q"
                } else {
                    str += "."
                }
            }
            s = append(s, str)
        }
        result = append(result, s)
    }
    return
}