huaxiazhihuo

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

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

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