何謂"八皇后"問題?

 

< 維基百科 > 內的說明
八皇后問題是一個以西洋棋為背景的問題:如何能夠在 8×8 的西洋棋棋盤上放置八個皇后,使得任何一個皇后都無法直接吃掉其他的皇后?為了達到此目的,任兩個皇后都不能處於同一條橫行、縱行或斜線上


這個問題被稱為遞迴問題的典型,網路上搜尋"八皇后"就可找到一堆資料,但是關於正確的解法程式...可說幾乎都是C語言的天下,其他程式語言的解法幾乎少到可列入保育類了

 

網路上找到用LabVIEW的解題程式少到用一隻手的手指都算的出來,用的方法都很類似:先隨機放上8個皇后,在去檢查是否為正解?這種做法往往迴圈要跑個幾萬次才得到1個解,那要得到全部92個解迴圈要跑幾次呢?而且解題的過程和"遞迴"毫無關係,只能算是暴力式解法

 

 

這一題真要做也不是很簡單,花了幾天先畫了解題的流程圖,又花了幾天修改流程圖,使整個流程簡化,最後完成如下圖的流程圖

20110514-11  

 

有部分流程參考了其他程式語言寫的程式,但沒有全盤照抄改寫。因為其他程式寫了十幾行的東西,有時LabVIEW一個元件就解決了。一些特殊點的寫法在2010版的LabVIEW有類似性質的元件可套用,在舊版的LabVIEW都沒有。這個流程圖則是針對7.1版的LabVIEW去修正

 

 

再來針對流程圖來寫程式

 

分析整個流程圖,有幾個步驟是重覆執行使用的,所謂的"遞迴"指的就是此一反覆執行的動作,這重覆的部分應用上要寫成SubVI來簡化程式,重覆的動作有:


1.搜尋空位:搜尋可放皇后的有效空位


2.標記皇后:標記皇后在棋盤上的攻擊範圍,在搜尋空位時就會把標記過的座標點當作無效空位


3.重新標記:當搜尋不到有效空位時,回溯到上一步驟的有效空位,再搜尋下一個有效空位做標記


4.顯示解答:依照流程圖得到的解只是每個皇后的座標而已,所以要再把座標轉成圖形畫面輸出

 

 

 

先製作SubVI程式:

 

1.搜尋空位:

 

基本上只是要搜尋每個Y列上的有效空位X?,所以用Index Array元件來自動指定要搜尋的Y列。搜尋就使用Search 1D Array元件,搜尋的起點之所以拉出來設為輸入點,是希望程式找到的空位無解時,能自動跳過那個空位找下一個空位。因為標記皇攻擊範圍用的2D陣列初始值為0,標記過的位置值為1,所以搜尋的值設定為0

20110514-01  

 

 

2.標記皇后:


標記程式的部分借重Replace Array Subset的功能,基本上是以找到的空位為中心,把縱橫斜向的原本值0置換為1

20110514-02  

 

 

3.重新標記:


重新標記借重標記皇后這個SubVI的功能,基本上是先把標記皇后攻擊範圍用的2D陣列所有值還原為0,再以已記錄的皇后位置重新標記置換攻擊範圍的值為1

20110514-03  

 

 

4.顯示解答:

 

顯示部分分成兩大部分,一個是文字敘速部分,另一個是圖形顯示部分

 

圖形顯示的部分比較傷腦筋,要能解決顯示棋盤黑白交錯格子和顯示皇后位置的問題,於是用Pict Ring元件放進黑、白和皇冠圖片,成為一個有3種狀態的物件

20110514-04  

 

再放進陣列內構成棋盤

20110514-05  

 

棋盤面板完成後,再來就是依需求完成把紀錄皇后位置數值轉換為顯示陣列的程式

20110514-06  

 

 

再來寫主程式


依照流程分拆成兩大部分:


左半邊利用迴圈不停的回溯搜尋,直到有解或無解時才停止迴圈

20110514-07  

 

右半邊在無解時不執行,有解時就轉換成文字和圖形顯示結果。下方放迴圈,是希望以手動控制一次只顯示一組解

20110514-08  

 

完成的完整程式架構

20110514-09  

 

解答顯示面板

20110514-10  

, ,

未出師的小工程師 發表在 痞客邦 PIXNET 留言(0) 人氣()