LeetCode（51.52.N皇后 && 37.解数独） PHP解法 回溯递归
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;$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-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 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;
}
}