史上最详细的八个皇后算法解析【php版本】
题目：
八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后。为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
一.题目解析：
每个可以放置的位置需满足的要求：
1）所在行都没有放置过；
2）所在列都没有放置过；
3）从左上到右下的对角线没有放置过；
4）从右上到左下的对角线没有放置过。
二.数学建模
1）建立坐标系，
2）设放置坐标为（a,b）,则需要满足下面是数学关系。
1.行row[a]=1（表示第a行没有放置过，0则表示第a行已被放置）；
2.列col[b]=1（表示第b列没有放置过，0则表示第b列已被放置）；
对角线的要做一下运算：
观察可知，设过（a,b）的曲线上还有点（x,y）,
3.从左上到右下的对角线（设为主对角线）斜率为-1:
则有(y-b)/(x-a)=-1,整理得到如下关系：y+x=a+b。
因此可以用a+b来标记过（a,b） 的主对角线，a+b的范围是[2,16],即用2-16的数字标记从过（1,1）到过（8,8）这15条对角线;
4.从右上到左下的对角线（设为次对角线）斜率为1:
则有(y-b)/(x-a)=1,整理得到如下关系：x-y=a-b;
因此可以用a-b来标记过（a,b） 的次对角线，a-b的范围是[-7,7];
3）放置过程
从第1摆至第8行，每行摆一个，则第二步的第一条件可以忽略（肯定不同行）。
下面假设一下摆放步骤，也就是回溯法的一个例子：
Q * * * * * * *
* * Q * * * * *
* * * * Q * * *
* Q * * * * * *
* * * * * * * Q
* * * * * * * *
* * * * * * * *
* * * * * * * *
从第一行的(1,1)开始摆，第二行检测第二步的三个条件，假设放置到(2,3),第三行放置到（3,5），第四行(4,2)，第五行(5,8)发现第五行已经找不到满足条件的坐标了，这时候就要退回第四行，发现第四行已经到行尾了，没有位置可选了，这时候就得退回第3行，在第三行找到（4,7）符合条件，又开始了往下摆放的过程，直到到达第八行找到八个可以摆放的位置，则为一个解。
三.程序实现
注：为了便于程序中用数组对对角线的标注，针对第i行第j列的坐标，其改坐标的主对角线为$this->rup[$i+$j]=1，表示该对角线未占用，次对角线为$this->lup[$i-$j+8]=1（数组的下标不能为负，而$i-$j可能为负），表示该对角线未占用，$this->column[$j]=1，表示该列未占用。
代码如下：
<?php/*** function：解决八个皇后的问题* author：xiaojun* date：2015-5-16*/class Queen { private $column= array();//存放列是否占有标记，0为占有 private $rup= array();//存放主对角线是否占有，0为占有 private $lup= array();//存放次对角线是否占有，0为占有 private $queen= array();//存放解中皇后的位置 private $num; //解的编号 function __construct() { for($i=1;$icolumn[$i]=1; } for($i=1;$irup[$i]=$this->lup[$i]=1; } public function backtrack($i){//i从上往下 if($i>8){ $this->showAnswer(); }else{ for($j=1;$jcolumn[$j]==1)&&($this->rup[$i+$j]==1)&&($this->lup[$i-$j+8]==1)){ $this->queen[$i]=$j; //设定为占用 $this->column[$j]=$this->rup[$i+$j]=$this->lup[$i-$j+8]=0; $this->backtrack($i+1); $this->column[$j]=$this->rup[$i+$j]=$this->lup[$i-$j+8]=1; } } } } protected function showAnswer(){ $this->num++; print("解答"); print($this->num); echo "
"; for($y=1;$y<=8;$y++){ for($x=1;$xqueen[$y]==$x){ print("Q"); }else{ print(" * "); } } print("
"); } print("
"); }}$queen=new Queen();$queen->backtrack(1);?>
四.运行结果
本文来源gao@daima#com搞(%代@#码@网&搞gaodaima代码
……….
………
转载请注明原文链接：四.运行结果
