四.运行结果

WBOY

Libérer： 2016-06-13 12:19:53

original

1002 Les gens l'ont consulté

史上最详细的八个皇后算法解析【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;$i<=8;$i++){            $this->column[$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 "<br>";        for($y=1;$yqueen[$y]==$x){                    print("Q");                }else{                    print(" * ");                }            }            print("<br>");         }        print("<br>");     }}$queen=new Queen();$queen->backtrack(1);?>

Copier après la connexion

四.运行结果

..........

.........