当前位置:首页 > PHP教程 > php高级应用 > 列表

PHP实现八皇后算法

发布:smiling 来源: PHP粉丝网  添加日期:2021-11-21 17:26:23 浏览: 评论:0 

回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

这边先以4皇后来解释解决步骤:

详细说明

在第一行有四种可能,选择第一个位置放上皇后

PHP八皇后算法

第二行原本可以有四种可能摆放,但是第一第二个已经和第一行的皇后冲突了,因此只剩下第三第四个格子了,先选择第三个格子

PHP八皇后算法

接下来是第三行,根据规则可以看出,第三行已经没有位置放了,因为都跟第一第二行的皇后冲突,此时返回到第二行第四个

PHP八皇后算法

继续来到第三行,发现只有第二个满足条件

PHP八皇后算法

然后发现第四行已经不能放了,只能继续返回,返回到第一行,开始下一种可能

PHP八皇后算法

按照 1-5 的步骤,可以找到下面的其中一种解法

PHP八皇后算法

总而言之,回溯法就是开始一路到底,碰到南墙了就返回走另外一条路,有点像穷举法那样走遍所有的路。

PHP代码实现:

  1. <?php 
  2.    
  3. class Backtracking { 
  4.    
  5.  protected $chessboard;  // 棋盘 二维数组 表示坐标轴 
  6.  protected $N;      // N表示几皇后 
  7.  protected $has_set_x;  // 已经设置的x坐标数组 已经设置的x坐标就不能重复了,用于检查坐标是否可用 
  8.  protected $has_set_y;  // 已经设置的y坐标数组 已经设置的y坐标就不能重复了,用于检查坐标是否可用 
  9.  protected $has_set_site// 已经设置的点 
  10.    
  11.  function __construct($N) { 
  12.  // 初始化数据 
  13.  $this->N = $N
  14.  $this->chessboard = array(); 
  15.  for ($i=0; $i < $N$i++) {  
  16.   for ($j=0; $j < $N$j++) {  
  17.   $this->chessboard[$i][$j] = 0; 
  18.   } 
  19.  } 
  20.  $this->has_set_x = array(); 
  21.  $this->has_set_y = array(); 
  22.  $this->has_set_site = array(); 
  23.  } 
  24.    
  25.  // 获取排列 
  26.  public function getPermutation($is_get_on = true) { // is_get_on 是否获取一种排列 true:是 false:获取所有排列 
  27.  $current_n = 0; // 当前设置第几个皇后 
  28.  $start_x = 0;  // 当前的x坐标 从x开始放置尝试 
  29.  $permutation_array = array(); // 全部皇后放置成功的排列数组 
  30.  while ($current_n < $this->N && $current_n >= 0) { 
  31.   $site_result = $this->setQueenSite($current_n$start_x); // 设置皇后位置 
  32.   if($site_result == true && $current_n + 1 >= $this->N) { // 如果最后的皇后位置放置成功则记录信息 
  33.   $permutation_array[] = array_merge($this->has_set_site, array(array('x' => $site_result['x'], 'y' => $site_result['y']))); 
  34.   if($is_get_on == false) { // 如果是获取所有排列,则设置当前放置失败,让程序回溯继续找到其他排列 
  35.    $site_result = false; 
  36.   } 
  37.   } 
  38.   if($site_result == true) { 
  39.   $this->chessboard[$site_result['x']][$site_result['y']] = 1; 
  40.   $this->has_set_x[] = $site_result['x']; 
  41.   $this->has_set_y[] = $site_result['y']; 
  42.   $this->has_set_site[] = array('x' => $site_result['x'], 'y' => $site_result['y']); 
  43.   $current_n++; // 皇后位置放置成功,继续设置下一个皇后,重置下一个皇后的x坐标从0开始 
  44.   $start_x = 0; 
  45.   }else { 
  46.   // 当前皇后找不到放置的位置,则需要回溯到上一步 
  47.   $previous_site = array_pop($this->has_set_site); // 找到上一步皇后的位置 
  48.   if(!emptyempty($previous_site)) { 
  49.    $start_x = $previous_site['x'] + 1; // 让上一步的皇后的x坐标+1继续尝试放置 
  50.    $this->deleteArrayValue($this->has_set_x, $previous_site['x']); 
  51.    $this->deleteArrayValue($this->has_set_y, $previous_site['y']); 
  52.    $this->chessboard[$previous_site['x']][$previous_site['y']] = 0; 
  53.   } 
  54.   $current_n--; // 回溯到上一步,即让一个皇后x坐标+1继续尝试放置 
  55.   } 
  56.  } 
  57.  return $permutation_array
  58.  } 
  59.    
  60.  // 设置皇后位置 
  61.  public function setQueenSite($n$start_x) { 
  62.  $start_y = $n
  63.  if($start_x >= $this->N) return false; 
  64.  $check_result = $this->checkQueenSite($start_x$start_y); // 检查当前是否可放置 
  65.  if($check_result == true) { 
  66.   return array('x' => $start_x'y' => $start_y); 
  67.  }else { // 不可放置,则x坐标+1,继续尝试 
  68.   $start_x++; 
  69.   return $this->setQueenSite($n$start_x); 
  70.  } 
  71.  } 
  72.    
  73.  // 检查皇后位置是否正确 
  74.  public function checkQueenSite($x$y) { 
  75.  // 判断当前坐标的横、纵、斜线是否存在已经放置的皇后 
  76.  if(in_array($x$this->has_set_x)) return false; 
  77.  if(in_array($y$this->has_set_y)) return false; 
  78.  $operate_array = array
  79.   array('operate_x' => '+''operate_y' => '+'), 
  80.   array('operate_x' => '-''operate_y' => '-'), 
  81.   array('operate_x' => '+''operate_y' => '-'), 
  82.   array('operate_x' => '-''operate_y' => '+'
  83.  ); 
  84.  foreach ($operate_array as $key => $value) { 
  85.   $diagonal_x = $x
  86.   $diagonal_y = $y
  87.   while (true) { 
  88.   eval("\$diagonal_x=$diagonal_x {$value['operate_x']} 1;"); 
  89.   eval("\$diagonal_y=$diagonal_y {$value['operate_y']} 1;"); 
  90.   if($diagonal_x >= $this->N || $diagonal_y >= $this->N || $diagonal_x < 0 || $diagonal_y < 0) break
  91.   if($this->chessboard[$diagonal_x][$diagonal_y] == 1) return false; 
  92.   } 
  93.  } 
  94.  return true; 
  95.  } 
  96.    
  97.  // 删除数组元素 
  98.  public function deleteArrayValue(&$array$value) { 
  99.  $delete_key = array_search($value$array); 
  100.  array_splice($array$delete_key, 1); 
  101.  } 
  102.    
  103.    
  104. $N = 8; // 8表示获取8皇后的排列组合 
  105. $backtracking = new Backtracking($N); 
  106. $permutations = $backtracking->getPermutation(false); 
  107. var_dump($permutations); // 输出92种排列

Tags: PHP八皇后算法

分享到: