<?php class Backtracking {  protected $chessboard;  // 棋盤 二維數組 表示坐標軸 protected $N;      // N表示幾皇后 protected $has_set_x;  // 已經設置的x坐標數組 已經設置的x坐標就不能重復了，用于檢查坐標是否可用 protected $has_set_y;  // 已經設置的y坐標數組 已經設置的y坐標就不能重復了，用于檢查坐標是否可用 protected $has_set_site; // 已經設置的點  function __construct($N) { // 初始化數據 $this->N = $N; $this->chessboard = array(); for ($i=0; $i < $N; $i++) {   for ($j=0; $j < $N; $j++) {   $this->chessboard[$i][$j] = 0;  } } $this->has_set_x = array(); $this->has_set_y = array(); $this->has_set_site = array(); }  // 獲取排列 public function getPermutation($is_get_on = true) { // is_get_on 是否獲取一種排列 true:是 false:獲取所有排列 $current_n = 0; // 當前設置第幾個皇后 $start_x = 0;  // 當前的x坐標 從x開始放置嘗試 $permutation_array = array(); // 全部皇后放置成功的排列數組 while ($current_n < $this->N && $current_n >= 0) {  $site_result = $this->setQueenSite($current_n, $start_x); // 設置皇后位置  if($site_result == true && $current_n + 1 >= $this->N) { // 如果最后的皇后位置放置成功則記錄信息  $permutation_array[] = array_merge($this->has_set_site, array(array('x' => $site_result['x'], 'y' => $site_result['y'])));  if($is_get_on == false) { // 如果是獲取所有排列，則設置當前放置失敗，讓程序回溯繼續找到其他排列   $site_result = false;  }  }  if($site_result == true) {  $this->chessboard[$site_result['x']][$site_result['y']] = 1;  $this->has_set_x[] = $site_result['x'];  $this->has_set_y[] = $site_result['y'];  $this->has_set_site[] = array('x' => $site_result['x'], 'y' => $site_result['y']);  $current_n++; // 皇后位置放置成功，繼續設置下一個皇后，重置下一個皇后的x坐標從0開始  $start_x = 0;  }else {  // 當前皇后找不到放置的位置，則需要回溯到上一步  $previous_site = array_pop($this->has_set_site); // 找到上一步皇后的位置  if(!empty($previous_site)) {   $start_x = $previous_site['x'] + 1; // 讓上一步的皇后的x坐標+1繼續嘗試放置   $this->deleteArrayValue($this->has_set_x, $previous_site['x']);   $this->deleteArrayValue($this->has_set_y, $previous_site['y']);   $this->chessboard[$previous_site['x']][$previous_site['y']] = 0;  }  $current_n--; // 回溯到上一步，即讓一個皇后x坐標+1繼續嘗試放置  } } return $permutation_array; }  // 設置皇后位置 public function setQueenSite($n, $start_x) { $start_y = $n; if($start_x >= $this->N) return false; $check_result = $this->checkQueenSite($start_x, $start_y); // 檢查當前是否可放置 if($check_result == true) {  return array('x' => $start_x, 'y' => $start_y); }else { // 不可放置，則x坐標+1，繼續嘗試  $start_x++;  return $this->setQueenSite($n, $start_x); } }  // 檢查皇后位置是否正確 public function checkQueenSite($x, $y) { // 判斷當前坐標的橫、縱、斜線是否存在已經放置的皇后 if(in_array($x, $this->has_set_x)) return false; if(in_array($y, $this->has_set_y)) return false; $operate_array = array(  array('operate_x' => '+', 'operate_y' => '+'),  array('operate_x' => '-', 'operate_y' => '-'),  array('operate_x' => '+', 'operate_y' => '-'),  array('operate_x' => '-', 'operate_y' => '+') ); foreach ($operate_array as $key => $value) {  $diagonal_x = $x;  $diagonal_y = $y;  while (true) {  eval("/$diagonal_x=$diagonal_x {$value['operate_x']} 1;");  eval("/$diagonal_y=$diagonal_y {$value['operate_y']} 1;");  if($diagonal_x >= $this->N || $diagonal_y >= $this->N || $diagonal_x < 0 || $diagonal_y < 0) break;  if($this->chessboard[$diagonal_x][$diagonal_y] == 1) return false;  } } return true; }  // 刪除數組元素 public function deleteArrayValue(&$array, $value) { $delete_key = array_search($value, $array); array_splice($array, $delete_key, 1); } } $N = 8; // 8表示獲取8皇后的排列組合$backtracking = new Backtracking($N);$permutations = $backtracking->getPermutation(false);var_dump($permutations); // 輸出92種排列