圖像思維解釋八皇后算法及其拓展問題

葉均隆　葉均明　余偉紅

摘 要：從多年教學中，筆者發(fā)現(xiàn)計算機專業(yè)的學生大多數(shù)在學習中運用的是數(shù)學邏輯思維，尤其在競賽中有獲獎的同學，如：藍橋杯獲獎的。這些優(yōu)秀同學利用邏輯推理思維去理解某些困難算法，如：八皇后、回溯、廣搜、深搜等算法，表現(xiàn)得非常困難，耗費很多時間仍然不得要領。如果通過圖像思維幫助其理解困難的算法問題，往往事半功倍。因此，文章研究了圖像思維解釋八皇后算法及其拓展問題。

關鍵詞：圖像思維；視覺化思維；藍橋杯；八皇后；教學設計；算法

運用圖像思維解釋八皇后算法問題是筆者立項以來第一個運用案例。文章適合有一定的C語言基礎的，想了解圖像思維的或遞歸算法能力薄弱但想加深理解的讀者。軟件技術和計算機應用技術專業(yè)是筆者所在院系人數(shù)最多的兩個專業(yè)，但在近年來每次參加藍橋杯省賽獲一等獎人數(shù)徘徊在1～2人。藍橋杯競賽的難題的解決主要是能否靈活運用適合的算法。通常題目越難，程序算法越復雜。從參賽的情況看，學生在軟件技術中的算法把握得還不夠。機器學習應用、自然語言處理、智能無人機、計算機視覺與圖像、人工智能、大數(shù)據(jù)、操作系統(tǒng)開發(fā)、智能導航等是國家重點發(fā)展核心領域，而這些領域的基礎都是靠好的算法。算法是軟件的靈魂，得益于好的算法會給軟件帶來的往往都是質的變化，性能都是呈指數(shù)倍提高的。如何培養(yǎng)學生程序算法設計能力，筆者提出新思路—嘗試運用視覺圖像思維。

1 視覺圖像思維介紹

視覺圖像思維自從人類誕生就產(chǎn)生了，在沒有發(fā)明文字前，人們用石器在石頭、木頭等物體上刻畫圖案用來表達事件、物體、動作等，人們幾乎不需要怎樣學習都能理解其意義。隨著社會的發(fā)展，原來的圖案慢慢變成規(guī)則的符號，失去形象的效果，思維方式也慢慢改變。視覺圖像思維是通過攝影般逼真的具體圖像來思考，視覺化思考的具體程度因人而異。一般的視覺思考者只能想象靜止的圖像。這些圖像的范圍包括，從具體地點的圖像，到更模糊的概念圖像。運用圖像思維的好處有：豐富的信息量、具體且形象、準確、推理方便、協(xié)助記憶、協(xié)助整理思路等。

2 以經(jīng)典算法八皇后問題為例

棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國際象棋上擺放8個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法[1]。運用計算機求解8個皇后問題，筆者將問題簡單化，由于運算原理相同，先求解四皇后問題，那么八皇后問題就迎刃而解。四皇后問題可再分兩部分處理，第一部分是：編寫解決同一行、同一列或同一斜線上判斷函數(shù)（函數(shù)返回“1”代表可此位置可放置棋子）。第二部分是：編寫遞歸函數(shù)檢測所有擺放情況，并算出其中符合要求擺放情況。筆者多年培訓藍橋杯的參賽者發(fā)現(xiàn)，第一部分的函數(shù)編寫問題不大，在第二部分的算法里，學生能完全理解原理較少。通過筆者多年的教學經(jīng)驗運用圖像分析，學生的學習效果較好，如圖1所示，程序按先根遍歷執(zhí)行，每個棋盤旁邊的數(shù)字為計算機執(zhí)行的順序。

如果讀者是第一次接觸這個四皇后問題，運用圖像思維入手，讀者只需觀察圖1所示的所有信息變化規(guī)律入手，不需閱讀其他文字說明，就很容易找出編寫遞歸函數(shù)實現(xiàn)的思路。序號2，19，32，42就是表格逐列循環(huán)（四皇后循環(huán)4次，八皇后循環(huán)8次如此類推）。在序號2下一層又同樣執(zhí)行逐列循環(huán)（序號3，4，5，10）。序號3，4因為不符合條件停止搜索，不會放置皇后，而在第二層的序號5（即檢測到放置在此位置是安全的，放置第二個皇后）下一層又同樣執(zhí)行逐列循環(huán)（序號6，7，8，9）。每個序號的下層都會進行同樣的檢索，直至4個皇后放置完畢，同時所處的位置安全即是所求的解，具體算法如圖2所示。這里還需注意一點，每次放置棋子后往后執(zhí)行需要回溯，例如：細心的讀者會發(fā)現(xiàn)，序號5完成一次遞歸函數(shù)調用會先清掉當前位置的棋子再到序號10位置運行，具體實現(xiàn)如圖2第11行所示。

3 八皇后算法問題拓展

如果棋盤大小及皇后的個數(shù)可任意設置，程序怎么求解有多少種擺法。這個問題可以轉化為特定問題的解，如：在3×4的棋盤放2個皇后，有多少種擺法。通過上面規(guī)則（4個皇后在4×4的棋盤）作進一步圖形轉換（2個皇后在3×4的棋盤），如圖3所示。轉換成對應的狀態(tài)后，觀察棋盤狀態(tài)執(zhí)行順序，如圖4所示，在當前函數(shù)結束時再次遞歸調用往下逐列循環(huán)探索，其他棋盤狀態(tài)同理不一一繪制（下同）。因此，從圖4的圖形變化推理，筆者找到函數(shù)遞歸調用的位置和要求—放置在函數(shù)體的最后，函數(shù)參數(shù)傳遞變化還是像原來那樣對行號的值加一處理（算法在圖2的偽代碼基礎修改），但是程序不能無限往下探索，從圖4的棋盤狀態(tài)可得行號最大是3，也就是需要增加遞歸結束條件：行號累加后不能超過3。繼續(xù)觀察圖4的變化可知，還需增加檢測放置皇后的數(shù)量的變量：count= count﹢1，達到要求的數(shù)量輸出并返回，放完后為了不影響后面的探索，需對這變量回溯：count= count-1。

4 結語

筆者最初編寫八皇后算法時，運用常用的數(shù)學邏輯編程思維，尚且能解決，但到了任意皇后及其拓展問題，感覺程序執(zhí)行的方向性難以把握，各變量的數(shù)值變化難以推理。通過轉變思路，使用作圖、圖形轉換、輔助線、圖形推理時恍然大悟，使復雜的事情變得簡單化了；感覺能看到程序運行全過程，并能捕捉到某一時刻的變量的變化，有點像在做建筑設計或機械設計。筆者拋磚引玉，引起大家去摸索圖像思維在教研中的作用，促進技能人才的培養(yǎng)和就業(yè)，同時提出解決問題的另一種思路。

[參考文獻]

[1]嚴蔚敏，吳偉民.數(shù)據(jù)結構C語言版[M].北京：清華大學出版社，2007.