使用PHP怎么实现一个八皇后算法-创新互联
使用PHP怎么实现一个八皇后算法？相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。
PHP代码实现：
N = $N;
$this->chessboard = array();
for ($i=0; $i < $N; $i++) {
for ($j=0; $j < $N; $j++) {
$this->chessboard[$i][$j] = 0;
}
}
$this->has_set_x = array();
$this->has_set_y = array();
$this->has_set_site = array();
}
// 获取排列
public function getPermutation($is_get_on = true) { // is_get_on 是否获取一种排列 true:是 false:获取所有排列
$current_n = 0; // 当前设置第几个皇后
$start_x = 0; // 当前的x坐标 从x开始放置尝试
$permutation_array = array(); // 全部皇后放置成功的排列数组
while ($current_n < $this->N && $current_n >= 0) {
$site_result = $this->setQueenSite($current_n, $start_x); // 设置皇后位置
if($site_result == true && $current_n + 1 >= $this->N) { // 如果最后的皇后位置放置成功则记录信息
$permutation_array[] = array_merge($this->has_set_site, array(array('x' => $site_result['x'], 'y' => $site_result['y'])));
if($is_get_on == false) { // 如果是获取所有排列，则设置当前放置失败，让程序回溯继续找到其他排列
$site_result = false;
}
}
if($site_result == true) {
$this->chessboard[$site_result['x']][$site_result['y']] = 1;
$this->has_set_x[] = $site_result['x'];
$this->has_set_y[] = $site_result['y'];
$this->has_set_site[] = array('x' => $site_result['x'], 'y' => $site_result['y']);
$current_n++; // 皇后位置放置成功，继续设置下一个皇后，重置下一个皇后的x坐标从0开始
$start_x = 0;
}else {
// 当前皇后找不到放置的位置，则需要回溯到上一步
$previous_site = array_pop($this->has_set_site); // 找到上一步皇后的位置
if(!empty($previous_site)) {
$start_x = $previous_site['x'] + 1; // 让上一步的皇后的x坐标+1继续尝试放置
$this->deleteArrayValue($this->has_set_x, $previous_site['x']);
$this->deleteArrayValue($this->has_set_y, $previous_site['y']);
$this->chessboard[$previous_site['x']][$previous_site['y']] = 0;
}
$current_n--; // 回溯到上一步，即让一个皇后x坐标+1继续尝试放置
}
}
return $permutation_array;
}
// 设置皇后位置
public function setQueenSite($n, $start_x) {
$start_y = $n;
if($start_x >= $this->N) return false;
$check_result = $this->checkQueenSite($start_x, $start_y); // 检查当前是否可放置
if($check_result == true) {
return array('x' => $start_x, 'y' => $start_y);
}else { // 不可放置，则x坐标+1，继续尝试
$start_x++;
return $this->setQueenSite($n, $start_x);
}
}
// 检查皇后位置是否正确
public function checkQueenSite($x, $y) {
// 判断当前坐标的横、纵、斜线是否存在已经放置的皇后
if(in_array($x, $this->has_set_x)) return false;
if(in_array($y, $this->has_set_y)) return false;
$operate_array = array(
array('operate_x' => '+', 'operate_y' => '+'),
array('operate_x' => '-', 'operate_y' => '-'),
array('operate_x' => '+', 'operate_y' => '-'),
array('operate_x' => '-', 'operate_y' => '+')
);
foreach ($operate_array as $key => $value) {
$diagonal_x = $x;
$diagonal_y = $y;
while (true) {
eval("\$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怎么实现一个八皇后算法的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注创新互联行业资讯频道，感谢各位的阅读！
网页名称：使用PHP怎么实现一个八皇后算法-创新互联
URL地址：http://scjbc.cn/article/shoii.html
