快捷導(dǎo)航

PHP基于回溯算法解決n皇后問(wèn)題的方法示例

更新時(shí)間：2017年11月07日 09:40:38 作者：藍(lán)山小智

這篇文章主要介紹了PHP基于回溯算法解決n皇后問(wèn)題的方法,結(jié)合實(shí)例形式分析了PHP基于回溯算法解決N皇后問(wèn)題的原理與具體實(shí)現(xiàn)技巧,需要的朋友可以參考下

本文實(shí)例講述了PHP基于回溯算法解決n皇后問(wèn)題的方法。分享給大家供大家參考，具體如下：

這里對(duì)于n皇后問(wèn)題就不做太多的介紹，相關(guān)的介紹與算法分析可參考前面一篇C++基于回溯法解決八皇后問(wèn)題。

回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問(wèn)題。

回溯法在問(wèn)題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。

回溯法指導(dǎo)思想——走不通，就掉頭。設(shè)計(jì)過(guò)程：確定問(wèn)題的解空間；確定結(jié)點(diǎn)的擴(kuò)展規(guī)則；搜索。

這里主要展示怎么用php實(shí)現(xiàn)該問(wèn)題

$tres代表一次可行的嘗試
$res 記錄總結(jié)果

詳細(xì)數(shù)據(jù)結(jié)構(gòu)分析可以參考前面的文章鏈接。

<?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.";

運(yùn)行結(jié)果：

復(fù)制代碼代碼如下:

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.

還有要說(shuō)明的最后面面的時(shí)間計(jì)算不太嚴(yán)謹(jǐn) 高精度的變量php是不能直接相減的會(huì)有嚴(yán)重誤差。這里只做臨時(shí)演示，需要精確計(jì)算還得調(diào)用相關(guān)函數(shù)。

更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設(shè)計(jì)算法總結(jié)》、《php字符串(string)用法總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結(jié)》及《PHP數(shù)學(xué)運(yùn)算技巧總結(jié)》

希望本文所述對(duì)大家PHP程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: