N皇后问题

 1 <?php 
 2 /**
 3 *在n行n列的棋盘上，如果两个皇后位于棋盘上
 4 *的同一行或者同一列或者同一对角线上，则称
 5 *他们为互相攻击。现要求找出使n元棋盘上的n
 6 *个皇后互不攻击的所有布局。
 7 */
 8 //判断第k个皇后放在k行的x列上会不会有冲突
 9 function place($k,$x){
10     for($i=0;$i<$k;$i++){
11         if(abs($k-$i)==abs($x[$k]-$x[$i])||$x[$k]==$x[$i]){
12             return false;
13         }
14     }
15     return true;
16 }
17 function queen($n){
18     $x = array();
19     for($i=0;$i<$n;$i++){
20         $x[$i] = 0;
21     }
22     $i = 0;
23     while($i>=0&&$i<$n){
24         while($x[$i]<$n&&!place($i,$x)){
25             $x[$i] = $x[$i] + 1;
26         }
27         if($x[$i]<$n&&$i==$n-1){
28             print_r($x);
29             exit;
30         }else if($x[$i]>=$n){
31             $x[$i] = 0;
32             $i -= 1;
33             $x[$i] += 1;
34         }else{
35             $i += 1;
36         }
37     }
38 }
39 queen(10);