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

葉均隆　葉均明　余偉紅

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

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

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

1 視覺圖像思維介紹

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

2 以經典算法八皇后問題為例

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

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

3 八皇后算法問題拓展

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

4 結語

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

[參考文獻]

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