51.52.N皇后——经典问题,八皇后

皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n,返回所有不同的 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]

解释: 4 皇后问题存在两个不同的解法。

51和52的区别仅在于,52只要求结果的数量,51要求求出所有可能的排列方式

解法:递归回溯,逐行的搜索在每一行中,皇后应该出现在哪。每一次尝试在一行中摆放皇后,看能不能摆下这个皇后,如果不能则回溯到上一行重新摆放上一个皇后

如下递归树

(1)在递归树中,从第一行开始检索,占领第一行第一个元素

(2)开始检索第二行,第二行还有0,1,2,3下标四个元素,但是0下标元素跟第一行元素在同一列,1下标元素在第一行元素的对角线上,因此可以减掉0,1两个分支

(3)以此类推,找到所有符合条件的摆放

如何快速判断不合法的情况,如何快速剪枝:

(1)横向:每一次都是在下一行检索,所以不会有行冲突的问题

(2)竖向:用$this->col[$i]表示第 i 列被占用

(3)对角线1:利用$this->dia1[$i]表示第 i 对角线1被占用

如下图所示,下图中显示了每一个坐标的横纵坐标,对角线1总共有2*n-1条

每一条对角线上的坐标可以很明显的看出,可以用横纵坐标相加的值来判断该对角线是否被占用

(4)对角线2:利用$this->dia2[$i]表示第 i 对角线2被占用

另一个方向的对角线如下图所示,下图中显示了每一个坐标的横纵坐标,对角线2总共有2*n-1条

由每一条对角线上的坐标可以得出,可以用横纵坐标相减的值相同,可以用该值来判断该对角线是否被占用

作为一个数组,希望数组可以从0开始,所以可以用横坐标 - 纵坐标 + n - 1,来使数组从0开始

PS:用 path 记录摆放的列位置 ,path自身下标对应行位置

class Solution {
    private $res = [];       //初始化结果数组
    private $n;              //初始化要求n皇后
    private $col,$dia1,$dia2;//列,左对角线,右对角线
    /**
     * @param Integer $n
     * @return String[][]
     */
    function solveNQueens($n) {
        $this->n = $n;          //定义要求几皇后
        if($n == 0) return [];  //初始化判断
        $this->putQueen(0,[]);  //摆放N皇后
        return $this->res;
    }
    /**
     * [尝试在N皇后问题中,摆放第index行的皇后未知]
     * @param  [type] $index [行下标]
     * @param  [type] $path  [暂存的结果路径]
     */
    private function putQueen($index,$path){
        //终止条件:在行下标 = 第n时,已经无法继续下去
        if($index == $this->n){
            $this->res[] = $this->generateBoard($path); //构造N皇后摆放图,压入结果数组中
            return;
        }
        //尝试将第index行的皇后摆放在第i列
        for($i = 0;$in;++$i){
            $dia = $index + $i;                         //该下标对应的dia1的下标
            $revdia = $index - $i + $this->n - 1;       //该下标对应的dia2的下标
            if((empty($this->col[$i]) || $this->col[$i] == 0)               //判断是否在同一列
                &&
                (empty($this->dia1[$dia]) || $this->dia1[$dia] == 0)        //判断是否在同一对角线dia1
                &&
                (empty($this->dia2[$revdia]) || $this->dia2[$revdia] == 0)  //判断是否在同一对角线dia2
                ){
                //满足上方条件,则可以将皇后放在此位置
                $this->col[$i] = 1;                     //标记该列被已经访问
                $this->dia1[$dia] = 1;                  //标记该对角线1被已经访问
                $this->dia2[$revdia] = 1;               //标记该对角线2被已经访问
                $path[] = $i;                           //将该节点放入暂存的结果数组
                $this->putQueen($index+1,$path);        //继续摆放
                array_pop($path);                       //回溯过程
                $this->col[$i] = 0;
                $this->dia1[$dia] = 0;
                $this->dia2[$revdia] = 0;
            }
        }
        return ;
    }
    /**
     * [构造N皇后摆放图]
     * @param  [type] $path [暂存的结果数组中保存的是每一行的皇后摆放的位置]
     */
    private function generateBoard($path){
        $board = [];
        //$path[$i] = $j : $i => 行  $j => 列
        for($i = 0;$in;++$i){
            $str = '';
            for($j = 0;$jn;++$j){
                if($j == $path[$i]){
                    $str .= 'Q';
                }else{
                    $str .= '.';
                }
            }
            $board[$i] = $str;
        }
        return $board;
    }
}

