Table of Contents
一.题目解析:
二.数学建模
三.程序实现
四.运行结果

四.运行结果

Jun 13, 2016 pm 12:19 PM
gt quot this

史上最详细的八个皇后算法解析【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-&gt;lup[$i]=1;    }    public function backtrack($i){//i从上往下        if($i&gt;8){            $this-&gt;showAnswer();        }else{        for($j=1;$jcolumn[$j]==1)&amp;&amp;($this-&gt;rup[$i+$j]==1)&amp;&amp;($this-&gt;lup[$i-$j+8]==1)){                         $this-&gt;queen[$i]=$j;                //设定为占用                $this-&gt;column[$j]=$this-&gt;rup[$i+$j]=$this-&gt;lup[$i-$j+8]=0;                $this-&gt;backtrack($i+1);                $this-&gt;column[$j]=$this-&gt;rup[$i+$j]=$this-&gt;lup[$i-$j+8]=1;            }          }       }    }         protected function showAnswer(){        $this-&gt;num++;        print("解答");        print($this-&gt;num);        echo "<br>";        for($y=1;$yqueen[$y]==$x){                    print("Q");                }else{                    print(" * ");                }            }            print("<br>");         }        print("<br>");     }}$queen=new Queen();$queen-&gt;backtrack(1);?&gt;
Copy after login

四.运行结果


..........

.........






















Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot Article

Hot Article

Hot Article Tags

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

What are the differences between Huawei GT3 Pro and GT4? What are the differences between Huawei GT3 Pro and GT4? Dec 29, 2023 pm 02:27 PM

What are the differences between Huawei GT3 Pro and GT4?

Fix: Snipping tool not working in Windows 11 Fix: Snipping tool not working in Windows 11 Aug 24, 2023 am 09:48 AM

Fix: Snipping tool not working in Windows 11

How to Fix Can't Connect to App Store Error on iPhone How to Fix Can't Connect to App Store Error on iPhone Jul 29, 2023 am 08:22 AM

How to Fix Can't Connect to App Store Error on iPhone

php提交表单通过后,弹出的对话框怎样在当前页弹出,该如何解决 php提交表单通过后,弹出的对话框怎样在当前页弹出,该如何解决 Jun 13, 2016 am 10:23 AM

php提交表单通过后,弹出的对话框怎样在当前页弹出,该如何解决

Is watch4pro better or gt? Is watch4pro better or gt? Sep 26, 2023 pm 02:45 PM

Is watch4pro better or gt?

How to use this method in Java How to use this method in Java Apr 18, 2023 pm 01:58 PM

How to use this method in Java

An article that understands this point and catches up with 70% of front-end people An article that understands this point and catches up with 70% of front-end people Sep 06, 2022 pm 05:03 PM

An article that understands this point and catches up with 70% of front-end people

How to optimize iPad battery life with iPadOS 17.4 How to optimize iPad battery life with iPadOS 17.4 Mar 21, 2024 pm 10:31 PM

How to optimize iPad battery life with iPadOS 17.4

See all articles