huaxiazhihuo

C++代碼（2）八皇后問題

        八皇后實在太有名了，我也就不廢話了。利用回溯算法，不難寫出其代碼，相信各位同學也都干過了。那這篇文章還有何新意呢？難道是向各位展示在下的代碼要比各位好，絕對不是。只因用C++寫代碼的時候，很容易就陷入各種細節的糾纏中，必須牢記大刀闊斧地砍除無關緊要的細節，始終堅持用C++清晰地表達解決問題的思路，嚴格遵守單一職責的規則，集中精力解決問題，不賣弄半點花巧。這是在下努力的一種嘗試。
        八皇后的解決方案，相信大家也都知道了，請恕我直奔主題了。
        由于長年累月沉浸于C++中，中毒已經甚深了，碰到任何問題，都條件反射地將其大御八塊，然后用CLASS來組織。于是，非常自然的，我決定用類QueenGame來表示八皇后這個游戲，用Play來擺弄出一個安全棋局。當然，不用CLASS，也依然可以寫出清晰的代碼，但是，感覺總是很不習慣。于是，main起來就非常簡單了。         為何不讓DisplayQueens成為QueenGame的成員，那是因為最后的結果不止顯示于控制臺，也可能要寫入文件中，也可能會繪制于窗口上，而且就算于控制臺上，也有多種輸出方式，種種可能，無窮無盡，QueenGame難道要用一大堆成員函數來應付這些顯示要求，這無疑不切合實際，而且也將污染QueenGame的接口。當一個類無法預料一件操作將如何發生的時候，就應該把這個決定交給上層調用來決定好了，這也是C++一貫的作法，既然我不知道怎么辦，那就由用戶來決定好了。我們要保持清醒，QueenGame的職責只是要擺出讓各個Queen和平共處的局面，至于其他的事情，那都不屬于自己的事情。不在其位，不謀其政。
        接下來就要思考QueenGame里面有那些東東，除了Play，肯定還有一些其他東東，最起碼也應該有些房子來供皇后們居住。最自然的想法是用一個二維的bool數組chessboard來表示棋盤，假如chessboard[i][j]為true，就表示皇后在上面。但是，目前市面上的作法是用數組來儲存N個皇后的位置，數組上的元素的索引表示皇后在棋盤上第幾行，其值對應皇后在第幾列上，這種儲存方式相當方便高效，二維數組如何搗鼓，都沒它方便。因此，可以這樣定義后宮的地點int m_QueenPos[N]，代碼有點呆板，似乎應該用使用指針或者引入vector，來靈活處理不同數量的N個皇后，但這樣做，將引入一些其他的復雜性，對于本道程序，大可以假設皇后不會太多，10個已經足夠多了，犧牲一點點空間，來踢開這個細節，換取程序的安全穩定，我非常樂意。
        由于QueenGame可以Play不同數目的皇后，從1個到10個都可以，因此在QueenGame的構造函應該確立皇后的數量，同時，再提供一個函數GetQueenCount，用以獲取她們的數目。QueenGame的初版如下：
有了這些信息，就可以開始實作DisplayQueen了。但在此之前，還要解決一個問題，就是QueenGame如何讓外部函數來訪問它的棋盤局面呢？我的作法是直接暴露m_QueenPos，這不是公然違背了面向對象的封裝規定嗎？這樣做，我不會感到一絲絲的不安，因為除此之外，沒有更好的辦法了，其他的種種方案，都屬無病呻吟。比如說，仿效標準庫作法，typename一個迭代器，然后再搗鼓出一個begin和end的函數，這將要花費多少精力啊，這么做，僅僅是為了取悅封裝要求，而與原本要解決的問題根本是風馬牛不相及。那么采用GetQueenPos返回m_QueenPos的地址呢？這與直接訪問m_QueenPos并沒有多大的區別，如果以為這樣就可以滿足封裝，就可以享受封裝帶來的好處，純屬在自欺欺人罷了。還是一個辦法，就是讓DisplayQueens成為QueenGame的friend，這樣就可以不破壞封裝性，但如DisplayQueens不要為QueenGame的函數成員類似，既然DisplayQueens要為友元，那么WriteQueens也應為friend了，ShowQueens也應為friend了，為了滿足封裝，搞出這么多花招，畫蛇添足。……，但是，這樣直接暴露內部狀態，總是不安全的，那也沒什么，只要訂下規則，類外的一切函數不允許修改類的數據成員就OK了。總之，我不想在如何訪問m_QueenPos這個小細節上耗費一丁點精力了，我的精力應該集中在原本要解決的問題上。
        好了，做足準備工作了，終于來到問題核心了，實作QueenGame的Play函數。這可不是一件容易的事情，起碼不像前面的代碼那么容易好寫。來回顧一下我們聰明的大腦是如何處理這個問題的。面對著棋盤，我們手里拿著8個皇后，先把第1個皇后擺到第1行的第1列上開始，然后按照規則擺放第2個，也即是在第1個皇后的淫威之外給第2個皇后尋找第1個安身之所（總共有6個），然后再在第1、2個皇后的勢力范圍之外給第3個皇后謀求第1個住所，可知越往后，皇后們的生存空間將越來越狹窄，以至于在第N個皇后的時候，已無安身之所，說明第N-1個皇后的位置不恰當，將她挪到下一個地方，然后再嘗試擺上第N個皇后，如果嘗試遍了第N-1個皇后的住所，都無法給第N個皇后提供一個去處，說明第N-1個皇后的位置不當，回溯到第N-2個皇后上，然后擺上第N-1個皇后，用這個方法，最后終究能安頓好8個皇后。接下來，就是將其轉換成代碼，很明顯，這里出現了遞歸。代碼的關鍵在于，當擺上了第N個皇后時，如何表達第N+1個皇后的擺法，當無法擺上時，又該如何回溯到第N-1個皇后上去。當然，該如何停止遞歸，也不能不考慮。         代碼用m_nLast紀錄Play到第幾行了。其實這個變量可以省掉的，只要重新再寫一個Play的輔助函數PlayHelper，其帶有m_nLast的參數，內部遞歸調用自己。但是，在下寫代碼的原則是，能少寫函數就少寫函數，而且用了m_nLast之后，這個程序還有一個新的功能。于是，QueenGame的定義如下。
        私有函數testNewQueen用以最后的位置是否適合第N個皇后居住，分別從縱向和斜向上予以考察，橫向就不用再考慮了，你應該知道WHY的。              激動人心的一刻來臨了，程序終于可以跑起來了。再次審視代碼的時候，我們驚喜地發現QueenGame的Play函數可以遍歷所有的解，只要將main中的if改成while就可以了，非常棒。這都是堅持分離代碼的操作與輸出，并序將八皇后問題封裝成類所帶來的好處。
        顯然，這里采用了深度優先的搜索算法，代碼也可以寫成不用遞歸的形式，還有，這里也可以用寬度優先搜索法，這一切就有待各位嘗試了。
        又，程序采用了一點點匈牙利的命名習慣，這是MFC用久了所沾染上的惡習，沒辦法改了，偶也知道匈牙利命名的種種弊端。

posted on 2011-07-13 19:12 華夏之火 閱讀(3206) 評論(4)  編輯 收藏 引用