回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
这边先以4皇后来解释解决步骤：
详细说明
在第一行有四种可能，选择第一个位置放上皇后
第二行原本可以有四种可能摆放，但是第一第二个已经和第一行的皇后冲突了，因此只剩下第三第四个格子了，先选择第三个格子
接下来是第三行，根据规则可以看出，第三行已经没有位置放了，因为都跟第一第二行的皇后冲突，此时返回到第二行第四个
继续来到第三行，发现只有第二个满足条件
然后发现第四行已经不能放了，只能继续返回，返回到第一行，开始下一种可能
按照 1-5 的步骤，可以找到下面的其中一种解法
总而言之，回溯法就是开始一路到底，碰到南墙了就返回走另外一条路，有点像穷举法那样走遍所有的路。
PHP代码实现：
<"\$diagonal_x=$diagonal_x {$value['operate_x']} 1;");
eval("\$diagonal_y=$diagonal_y {$value['operate_y']} 1;");
if($diagonal_x >= $this->N || $diagonal_y >= $this->N || $diagonal_x < 0 || $diagonal_y < 0) break;
if($this->chessboard[$diagonal_x][$diagonal_y] == 1) return false;
}
}
return true;
}
// 删除数组元素
public function deleteArrayValue(&$array, $value) {
$delete_key = array_search($value, $array);
array_splice($array, $delete_key, 1);
}
}
$N = 8; // 8表示获取8皇后的排列组合
$backtracking = new Backtracking($N);
$permutations = $backtracking->getPermutation(false);
var_dump($permutations); // 输出92种排列
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。
标签：
php,八皇后算法
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！
如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
桃源资源网 Design By www.nqtax.com
暂无“PHP实现八皇后算法”评论...