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程序设计有所帮助。