search

史上最详细的八个皇后算法解析【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);?>

四.运行结果


..........

.........






















Statement
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
Explain the concept of a PHP session in simple terms.Explain the concept of a PHP session in simple terms.Apr 26, 2025 am 12:09 AM

PHPsessionstrackuserdataacrossmultiplepagerequestsusingauniqueIDstoredinacookie.Here'showtomanagethemeffectively:1)Startasessionwithsession_start()andstoredatain$_SESSION.2)RegeneratethesessionIDafterloginwithsession_regenerate_id(true)topreventsessi

How do you loop through all the values stored in a PHP session?How do you loop through all the values stored in a PHP session?Apr 26, 2025 am 12:06 AM

In PHP, iterating through session data can be achieved through the following steps: 1. Start the session using session_start(). 2. Iterate through foreach loop through all key-value pairs in the $_SESSION array. 3. When processing complex data structures, use is_array() or is_object() functions and use print_r() to output detailed information. 4. When optimizing traversal, paging can be used to avoid processing large amounts of data at one time. This will help you manage and use PHP session data more efficiently in your actual project.

Explain how to use sessions for user authentication.Explain how to use sessions for user authentication.Apr 26, 2025 am 12:04 AM

The session realizes user authentication through the server-side state management mechanism. 1) Session creation and generation of unique IDs, 2) IDs are passed through cookies, 3) Server stores and accesses session data through IDs, 4) User authentication and status management are realized, improving application security and user experience.

Give an example of how to store a user's name in a PHP session.Give an example of how to store a user's name in a PHP session.Apr 26, 2025 am 12:03 AM

Tostoreauser'snameinaPHPsession,startthesessionwithsession_start(),thenassignthenameto$_SESSION['username'].1)Usesession_start()toinitializethesession.2)Assigntheuser'snameto$_SESSION['username'].Thisallowsyoutoaccessthenameacrossmultiplepages,enhanc

What are some common problems that can cause PHP sessions to fail?What are some common problems that can cause PHP sessions to fail?Apr 25, 2025 am 12:16 AM

Reasons for PHPSession failure include configuration errors, cookie issues, and session expiration. 1. Configuration error: Check and set the correct session.save_path. 2.Cookie problem: Make sure the cookie is set correctly. 3.Session expires: Adjust session.gc_maxlifetime value to extend session time.

How do you debug session-related issues in PHP?How do you debug session-related issues in PHP?Apr 25, 2025 am 12:12 AM

Methods to debug session problems in PHP include: 1. Check whether the session is started correctly; 2. Verify the delivery of the session ID; 3. Check the storage and reading of session data; 4. Check the server configuration. By outputting session ID and data, viewing session file content, etc., you can effectively diagnose and solve session-related problems.

What happens if session_start() is called multiple times?What happens if session_start() is called multiple times?Apr 25, 2025 am 12:06 AM

Multiple calls to session_start() will result in warning messages and possible data overwrites. 1) PHP will issue a warning, prompting that the session has been started. 2) It may cause unexpected overwriting of session data. 3) Use session_status() to check the session status to avoid repeated calls.

How do you configure the session lifetime in PHP?How do you configure the session lifetime in PHP?Apr 25, 2025 am 12:05 AM

Configuring the session lifecycle in PHP can be achieved by setting session.gc_maxlifetime and session.cookie_lifetime. 1) session.gc_maxlifetime controls the survival time of server-side session data, 2) session.cookie_lifetime controls the life cycle of client cookies. When set to 0, the cookie expires when the browser is closed.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

mPDF

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools