This article describes the method of PHP solving the n-Queen problem based on backtracking algorithm. Share it for your reference, as follows:
I won't give much introduction to the problem of n queen here. For related introductions and algorithm analysis, please refer to the previous article.C++ solves the Eight Queens problem based on backtracking method。
The basic practice of backtracking is search, or an exhaustive search method that is organized and can avoid unnecessary search. This method is suitable for solving some problems with considerable combinations.
In the solution space tree of the problem, the backtracking method searches the solution space tree from the root node according to the depth priority strategy. When the algorithm searches at any point in the solution space tree, first determine whether the node contains the solution to the problem. If it is definitely not included, skip searches for subtrees with the node as root and trace back to their ancestor nodes layer by layer; otherwise, enter the subtree and continue searching according to the depth-first strategy.
Guiding ideology of the retrospective method - if you can't understand it, you will turn around. Design process: determine the solution space of the problem; determine the extension rules of the node; search.
Here we mainly show how to use php to implement this problem
$tresRepresents a feasible attempt
$resRecord total results
For detailed data structure analysis, please refer to the previous article link.
<?php
//check is valid now
function check($l,$c){
global $tres;
global $res;
global $n,$count;
foreach($tres as $key=>$value){
if($key<$l){
if($value==$c){
return 0;
}else if(abs($l-$key)==abs($c-$value)){
return 0;
}
}
}
return 1;
}
function scan($line){
global $tres;
global $res;
global $n,$count;
if($line==$n){
$res[]=$tres;
// $tres=array();
$count++;
}else{
for($i=0;$i<$n;$i++){
if(check($line,$i)==1){
$tres[$line]=$i;
$nxline=$line+1;
scan($nxline);
}
}
}
}
$tres=array();
$res=array();
$n=8;$count=0;
$stime=microtime();
scan(0);
$etime=microtime();
var_dump($res);
echo "there is $count ways !\n";
$t=$etime-$stime;
echo (int)$t."seconds used.";
Running results:
Copy the codeThe code is as follows:
array(92) { [0]=> array(8) { [0]=> int(0) [1]=> int(4) [2]=> int(7) [3]=> int(5) [4]=> int(2) [5]=> int(6) [6]=> int(1) [7]=> int(3) } [1]=> array(8) { [0]=> int(0) [1]=> int(5) [2]=> int(7) [3]=> int(2) [4]=> int(6) [5]=> int(3) [6]=> int(1) [7]=> int(4) } [2]=> array(8) { [0]=> int(0) [1]=> int(6) [2]=> int(3) [3]=> int(5) [4]=> int(7) [5]=> int(1) [6]=> int(4) [7]=> int(2) } [3]=> array(8) { [0]=> int(0) [1]=> int(6) [2]=> int(4) [3]=> int(7) [4]=> int(1) [5]=> int(3) [6]=> int(5) [7]=> int(2) } [4]=> array(8) { [0]=> int(1) [1]=> int(3) [2]=> int(5) [3]=> int(7) [4]=> int(2) [5]=> int(0) [6]=> int(6) [7]=> int(4) } [5]=> array(8) { [0]=> int(1) [1]=> int(4) [2]=> int(6) [3]=> int(0) [4]=> int(2) [5]=> int(7) [6]=> int(5) [7]=> int(3) } [6]=> array(8) { [0]=> int(1) [1]=> int(4) [2]=> int(6) [3]=> int(3) [4]=> int(0) [5]=> int(7) [6]=> int(5) [7]=> int(2) } [7]=> array(8) { [0]=> int(1) [1]=> int(5) [2]=> int(0) [3]=> int(6) [4]=> int(3) [5]=> int(7) [6]=> int(2) [7]=> int(4) } [8]=> array(8) { [0]=> int(1) [1]=> int(5) [2]=> int(7) [3]=> int(2) [4]=> int(0) [5]=> int(3) [6]=> int(6) [7]=> int(4) } [9]=> array(8) { [0]=> int(1) [1]=> int(6) [2]=> int(2) [3]=> int(5) [4]=> int(7) [5]=> int(4) [6]=> int(0) [7]=> int(3) } [10]=> array(8) { [0]=> int(1) [1]=> int(6) [2]=> int(4) [3]=> int(7) [4]=> int(0) [5]=> int(3) [6]=> int(5) [7]=> int(2) } [11]=> array(8) { [0]=> int(1) [1]=> int(7) [2]=> int(5) [3]=> int(0) [4]=> int(2) [5]=> int(4) [6]=> int(6) [7]=> int(3) } [12]=> array(8) { [0]=> int(2) [1]=> int(0) [2]=> int(6) [3]=> int(4) [4]=> int(7) [5]=> int(1) [6]=> int(3) [7]=> int(5) } [13]=> array(8) { [0]=> int(2) [1]=> int(4) [2]=> int(1) [3]=> int(7) [4]=> int(0) [5]=> int(6) [6]=> int(3) [7]=> int(5) } [14]=> array(8) { [0]=> int(2) [1]=> int(4) [2]=> int(1) [3]=> int(7) [4]=> int(5) [5]=> int(3) [6]=> int(6) [7]=> int(0) } [15]=> array(8) { [0]=> int(2) [1]=> int(4) [2]=> int(6) [3]=> int(0) [4]=> int(3) [5]=> int(1) [6]=> int(7) [7]=> int(5) } [16]=> array(8) { [0]=> int(2) [1]=> int(4) [2]=> int(7) [3]=> int(3) [4]=> int(0) [5]=> int(6) [6]=> int(1) [7]=> int(5) } [17]=> array(8) { [0]=> int(2) [1]=> int(5) [2]=> int(1) [3]=> int(4) [4]=> int(7) [5]=> int(0) [6]=> int(6) [7]=> int(3) } [18]=> array(8) { [0]=> int(2) [1]=> int(5) [2]=> int(1) [3]=> int(6) [4]=> int(0) [5]=> int(3) [6]=> int(7) [7]=> int(4) } [19]=> array(8) { [0]=> int(2) [1]=> int(5) [2]=> int(1) [3]=> int(6) [4]=> int(4) [5]=> int(0) [6]=> int(7) [7]=> int(3) } [20]=> array(8) { [0]=> int(2) [1]=> int(5) [2]=> int(3) [3]=> int(0) [4]=> int(7) [5]=> int(4) [6]=> int(6) [7]=> int(1) } [21]=> array(8) { [0]=> int(2) [1]=> int(5) [2]=> int(3) [3]=> int(1) [4]=> int(7) [5]=> int(4) [6]=> int(6) [7]=> int(0) } [22]=> array(8) { [0]=> int(2) [1]=> int(5) [2]=> int(7) [3]=> int(0) [4]=> int(3) [5]=> int(6) [6]=> int(4) [7]=> int(1) } [23]=> array(8) { [0]=> int(2) [1]=> int(5) [2]=> int(7) [3]=> int(0) [4]=> int(4) [5]=> int(6) [6]=> int(1) [7]=> int(3) } [24]=> array(8) { [0]=> int(2) [1]=> int(5) [2]=> int(7) [3]=> int(1) [4]=> int(3) [5]=> int(0) [6]=> int(6) [7]=> int(4) } [25]=> array(8) { [0]=> int(2) [1]=> int(6) [2]=> int(1) [3]=> int(7) [4]=> int(4) [5]=> int(0) [6]=> int(3) [7]=> int(5) } [26]=> array(8) { [0]=> int(2) [1]=> int(6) [2]=> int(1) [3]=> int(7) [4]=> int(5) [5]=> int(3) [6]=> int(0) [7]=> int(4) } [27]=> array(8) { [0]=> int(2) [1]=> int(7) [2]=> int(3) [3]=> int(6) [4]=> int(0) [5]=> int(5) [6]=> int(1) [7]=> int(4) } [28]=> array(8) { [0]=> int(3) [1]=> int(0) [2]=> int(4) [3]=> int(7) [4]=> int(1) [5]=> int(6) [6]=> int(2) [7]=> int(5) } [29]=> array(8) { [0]=> int(3) [1]=> int(0) [2]=> int(4) [3]=> int(7) [4]=> int(5) [5]=> int(2) [6]=> int(6) [7]=> int(1) } [30]=> array(8) { [0]=> int(3) [1]=> int(1) [2]=> int(4) [3]=> int(7) [4]=> int(5) [5]=> int(0) [6]=> int(2) [7]=> int(6) } [31]=> array(8) { [0]=> int(3) [1]=> int(1) [2]=> int(6) [3]=> int(2) [4]=> int(5) [5]=> int(7) [6]=> int(0) [7]=> int(4) } [32]=> array(8) { [0]=> int(3) [1]=> int(1) [2]=> int(6) [3]=> int(2) [4]=> int(5) [5]=> int(7) [6]=> int(4) [7]=> int(0) } [33]=> array(8) { [0]=> int(3) [1]=> int(1) [2]=> int(6) [3]=> int(4) [4]=> int(0) [5]=> int(7) [6]=> int(5) [7]=> int(2) } [34]=> array(8) { [0]=> int(3) [1]=> int(1) [2]=> int(7) [3]=> int(4) [4]=> int(6) [5]=> int(0) [6]=> int(2) [7]=> int(5) } [35]=> array(8) { [0]=> int(3) [1]=> int(1) [2]=> int(7) [3]=> int(5) [4]=> int(0) [5]=> int(2) [6]=> int(4) [7]=> int(6) } [36]=> array(8) { [0]=> int(3) [1]=> int(5) [2]=> int(0) [3]=> int(4) [4]=> int(1) [5]=> int(7) [6]=> int(2) [7]=> int(6) } [37]=> array(8) { [0]=> int(3) [1]=> int(5) [2]=> int(7) [3]=> int(1) [4]=> int(6) [5]=> int(0) [6]=> int(2) [7]=> int(4) } [38]=> array(8) { [0]=> int(3) [1]=> int(5) [2]=> int(7) [3]=> int(2) [4]=> int(0) [5]=> int(6) [6]=> int(4) [7]=> int(1) } [39]=> array(8) { [0]=> int(3) [1]=> int(6) [2]=> int(0) [3]=> int(7) [4]=> int(4) [5]=> int(1) [6]=> int(5) [7]=> int(2) } [40]=> array(8) { [0]=> int(3) [1]=> int(6) [2]=> int(2) [3]=> int(7) [4]=> int(1) [5]=> int(4) [6]=> int(0) [7]=> int(5) } [41]=> array(8) { [0]=> int(3) [1]=> int(6) [2]=> int(4) [3]=> int(1) [4]=> int(5) [5]=> int(0) [6]=> int(2) [7]=> int(7) } [42]=> array(8) { [0]=> int(3) [1]=> int(6) [2]=> int(4) [3]=> int(2) [4]=> int(0) [5]=> int(5) [6]=> int(7) [7]=> int(1) } [43]=> array(8) { [0]=> int(3) [1]=> int(7) [2]=> int(0) [3]=> int(2) [4]=> int(5) [5]=> int(1) [6]=> int(6) [7]=> int(4) } [44]=> array(8) { [0]=> int(3) [1]=> int(7) [2]=> int(0) [3]=> int(4) [4]=> int(6) [5]=> int(1) [6]=> int(5) [7]=> int(2) } [45]=> array(8) { [0]=> int(3) [1]=> int(7) [2]=> int(4) [3]=> int(2) [4]=> int(0) [5]=> int(6) [6]=> int(1) [7]=> int(5) } [46]=> array(8) { [0]=> int(4) [1]=> int(0) [2]=> int(3) [3]=> int(5) [4]=> int(7) [5]=> int(1) [6]=> int(6) [7]=> int(2) } [47]=> array(8) { [0]=> int(4) [1]=> int(0) [2]=> int(7) [3]=> int(3) [4]=> int(1) [5]=> int(6) [6]=> int(2) [7]=> int(5) } [48]=> array(8) { [0]=> int(4) [1]=> int(0) [2]=> int(7) [3]=> int(5) [4]=> int(2) [5]=> int(6) [6]=> int(1) [7]=> int(3) } [49]=> array(8) { [0]=> int(4) [1]=> int(1) [2]=> int(3) [3]=> int(5) [4]=> int(7) [5]=> int(2) [6]=> int(0) [7]=> int(6) } [50]=> array(8) { [0]=> int(4) [1]=> int(1) [2]=> int(3) [3]=> int(6) [4]=> int(2) [5]=> int(7) [6]=> int(5) [7]=> int(0) } [51]=> array(8) { [0]=> int(4) [1]=> int(1) [2]=> int(5) [3]=> int(0) [4]=> int(6) [5]=> int(3) [6]=> int(7) [7]=> int(2) } [52]=> array(8) { [0]=> int(4) [1]=> int(1) [2]=> int(7) [3]=> int(0) [4]=> int(3) [5]=> int(6) [6]=> int(2) [7]=> int(5) } [53]=> array(8) { [0]=> int(4) [1]=> int(2) [2]=> int(0) [3]=> int(5) [4]=> int(7) [5]=> int(1) [6]=> int(3) [7]=> int(6) } [54]=> array(8) { [0]=> int(4) [1]=> int(2) [2]=> int(0) [3]=> int(6) [4]=> int(1) [5]=> int(7) [6]=> int(5) [7]=> int(3) } [55]=> array(8) { [0]=> int(4) [1]=> int(2) [2]=> int(7) [3]=> int(3) [4]=> int(6) [5]=> int(0) [6]=> int(5) [7]=> int(1) } [56]=> array(8) { [0]=> int(4) [1]=> int(6) [2]=> int(0) [3]=> int(2) [4]=> int(7) [5]=> int(5) [6]=> int(3) [7]=> int(1) } [57]=> array(8) { [0]=> int(4) [1]=> int(6) [2]=> int(0) [3]=> int(3) [4]=> int(1) [5]=> int(7) [6]=> int(5) [7]=> int(2) } [58]=> array(8) { [0]=> int(4) [1]=> int(6) [2]=> int(1) [3]=> int(3) [4]=> int(7) [5]=> int(0) [6]=> int(2) [7]=> int(5) } [59]=> array(8) { [0]=> int(4) [1]=> int(6) [2]=> int(1) [3]=> int(5) [4]=> int(2) [5]=> int(0) [6]=> int(3) [7]=> int(7) } [60]=> array(8) { [0]=> int(4) [1]=> int(6) [2]=> int(1) [3]=> int(5) [4]=> int(2) [5]=> int(0) [6]=> int(7) [7]=> int(3) } [61]=> array(8) { [0]=> int(4) [1]=> int(6) [2]=> int(3) [3]=> int(0) [4]=> int(2) [5]=> int(7) [6]=> int(5) [7]=> int(1) } [62]=> array(8) { [0]=> int(4) [1]=> int(7) [2]=> int(3) [3]=> int(0) [4]=> int(2) [5]=> int(5) [6]=> int(1) [7]=> int(6) } [63]=> array(8) { [0]=> int(4) [1]=> int(7) [2]=> int(3) [3]=> int(0) [4]=> int(6) [5]=> int(1) [6]=> int(5) [7]=> int(2) } [64]=> array(8) { [0]=> int(5) [1]=> int(0) [2]=> int(4) [3]=> int(1) [4]=> int(7) [5]=> int(2) [6]=> int(6) [7]=> int(3) } [65]=> array(8) { [0]=> int(5) [1]=> int(1) [2]=> int(6) [3]=> int(0) [4]=> int(2) [5]=> int(4) [6]=> int(7) [7]=> int(3) } [66]=> array(8) { [0]=> int(5) [1]=> int(1) [2]=> int(6) [3]=> int(0) [4]=> int(3) [5]=> int(7) [6]=> int(4) [7]=> int(2) } [67]=> array(8) { [0]=> int(5) [1]=> int(2) [2]=> int(0) [3]=> int(6) [4]=> int(4) [5]=> int(7) [6]=> int(1) [7]=> int(3) } [68]=> array(8) { [0]=> int(5) [1]=> int(2) [2]=> int(0) [3]=> int(7) [4]=> int(3) [5]=> int(1) [6]=> int(6) [7]=> int(4) } [69]=> array(8) { [0]=> int(5) [1]=> int(2) [2]=> int(0) [3]=> int(7) [4]=> int(4) [5]=> int(1) [6]=> int(3) [7]=> int(6) } [70]=> array(8) { [0]=> int(5) [1]=> int(2) [2]=> int(4) [3]=> int(6) [4]=> int(0) [5]=> int(3) [6]=> int(1) [7]=> int(7) } [71]=> array(8) { [0]=> int(5) [1]=> int(2) [2]=> int(4) [3]=> int(7) [4]=> int(0) [5]=> int(3) [6]=> int(1) [7]=> int(6) } [72]=> array(8) { [0]=> int(5) [1]=> int(2) [2]=> int(6) [3]=> int(1) [4]=> int(3) [5]=> int(7) [6]=> int(0) [7]=> int(4) } [73]=> array(8) { [0]=> int(5) [1]=> int(2) [2]=> int(6) [3]=> int(1) [4]=> int(7) [5]=> int(4) [6]=> int(0) [7]=> int(3) } [74]=> array(8) { [0]=> int(5) [1]=> int(2) [2]=> int(6) [3]=> int(3) [4]=> int(0) [5]=> int(7) [6]=> int(1) [7]=> int(4) } [75]=> array(8) { [0]=> int(5) [1]=> int(3) [2]=> int(0) [3]=> int(4) [4]=> int(7) [5]=> int(1) [6]=> int(6) [7]=> int(2) } [76]=> array(8) { [0]=> int(5) [1]=> int(3) [2]=> int(1) [3]=> int(7) [4]=> int(4) [5]=> int(6) [6]=> int(0) [7]=> int(2) } [77]=> array(8) { [0]=> int(5) [1]=> int(3) [2]=> int(6) [3]=> int(0) [4]=> int(2) [5]=> int(4) [6]=> int(1) [7]=> int(7) } [78]=> array(8) { [0]=> int(5) [1]=> int(3) [2]=> int(6) [3]=> int(0) [4]=> int(7) [5]=> int(1) [6]=> int(4) [7]=> int(2) } [79]=> array(8) { [0]=> int(5) [1]=> int(7) [2]=> int(1) [3]=> int(3) [4]=> int(0) [5]=> int(6) [6]=> int(4) [7]=> int(2) } [80]=> array(8) { [0]=> int(6) [1]=> int(0) [2]=> int(2) [3]=> int(7) [4]=> int(5) [5]=> int(3) [6]=> int(1) [7]=> int(4) } [81]=> array(8) { [0]=> int(6) [1]=> int(1) [2]=> int(3) [3]=> int(0) [4]=> int(7) [5]=> int(4) [6]=> int(2) [7]=> int(5) } [82]=> array(8) { [0]=> int(6) [1]=> int(1) [2]=> int(5) [3]=> int(2) [4]=> int(0) [5]=> int(3) [6]=> int(7) [7]=> int(4) } [83]=> array(8) { [0]=> int(6) [1]=> int(2) [2]=> int(0) [3]=> int(5) [4]=> int(7) [5]=> int(4) [6]=> int(1) [7]=> int(3) } [84]=> array(8) { [0]=> int(6) [1]=> int(2) [2]=> int(7) [3]=> int(1) [4]=> int(4) [5]=> int(0) [6]=> int(5) [7]=> int(3) } [85]=> array(8) { [0]=> int(6) [1]=> int(3) [2]=> int(1) [3]=> int(4) [4]=> int(7) [5]=> int(0) [6]=> int(2) [7]=> int(5) } [86]=> array(8) { [0]=> int(6) [1]=> int(3) [2]=> int(1) [3]=> int(7) [4]=> int(5) [5]=> int(0) [6]=> int(2) [7]=> int(4) } [87]=> array(8) { [0]=> int(6) [1]=> int(4) [2]=> int(2) [3]=> int(0) [4]=> int(5) [5]=> int(7) [6]=> int(1) [7]=> int(3) } [88]=> array(8) { [0]=> int(7) [1]=> int(1) [2]=> int(3) [3]=> int(0) [4]=> int(6) [5]=> int(4) [6]=> int(2) [7]=> int(5) } [89]=> array(8) { [0]=> int(7) [1]=> int(1) [2]=> int(4) [3]=> int(2) [4]=> int(0) [5]=> int(6) [6]=> int(3) [7]=> int(5) } [90]=> array(8) { [0]=> int(7) [1]=> int(2) [2]=> int(0) [3]=> int(5) [4]=> int(1) [5]=> int(4) [6]=> int(6) [7]=> int(3) } [91]=> array(8) { [0]=> int(7) [1]=> int(3) [2]=> int(0) [3]=> int(2) [4]=> int(5) [5]=> int(1) [6]=> int(6) [7]=> int(4) } } there is 92 ways ! 0seconds used.
There is also something to be explained. The time calculation of the last face is not very rigorous. The high-precision variable PHP cannot be subtracted directly, and there will be serious errors. Only temporary demonstrations are made here, and relevant functions need to be called if they need to be calculated accurately.
For more information about PHP related content, please check out the topic of this site:PHP data structure and algorithm tutorial》、《Summary of PHP Programming Algorithm》、《Summary of usage of php strings》、《Complete collection of PHP array (Array) operation techniques》、《Summary of common traversal algorithms and techniques for PHP"and"Summary of PHP mathematical operation skills》
I hope this article will be helpful to everyone's PHP programming.