本文實例講述了PHP基于回溯算法解決n皇后問題的方法。分享給大家供大家參考，具體如下：
這里對于n皇后問題就不做太多的介紹，相關的介紹與算法分析可參考前面一篇C++基于回溯法解決八皇后問題。
回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當大的問題。
回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解。如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。
回溯法指導思想——走不通，就掉頭。設計過程：確定問題的解空間；確定結點的擴展規(guī)則；搜索。
這里主要展示怎么用php實現(xiàn)該問題
$tres代表一次可行的嘗試
$res 記錄總結果
詳細數(shù)據(jù)結構分析 可以參考前面的文章鏈接。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
<?php//check is valid nowfunction 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."; |
運行結果：
復制代碼 代碼如下:
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.
還有要說明的 最后面面的時間計算 不太嚴謹 高精度的變量php是不能直接相減的 會有嚴重誤差。這里只做臨時演示，需要精確計算還得調用相關函數(shù)。
希望本文所述對大家PHP程序設計有所幫助。
原文鏈接：http://blog.csdn.net/myphpnotes/article/details/17561613
