目录

51.52.N皇后

37.解数独

---

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

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

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

给定一个整数 n，返回所有不同的 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;$i<$this->n;++$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;$i<$this->n;++$i){
            $str = '';
            for($j = 0;$j<$this->n;++$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;
    }
}