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

Effective methods to prevent session fixed attacks include: 1. Regenerate the session ID after the user logs in; 2. Use a secure session ID generation algorithm; 3. Implement the session timeout mechanism; 4. Encrypt session data using HTTPS. These measures can ensure that the application is indestructible when facing session fixed attacks.

Implementing session-free authentication can be achieved by using JSONWebTokens (JWT), a token-based authentication system where all necessary information is stored in the token without server-side session storage. 1) Use JWT to generate and verify tokens, 2) Ensure that HTTPS is used to prevent tokens from being intercepted, 3) Securely store tokens on the client side, 4) Verify tokens on the server side to prevent tampering, 5) Implement token revocation mechanisms, such as using short-term access tokens and long-term refresh tokens.

The security risks of PHP sessions mainly include session hijacking, session fixation, session prediction and session poisoning. 1. Session hijacking can be prevented by using HTTPS and protecting cookies. 2. Session fixation can be avoided by regenerating the session ID before the user logs in. 3. Session prediction needs to ensure the randomness and unpredictability of session IDs. 4. Session poisoning can be prevented by verifying and filtering session data.

To destroy a PHP session, you need to start the session first, then clear the data and destroy the session file. 1. Use session_start() to start the session. 2. Use session_unset() to clear the session data. 3. Finally, use session_destroy() to destroy the session file to ensure data security and resource release.

How to change the default session saving path of PHP? It can be achieved through the following steps: use session_save_path('/var/www/sessions');session_start(); in PHP scripts to set the session saving path. Set session.save_path="/var/www/sessions" in the php.ini file to change the session saving path globally. Use Memcached or Redis to store session data, such as ini_set('session.save_handler','memcached'); ini_set(

TomodifydatainaPHPsession,startthesessionwithsession_start(),thenuse$_SESSIONtoset,modify,orremovevariables.1)Startthesession.2)Setormodifysessionvariablesusing$_SESSION.3)Removevariableswithunset().4)Clearallvariableswithsession_unset().5)Destroythe

Arrays can be stored in PHP sessions. 1. Start the session and use session_start(). 2. Create an array and store it in $_SESSION. 3. Retrieve the array through $_SESSION. 4. Optimize session data to improve performance.

PHP session garbage collection is triggered through a probability mechanism to clean up expired session data. 1) Set the trigger probability and session life cycle in the configuration file; 2) You can use cron tasks to optimize high-load applications; 3) You need to balance the garbage collection frequency and performance to avoid data loss.


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

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

Hot Article

Hot Tools

SublimeText3 English version
Recommended: Win version, supports code prompts!

ZendStudio 13.5.1 Mac
Powerful PHP integrated development environment

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.

SublimeText3 Chinese version
Chinese version, very easy to use

EditPlus Chinese cracked version
Small size, syntax highlighting, does not support code prompt function
