大學踏入程式開始,便鮮少練習這種偏重技巧與邏輯的題目
反而開始接觸網頁程式與資料庫,都是專案開發較多
近來無聊想說練習一下以前常聽到但沒做過的問題
也就是非常經典的八皇后問題,在西洋棋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; }
文章標籤
全站熱搜
留言列表