52.N皇后II,不需要构造N皇后图,当摆放完成后,$res 结果+1即可


37.解数独

编写一个程序,通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则:

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 '.' 表示。

一个数独。

答案被标成红色。

Note:

  • 给定的数独序列只包含数字 1-9 和字符 '.' 。
  • 你可以假设给定的数独只有唯一解。
  • 给定数独永远是 9x9 形式的。

人工智能递归回溯解决问题

与八皇后类似,需要标记行列不同,数独需要保证一个小区域内的数字不重复

解法:

(1)初始化已经访问过的行,列,块中的元素

(2)找寻空位置,遍历1-9,判断哪个数字是可以被插入到该位置的,插入并继续下一层递归

(3)满足条件则发挥true,不满足则返回false,一直回溯返回

判断不合法的情况:

(1)横向:$col['第 i 行'][' 数字 '] 是否为1,是则已经被占用了

(2)竖向:$row['第 i 行'][' 数字 '] 是否为1,是则已经被占用了

(3)块中:$row['第 index 块'][' 数字 '] 是否为1,是则已经被占用了

块下标index的定义:floor($i / 3) * 3 + floor($j / 3):

floor($i / 3) 表示纵向已经占领了几行,一行有3个块,则 * 3

floor($j / 3)表示横向已经占领了几块

 

class Solution {
    private $row,$col,$block;        //初始化标记行,列,块已被访问
    /**
     * @param String[][] $board
     * @return NULL
     */
    function solveSudoku(&$board) {
        //初始化标记行,列,块已被访问
        for($i = 0;$i<9;++$i){
            for($j = 0;$j<9;++$j){
                if($board[$i][$j] != '.'){
                    $num = $board[$i][$j];
                    $this->row[$i][$num] = 1;
                    $this->col[$j][$num] = 1;
                    $blockIndex = floor($i / 3) * 3 + floor($j / 3);    //第几块
                    $this->block[$blockIndex][$num] = 1;
                }
            }
        }
        $this->sudu($board,0,0);    //递归回溯解决数独问题
    }
    /**
     * [递归回溯解决数独问题]
     * @param  [type] &$board [数独表]
     * @param  [type] $i      [行下标]
     * @param  [type] $j      [列下标]
     */
    private function sudu(&$board,$i,$j){
        // 找寻空位置
        while ($board[$i][$j] != '.') {
            if (++$j >= 9) {
                $i++;
                $j = 0;
            }
            if ($i >= 9) {
                return true;
            }
        }
        //寻找到一个空位置,尝试摆放数字
        for($num = 1;$num<=9;++$num){
            $blockIndex = floor($i / 3) * 3 + floor($j / 3);                //取得该空位置对应的块
            if((empty($this->row[$i][$num]) || $this->row[$i][$num] == 0)   //判断行中该数字是否被访问
                &&
                (empty($this->col[$j][$num]) || $this->col[$j][$num] == 0)  //判断列中该数字是否被访问
                &&
                (empty($this->block[$blockIndex][$num]) || $this->block[$blockIndex][$num] == 0)  //判断块中是否被访问
                ){
                $this->block[$blockIndex][$num] = 1;    //标记对应块中数字已访问
                $this->col[$j][$num] = 1;               //标记对应列中数字已访问
                $this->row[$i][$num] = 1;               //标记对应行中数字已访问
                $board[$i][$j] = (string)$num;          //把数字添加入
                if($this->sudu($board,$i,$j)){          //继续填写下一个数字
                    return true;
                }else{
                    $this->block[$blockIndex][$num] = 0;//回溯
                    $this->col[$j][$num] = 0;
                    $this->row[$i][$num] = 0;
                    $board[$i][$j] = '.';
                }
            }
        }
        return false;
    }
}

» 版权所有:YaoLei's Blog » LeetCode(51.52.N皇后 && 37.解数独) PHP解法 回溯递归
» 本文链接:http://www.yaolei.info/archives/551