PHP backtracking algorithm solves the n-queens problem

PHP backtracking algorithm solves the n-queens problem_PHP tutorial

WBOY

Release： 2016-07-13 10:42:23

Original

1193 people have browsed it

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.

Copy after login

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

Copy after login

//There is something else to explain. The final time calculation is not very rigorous. High-precision variables PHP cannot be directly subtracted, and there will be serious errors. This is only a temporary demonstration. If accurate calculation is required, relevant functions must be called.