冷言冷語

大學踏入程式開始，便鮮少練習這種偏重技巧與邏輯的題目

反而開始接觸網頁程式與資料庫，都是專案開發較多

近來無聊想說練習一下以前常聽到但沒做過的問題

也就是非常經典的八皇后問題，在西洋棋8X8的棋盤上放上8位皇后

不得在各自的攻擊範圍內，果然一開始就想很久，雖然查了一些講解

不過實在很不喜歡用遞迴的方式，根本不適合人腦思考= =

想了半天終於想到了不用遞迴，也可以做出來的方法了

實作成可顯示棋盤以及自訂棋盤大小的版本

點我連結

核心程式碼如下:

///棋盤寬度
$width=8;
/**
* 每一行的運算會驗證前面所有的候選解，留下通過驗證的候選解，候選解的表達
* 方式以字串_將每一行的位置接起來，以4X4為例:第一行所有位置皆有可能[0,1,2,3]
* ，第二行則[0_2,0_4,...]以此類推
*/
$answer = array();
for($i=0;$i<$width;$i++){
	///第一行的所有可能
	if($i==0){
		for($j=0;$j<$width;$j++){
			$answer[$i][] = $j;
		}
	}
	else{
		///候選解數量
		$count = count($answer[$i-1]);
		for($j=0;$j<$count;$j++){
			$value = explode('_',$answer[$i-1][$j]);
			///跑過該行由上而下可能的位置
			for($l=0;$l<$width;$l++){
				///旗標:判斷是否符合不與前面的皇后同列或者在斜線上
				$is_fit = TRUE;
				for($k=0,$k_length=count($value);$k<$k_length;$k++){
					///若同一列，或者在45度斜角上，則不符合
					if($l == $value[$k] || abs($l-$value[$k]) == abs($i-$k)){
						$is_fit = FALSE;
					}
				}
				if($is_fit){
					///寫入當前行數的候選解
					$answer[$i][] = $answer[$i-1][$j].'_'.$l;
				}
			}
		}
	}
}
///$answer[$width-1]即為所有解答組成的陣列

雖然平常碰到的工作大多不需要吃重的資料結構或演算法輔助

但是還是要多練習解決問題的能力啊~

順便附上畫棋盤的涵式~

/**
* 畫出棋盤與解答，使用span，要記得定義CSS長寬與顏色
* @param int $size 棋盤大小
* @parm String $answer 解答，格式(4X4):2_0_3_1
* @return String HTML格式輸出
*/
function draw_board($size,$answer){
	$html = '';
	$color = '';
	$ans_arr = explode('_',$answer);
	for($i=0;$i<$size;$i++){
		for($j=0;$j<$size;$j++){
			/*i與j相加為偶數，格子為黑，反之為白，但是，若size為
			奇數時要顛倒，因為是由上往下顯示的關係*/
			if(($i+$j)%2 == !($size%2)){
				$color = 'black';
			}
			else{
				$color = 'white';
			}
			$html .= ' ';
			if($j == $ans_arr[$i]){
				$html .= 'Q';
			}
			$html .= '';
		}
		$html .= '
';
	}
	$html .= '
';
	return $html;
}