PHP backtracking algorithm solves the n-queens problem_PHP tutorial

The basic method of backtracking is search, or an exhaustive search method that is well organized and can avoid unnecessary searches. This method is suitable for solving some problems with quite large number of combinations.

The backtracking method follows the depth-first strategy in the solution space tree of the problem and searches the solution space tree starting from the root node. When the algorithm searches to any point in the solution space tree, it first determines whether the node contains the solution to the problem. If it is definitely not included, skip the search for the subtree with the node as the root and backtrack to its ancestor nodes layer by layer; otherwise, enter the subtree and continue searching according to the depth-first strategy.

The guiding ideology of the backtracking method - if you can't make it, turn around. Design process: determine the solution space of the problem; determine the expansion rules of the nodes; search.

Here we mainly show how to use php to achieve this problem

$tres represents a feasible attempt

$res records the total results

For detailed data structure analysis, please refer to the link.

$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 ! ; $t=$etime-$stime; echo (int)$t.seconds used.;