<?php
/**
 * 八皇后问题：八皇后问题是一个古老的问题，于1848年由一位国际象棋棋手提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，如何求解？
 *
 * 问题分析：
 * 1. 满足上述条件的八个皇后，必然是每行一个，每列一个
 * 2. 棋盘上任意一行、任意一列、任意一条斜线上都不能有两个皇后
 *
 * 解决方法：递归回溯
 * 所谓递归回溯，本质上是一种枚举法。这种方法从棋盘的第一行开始尝试摆放第一个皇后，摆放成功后，递归一层，再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放，则向右移动一格再次尝试，如果摆放成功，则继续递归一层，摆放第三个皇后......
 *
 * 如果某一层看遍了所有格子，都无法成功摆放，则回溯到上一个皇后，让上一个皇后右移一格，再进行递归。如果八个皇后都摆放完毕且符合规则，那么就得到了其中一种正确的解法。
 *
 * 解决八皇后问题，可以分为两个层面：
 * 1. 找出第一种正确摆放方式，也就是深度优先遍历
 * 2. 找出全部的正确摆放方式，也就是广度优先遍历
 *
 * 输出格式：
 * 类似下面的格式结果
1   0   0   0   0   0   0   0
0   0   0   0   0   0   1   0
0   0   0   1   0   0   0   0
0   0   0   0   0   1   0   0
0   0   0   0   0   0   0   1
0   1   0   0   0   0   0   0
0   0   0   0   1   0   0   0
0   0   1   0   0   0   0   0
 */

$obj = new EightQueen(8);

// 获取所有解法的皇后位置
$result = $obj->getResult();

// 输出所有解法的棋盘格子
PrintChessBoard($result);

/**
 * 按照0和1来输出棋盘的格式
 * @param $array
 */
function PrintChessBoard($array)
{
    $k = 0;
    echo '一共有' . count($array) . '种解法：<br /><br />';
    foreach ($array as $v) {
        echo "输出第" . ++$k . "个结果：<br />";
        foreach ($v as $row) {
            for ($i = 0; $i < count($v); $i++) {
                if ($row == $i) {
                    echo "1&nbsp;&nbsp;&nbsp;";
                } else {
                    echo "0&nbsp;&nbsp;&nbsp;";
                }
            }
            echo "<br />";
        }
        echo "<br />";
    }
}

/**
 * 八皇后问题
 */
class EightQueen
{
    // 棋盘格子的范围/皇后的数量
    private $MAX_NUM;

    // 二维数组作为棋盘，二维数组的第一个维度代表横坐标，第二个维度代表纵坐标，并且从0开始。比如chessBoard[3][4]代表的是棋盘第四行第五列格子的状态
    private $ChessBoard;

    // 所有的正确棋牌解法
    private $result = [];

    public function __construct($max_num)
    {
        // 初始化棋盘的格子范围/皇后的数量
        $this->MAX_NUM = $max_num;

        // 小于3x3的棋盘是无解的
        if ($max_num >= 4) {
            // 从第一层开始递归摆放皇后
            $this->settleQueen();
        }
    }

    /**
     * 检查落点是否符合规则（未放置棋子即符合规则）
     * @param $n int 纵坐标即行数
     * @return bool
     */
    private function check($n)
    {
        // 从第一层开始检查，从上到下进行每一层检查
        for ($i = 0; $i < $n; $i++) {
            // 纵向检查、对角线检查
            if ($this->ChessBoard[$i] == $this->ChessBoard[$n] || abs($this->ChessBoard[$i] - $this->ChessBoard[$n]) == ($n - $i)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 从$y层（纵层）开始往下每一层递归摆放皇后，一旦找到一种解法就保存到result中去，然后继续找下一种解法
     * @param $y int 纵坐标
     */
    private function settleQueen($y = 0)
    {
        // 行数超过棋盘的范围，说明已经找到一种解法了，保存到result里面去
        if ($y == $this->MAX_NUM) {
            // 保存正确的棋牌解法
            $this->result[] = $this->ChessBoard;
        }

        // 遍历当前行，从左到右逐一格子进行验证
        for ($i = 0; $i < $this->MAX_NUM; $i++) {
            $this->ChessBoard[$y] = $i;

            // 检查是否符合规则（未放置棋子即符合规则），如果符合，更改元素值并进一步递归
            if ($this->check($y)) {
                // 递归下层
                $this->settleQueen($y + 1);
            }
        }
    }

    /**
     * 输出所有正确棋盘解法
     */
    public function getResult()
    {
        return $this->result;
    }
}