八皇後實在太有名了，我也就不廢話了。利用回溯算法，不難寫出其代碼，相信各位同學也都干過了。那這篇文章還有何新意呢？難道是向各位展示在下的代碼要比各位好，絕對不是。只因用C++寫代碼的時候，很容易就陷入各種細節的糾纏中，必須牢記大刀闊斧地砍除無關緊要的細節，始終堅持用C++清晰地表達解決問題的思路，嚴格遵守單一職責的規則，集中精力解決問題，不賣弄半點花巧。這是在下努力的一種嘗試。
八皇後的解決方案，相信大家也都知道了，請恕我直奔主題了。
由於長年累月沉浸於C++中，中毒已經甚深了，碰到任何問題，都條件反射地將其大御八塊，然後用CLASS來組織。於是，非常自然的，我決定用類QueenGame來表示八皇後這個游戲，用Play來擺弄出一個安全棋局。當然，不用CLASS，也依然可以寫出清晰的代碼，但是，感覺總是很不習慣。於是，main起來就非常簡單了。 int main()
{
QueenGame game(8);
if(game.Play())
DisplayQueen(game);
return 0;
}
為何不讓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的初版如下：
class QueenGame
{
public:
enum {MAX_QUEEN_COUNT = 10};
QueenGame(int queenCount)；
public:
int GetQueenCount()const；
bool Play();
private:
int m_QueenPos[MAX_QUEEN_COUNT];
};
有了這些信息，就可以開始實作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這個小細節上耗費一丁點精力了，我的精力應該集中在原本要解決的問題上。
void DisplayQueen(const QueenGame& game)
{
using namespace std;
int count = game.GetQueenCount();
for (int n = 0; n<count; n++)
{
for (int i=1; i<=count; i++)
{
if (game.m_QueenPos[n] == i)
cout << "Q";
else
cout << "+";
}
cout << endl;
}
cout << endl;
} 好了，做足准備工作了，終於來到問題核心了，實作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個皇後上去。當然，該如何停止遞歸，也不能不考慮。 bool QueenGame::Play()
{
int& lastPos = m_QueenPos[m_nLast];
while (++lastPos <= m_nQueenCount)
{
if (testNewQueen())
break;
}
if (lastPos > m_nQueenCount)
{
m_nLast--;
if (m_nLast<=0 && m_QueenPos[0] > m_nQueenCount)
return false;
}
else
{
if (m_nLast+1 == m_nQueenCount)
return true;
m_nLast++;
m_QueenPos[m_nLast] = 0;
}
return Play();
}
代碼用m_nLast紀錄Play到第幾行了。其實這個變量可以省掉的，只要重新再寫一個Play的輔助函數PlayHelper，其帶有m_nLast的參數，內部遞歸調用自己。但是，在下寫代碼的原則是，能少寫函數就少寫函數，而且用了m_nLast之後，這個程序還有一個新的功能。於是，QueenGame的定義如下。
class QueenGame
{
public:
enum {MAX_QUEEN_COUNT = 10};
QueenGame(int queenCount)
{
assert(queenCount > 0 && queenCount <= MAX_QUEEN_COUNT );
m_nQueenCount = queenCount;
m_nLast = 0;
m_QueenPos[m_nLast] = 0;
}
public:
int GetQueenCount()const
{
return m_nQueenCount;
}
bool Play();
int m_QueenPos[MAX_QUEEN_COUNT];
private:
bool testNewQueen();
int m_nQueenCount;
int m_nLast;
}; 私有函數testNewQueen用以最後的位置是否適合第N個皇後居住，分別從縱向和斜向上予以考察，橫向就不用再考慮了，你應該知道WHY的。 bool QueenGame::testNewQueen()
{
int lastPos = m_QueenPos[m_nLast];
for (int i=0; i<m_nLast; i++)
{
if (m_QueenPos[i] == lastPos || abs(m_QueenPos[i]-lastPos)==(m_nLast-i))
return false;
}
return true;
}
激動人心的一刻來臨了，程序終於可以跑起來了。再次審視代碼的時候，我們驚喜地發現QueenGame的Play函數可以遍歷所有的解，只要將main中的if改成while就可以了，非常棒。這都是堅持分離代碼的操作與輸出，並序將八皇後問題封裝成類所帶來的好處。
顯然，這裡采用了深度優先的搜索算法，代碼也可以寫成不用遞歸的形式，還有，這裡也可以用寬度優先搜索法，這一切就有待各位嘗試了。
又，程序采用了一點點匈牙利的命名習慣，這是MFC用久了所沾染上的惡習，沒辦法改了，偶也知道匈牙利命名的種種弊端。
