当前位置:Gxlcms > PHP教程 > 四.运行结果

四.运行结果

时间:2021-07-01 10:21:17 帮助过:13人阅读

史上最详细的八个皇后算法解析【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,表示该列未占用。

代码如下:

column[$i]=1;        }        for($i=1;$i<=(2*8);$i++)        $this->rup[$i]=$this->lup[$i]=1;    }    public function backtrack($i){//i从上往下        if($i>8){            $this->showAnswer();        }else{        for($j=1;$j<=8;$j++){            //从左往右横向                       if(($this->column[$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;$x<=8;$x++){ if($this->queen[$y]==$x){ print("Q"); }else{ print(" * "); } } print("
"); } print("
"); }}$queen=new Queen();$queen->backtrack(1);?>

四.运行结果


..........

.........






















人气教程排行