PHP基于回溯算法解决n皇后问题的方法示例
本文实例讲述了PHP基于回溯算法解决n皇后问题的方法。分享给大家供大家参考，具体如下：
这里对于n皇后问题就不做太多的介绍，相关的介绍与算法分析可参考前面一篇C++基于回溯法解决八皇后问题。
回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。
回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
回溯法指导思想——走不通，就掉头。设计过程：确定问题的解空间；确定结点的扩展规则；搜索。
这里主要展示怎么用php实现该问题
$tres代表一次可行的尝试
$res记录总结果
详细数据结构分析可以参考前面的文章链接。
$value){
if($key<$l){
if($value==$c){
return0;
}elseif(abs($l-$key)==abs($c-$value)){
return0;
}
}
}
return1;
}
functionscan($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"thereis$countways!\n";
$t=$etime-$stime;
echo(int)$t."secondsused.";
运行结果：
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)}}thereis92ways!0secondsused.
还有要说明的最后面面的时间计算不太严谨高精度的变量php是不能直接相减的会有严重误差。这里只做临时演示，需要精确计算还得调用相关函数。
更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》
希望本文所述对大家PHP程序设计有所帮助。