PHP实现八皇后算法

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

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

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

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

详细说明

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

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

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

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

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

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

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

PHP代码实现:

<?php

class Backtracking {

 protected $chessboard;  // 棋盘 二维数组 表示坐标轴
 protected $N;      // N表示几皇后
 protected $has_set_x;  // 已经设置的x坐标数组 已经设置的x坐标就不能重复了,用于检查坐标是否可用
 protected $has_set_y;  // 已经设置的y坐标数组 已经设置的y坐标就不能重复了,用于检查坐标是否可用
 protected $has_set_site; // 已经设置的点

 function __construct($N) {
 // 初始化数据
 $this->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种排列

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • PHP正则表达式的效率 回溯与固化分组

    先来看下问题. 字符串 复制代码 代码如下: $str = '<script>123456</script>'; 正则表达式为 复制代码 代码如下: $strRegex1 = '%<script>.+<\/script>%'; $strRegex2 = '%<script>.+?<\/script>%'; $strRegex3 = '%<script>(?:(?!<\/script>).)+<\/scri

  • PHP基于回溯算法解决n皇后问题的方法示例

    本文实例讲述了PHP基于回溯算法解决n皇后问题的方法.分享给大家供大家参考,具体如下: 这里对于n皇后问题就不做太多的介绍,相关的介绍与算法分析可参考前面一篇C++基于回溯法解决八皇后问题. 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向

  • PHP实现的回溯算法示例

    本文实例讲述了PHP实现的回溯算法.分享给大家供大家参考,具体如下: 问题: 一头大牛驼2袋大米,一头中牛驼一袋大米,两头小牛驼一袋大米,请问100袋大米需要多少头大牛,多少头中牛,多少头小牛? 实现代码: <?php /* * k = 2x + y + 1/2z 取值范围 * 0 <= x <= 1/2k * 0 <= y <= k * 0 <= z < = 2k * x,y,z最大值 2k */ $daMi = 100; $result = array();

  • PHP实现基于回溯法求解迷宫问题的方法详解

    本文实例讲述了PHP实现基于回溯法求解迷宫问题的方法.分享给大家供大家参考,具体如下: 引言 最近在leetcode上看了些算法题,有些看着很简单的很常用的东西,竟然一下子想不出来怎么求解,比如说:实现sqrt函数,求数组的排列.如果高数学的不好,这些看似简单的问题,第一次碰到也会感觉很难求解,当然了,今天要说的是这样一个问题,求解迷宫的所有解,这个问题的求解用到了回溯法的思想,不了解这个思想的话,很多稍微复杂点的问题都很难解了. 问题描述 这个问题是在实在瞎逛的时候碰到的,具体哪里记不太清了.

  • PHP 正则表达式效率 贪婪、非贪婪与回溯分析(推荐)

    先扫盲一下什么是正则表达式的贪婪,什么是非贪婪?或者说什么是匹配优先量词,什么是忽略优先量词? 好吧,我也不知道概念是什么,来举个例子吧. 某同学想过滤之间的内容,那是这么写正则以及程序的. $str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪 看起来,好像没什么问题,其实则不然.若 $str = '<script<script>alert(document.cookie)</script&

  • PHP回溯法解决0-1背包问题实例分析

    本文实例讲述了PHP回溯法解决0-1背包问题的方法.分享给大家供大家参考.具体分析如下: 这段代码是根据<软件设计师>教程的伪代码写的: 最麻烦的不是伪代码改成php,而是数组下标从0开始,及相应的下标判断问题: 带着调试输出一块写上 <?php $v_arr = array(11,21,31,33,43,53,55,65); $w_arr = array(1,11,21,23,33,43,45,55); $n = count($w_arr ); //测试输出 var_dump(bkna

  • PHP实现八皇后算法

    回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就"回溯"返回,尝试别的路径.回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标.但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为"回溯点". 回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试. 八皇后问题,是一个古老而著名的问题,是回溯算法

  • C语言回溯法解八皇后问题(八皇后算法)

    八皇后问题(N皇后问题)的回溯法求解 一.问题描述 在一个国际象棋棋盘上放置八个皇后,使得任何两个皇后之间不相互攻击,求出所有的布棋方法,并推广到N皇后情况. 二.参考资料 啥文字都不用看,B站上有个非常详细的动画视频解说,上链接!!! Click Here! 三.源代码 #include<iostream> #include<vector> #include<string> using namespace std; void put_queen(int x, int

  • ios使用OC写算法之递归实现八皇后

    八皇后算法介绍 知道国际象棋的朋友们应该知道里面的皇后是最厉害的角色,她可以上下左右通吃,和中国象棋里面的车(ju 一声)一样,但是她比车更强大,她可以在斜线上也做到通吃,而我们的八皇后问题其实简单来说就是如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后 八皇后算法思路解析 既然任意一个皇后都无法吃掉其他的皇后,也就是说任两个皇后都不能处于同一条横行.纵行或斜线上,我们将棋盘当做一个二维数组,将皇后的位置标记为1 而其他位置默认都为0,这样我们就可以使用

  • Java基于循环递归回溯实现八皇后问题算法示例

    本文实例讲述了Java基于循环递归回溯实现八皇后问题.分享给大家供大家参考,具体如下: 运行效果图如下: 棋盘接口 /** * 棋盘接口 * @author Administrator * */ public interface Piece { abstract boolean isRow(int line); abstract boolean isCol(int line,int col); } 棋盘类: /** * 棋盘 * @author Administrator * */ public

  • C语言基于回溯算法解决八皇后问题的方法

    本文实例讲述了C语言基于回溯算法解决八皇后问题的方法.分享给大家供大家参考,具体如下: 问题描述: 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例:在8X8格的国际象棋棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 问题求解: 采用回溯算法,即从第一行开始,依次探查可以放置皇后的位置,若找到,则放置皇后,开始探查下一行:若该行没有位置可以放置皇后,则回溯至上一行,清除该行放置皇后的信息,从该行原本放置皇后的下一个位置开始探查可

  • JavaScript解八皇后问题的方法总结

    关于八皇后问题的 JavaScript 解法,总觉得是需要学习一下算法的,哪天要用到的时候发现真不会就尴尬了 背景 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上 八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为 n×n ,而皇后个数也变成n .当且仅当n = 1或n ≥ 4时问题有解 盲目的枚举算法 通过N重循环,枚举满足约束条件的解(

  • C++基于回溯法解决八皇后问题示例

    本文实例讲述了C++基于回溯法解决八皇后问题的方法.分享给大家供大家参考,具体如下: 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯:否则,进入该子树,继续按深度优先策略搜索. 回溯法指导思想--走不通,就掉头.设计过程:确

  • C++实现八皇后问题的方法

    本文实例展示了C++实现八皇后问题的方法,是数据结构与算法中非常经典的一个算法.分享给大家供大家参考之用.具体方法如下: 一般在八皇后问题中,我们要求解的是一个8*8的国际象棋棋盘中,放下8个皇后且互相不能攻击的排列总数.皇后的攻击范围为整行,整列,以及其斜对角线. 由于皇后的攻击范围特性,注定我们每行只能放下一个皇后,于是我们要做的只是逐行放下皇后.八皇后问题是回溯法的典型问题.这里我们用的方法很简单: 从第一行开始逐个检索安全位置摆放皇后,一旦有安全位置则考虑下一行的安全位置.如果发现某行没

  • Python解决八皇后问题示例

    本文实例讲述了Python解决八皇后问题的方法.分享给大家供大家参考,具体如下: 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上.八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n1×n1,而皇后个数也变成n2.而且仅当 n2 = 1 或 n1 ≥ 3 时问题有解. 这是一个典型的回溯算法,我们可以将问题进行分解: 首先,我们要想到某种方

  • Python八皇后问题解答过程详解

    最近看Python看得都不用tab键了,哈哈.今天看了一个经典问题--八皇后问题,说实话,以前学C.C++的时候有这个问题,但是当时不爱学,没搞会,后来算法课上又碰到,只是学会了思想,应该是学回溯法的时候碰到的.八皇后问题是说要在一个棋盘上放置8个皇后,但是不能发生战争,皇后们都小心眼,都爱争风吃醋,如果有人和自己在一条线上(水平.垂直.对角线)就会引发撕13大战,所以我们就是要妥当的安排8位娘娘,以保后宫太平. 言归正传,首先,我们得想好解决方案怎么表示,这种事首先想到列表,当然规模小的话用元

随机推荐