51. N 皇后

<?php
class Solution {
    private $ret;
    /**
     * @param Integer $n
     * @return String[][]
     */
    public function solveNQueens($n) {
        $this->dp($n);
        return $this->ret;
    }
    public function dp($n, $arr = [], $ii = 0, $jj = 0) {
        if (count($arr) == $n) {
            $this->ret[] = $arr;
            return;
        }
        for ($i = $ii; $i < $n; $i++) {
            for ($j = $jj; $j < $n; $j++) {
                if (!$this->isConflict($arr, $i, $j)) {
                    continue;
                }
                $arr[$i][$j] = 1;
                $this->dp($n, $arr, $i + 1, 0);
                unset($arr[$i]);
            }
        }
        return;
    }
    /**
     * 判断加入 [$i , $j] 元素后是否还满足N皇后规则
     * @param $arr
     * @param $i
     * @param $j
     * @return bool
     */
    private function isConflict($arr, $i, $j) {
        // 检查横向
        if (isset($arr[$i])) {
            return false;
        }
        foreach ($arr as $k1 => $v1) {
            // 检查竖向
            if (isset($v1[$j])) {
                return false;
            }
            foreach ($v1 as $k2 => $v2) {
                // 左上，右上，左下，右下
                if ($i - $k1 == $j - $k2 || $i - $k1 == $k2 - $j || $k1 - $i == $j - $k2 || $k1 - $i == $k2 - $j) {
                    return false;
                }
            }
        }
        return true;
    }
    /**
     * 格式化打印
     * @param $arr
     * @return string
     */
    public function pt($arr) {
        $ret = '';
        if (!$arr) return "[][]";
        foreach ($arr as $k1 => $v1) {
            foreach ($v1 as $k2 => $v2) {
                $ret = $ret ? $ret . "\t": $ret;
                $ret = $ret . "[$k1][$k2] = $v2";
            }
        }
        return "[$ret]";
    }
}
$n = 10;
$cls = new Solution();
$r = $cls->solveNQueens($n);
array_walk($r, function (&$v) use ($cls) {
    $v = $cls->pt($v);
});
print_r($r);