八皇后问题解法

什么事八皇后问题

国际象棋中的皇后，可以横向、纵向、斜向移动。如何在一个8X8的棋盘上放置8个皇后，使得任意两个皇后都不在同一条横线、竖线、斜线方向上？

解题思路

从第一排第一个位置放置第一个皇后,然后开始第二排,第二排第一个被封锁,第二个也被封锁,第三个可用,开始第三排,一排排循环向下,一旦遇到整排不可用,则表示前一排摆放错误,将上一排位置向后移动一个.这种向下递归搜索是否有解,失败则回退到循环换别的方式的解题方式就是递归回溯法,常见的一种算法思路,现在看一下递归回溯法如何解八皇后问题.

PHP递归回溯法解八皇后问题

Talk is cheap,show you my code!

<?php

class Queen8
{
    /**
     * 棋盘大小
     */
    const MAX_NUM = 8;
    /**
     * @var array 二维数组模拟棋盘
     */
    public $chess_board;

    /**
     * 构造棋盘
     * Queen8 constructor.
     */
    public function __construct()
    {
        for ($i = 0; $i < self::MAX_NUM; $i++) {
            for ($j = 0; $j < self::MAX_NUM; $j++) {
                $this->chess_board[$i][$j] = 0;
            }
        }
    }

    /**
     * 检查对应点能否放皇后
     * @param int $x
     * @param int $y
     * @return bool
     */
    public function check(int $x, int $y)
    {
        for ($i = 0; $i < $y; $i++) {
            // 轴检查竖
            if (1 == $this->chess_board[$x][$i]) {
                return false;
            }
            // 检查左斜方向,只需检查上侧
            if ($x-1-$i >= 0 && 1 == $this->chess_board[$x-1-$i][$y-1-$i]) {
                return false;
            }
            // 检查右斜方向,只需检查上侧
            if ($x+1+$i < self::MAX_NUM && 1 == $this->chess_board[$x+1+$i][$y-1-$i]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 从上下到放皇后
     * @param int $y
     * @return bool
     */
    public function settleQueen(int $y)
    {
        // 行数超过八行则表示已经全部摆放完毕
        if ($y == self::MAX_NUM) {
            return true;
        }

        for ($i = 0; $i < self::MAX_NUM; $i++) {
            for ($x = 0; $x < self::MAX_NUM; $x++) {
                $this->chess_board[$x][$y] = 0;
            }
            if ($this->check($i, $y)) {
                $this->chess_board[$i][$y] = 1;
                if ($this->settleQueen($y + 1)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 打印结果
     */
    public function printChessBoard()
    {
        foreach ($this->chess_board as $item) {
            foreach ($item as $point) {
                echo $point;
            }
            echo PHP_EOL;
        }
    }

}
$queen8 = new Queen8();
$queen8->settleQueen(0);
$queen8->printChessBoard();