一步一步寫算法（之八皇後）

【 聲明：版權所有，歡迎轉載，請勿用于商業用途。  聯系信箱：feixiaoxing @163.com】

    八皇後是一道很具典型性的題目。它的基本要求是這樣的：在一個8*8的矩陣上面放置8個物體，一個矩陣點隻允許放置一個物體，任意兩個點不能在一行上，也不能在一列上，不能在一條左斜線上，當然也不能在一條右斜線上。

    初看到這道題目，大家的第一印象是周遊，但是經過實踐之後發現周遊其實不好寫，而且複雜度很低。不僅需要周遊8*8*8*8*8*8*8*8*8 = 2^24次資料，還要判斷各種條件，實際的計算複雜度還要比較這個高。其實我們仔細看一看，這中間很多的計算其實很多是不需要的，因為如果我們在某一行沒有可以插入的資料的話，那麼這後面的行其實就不用考慮了。也就是說，我們隻有在保證前面 插入的物體都合法有效的情況下，才能進行下一次的物體插入。無謂的周遊隻會是無用功。

   那麼，我們應該怎麼做呢？其實步驟不太難：

    （1）在第n行尋找可以插入的位置，中間涉及到位置合法性的判斷

    （2）如果沒有可以插入的位置，傳回

    （3）如果有可以插入的位置， 插入資料。此時再判斷是否已經是最後一行，如果是，列印輸出傳回；反之繼續對下一行資料進行試探處理。

    有了上面的步驟，我們就可以書寫代碼了。老規矩，朋友們可以自己先嘗試一下。

    a）定義全局堆棧和列印函數

    b）添加位置合法性的函數判斷

    c） 八皇後周遊

總結：

    （1）疊代遞歸是程式設計的難點，需要自己好好實踐，看别人寫一百遍，不如自己寫一遍

    （2）遞歸的時候務必注意函數return的出口

    （3）遞歸函數中語句的順序不要随意更換

    （4）遞歸函數中注意資料的儲存和恢複

    （5）遞歸函數也要驗證，可以用程式驗證法，也可以用其他函數的結果來驗證

ps:

    下面是完整的代碼，大家可以直接儲存成queue.cpp，直接編譯運作即可。可以列印出所有92種情況，