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

初看到這道題目，大家的第一印象是遍歷，但是經(jīng)過實踐之后發(fā)現(xiàn)遍歷其實不好寫，而且復(fù)雜度很低。不僅需要遍歷888888888 = 2^24次數(shù)據(jù)，還要判斷各種條件，實際的計算復(fù)雜度還要比較這個高。其實我們仔細看一看，這中間很多的計算其實很多是不需要的，因為如果我們在某一行沒有可以插入的數(shù)據(jù)的話，那么這后面的行其實就不用考慮了。也就是說，我們只有在保證前面 插入的物體都合法有效的情況下，才能進行下一次的物體插入。無謂的遍歷只會是無用功。

那么，我們應(yīng)該怎么做呢？其實步驟不太難：

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

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

（3）如果有可以插入的位置， 插入數(shù)據(jù)。此時再判斷是否已經(jīng)是最后一行，如果是，打印輸出返回；反之繼續(xù)對下一行數(shù)據(jù)進行試探處理。

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

a）定義全局堆棧和打印函數(shù)

static int gEightQueen[8] = {0};
static int gCount = 0;

void print()
{
    int outer;
    int inner;

    for(outer = 0; outer <8; outer ++){
        for(inner = 0; inner < gEightQueen[outer]; inner ++)
            printf("* ");

        printf("# ");

        for(inner = gEightQueen[outer] + 1; inner < 8; inner ++)
            printf("* ");

        printf("n");
    }

    printf("=====================================n");
}

b）添加位置合法性的函數(shù)判斷

int check_pos_valid(int loop, int value)
{
    int index;
    int data;

    for(index = 0; index < loop; index ++){
        data = gEightQueen[index];

        if(value == data)
            return 0;

        if((index + data) == (loop + value))
            return 0;

        if((index - data) == (loop - value))
            return 0;
    }

    return 1;
}

c） 八皇后遍歷

void eight_queen(int index)
{
    int loop;

    for(loop = 0; loop < 8; loop++){
        if(check_pos_valid(index, loop)){
            gEightQueen[index] = loop;

            if(7 == index){
                gCount ++, print();
                gEightQueen[index] = 0;
                return;
            }

            eight_queen(index + 1);
            gEightQueen[index] = 0;
        }
    }
}

總結(jié)：

（1）迭代遞歸是編程的難點，需要自己好好實踐，看別人寫一百遍，不如自己寫一遍

（2）遞歸的時候務(wù)必注意函數(shù)return的出口

（3）遞歸函數(shù)中語句的順序不要隨意更換

（4）遞歸函數(shù)中注意數(shù)據(jù)的保存和恢復(fù)

（5）遞歸函數(shù)也要驗證，可以用程序驗證法，也可以用其他函數(shù)的結(jié)果來驗證

ps:

下面是完整的代碼，大家可以直接保存成queue.cpp，直接編譯運行即可?？梢源蛴〕鏊?2種情況，

#include 
using namespace std;

static int gEightQueen[8] = {0};
static int gCount = 0;

void print()
{
    int outer;
    int inner;

    for(outer = 0; outer <8; outer ++){
        for(inner = 0; inner < gEightQueen[outer]; inner ++)
            printf("* ");

        printf("# ");

        for(inner = gEightQueen[outer] + 1; inner < 8; inner ++)
            printf("* ");

        printf("n");
    }

    printf("=====================================n");
}

int check_pos_valid(int loop, int value)
{
    int index;
    int data;

    for(index = 0; index < loop; index ++){
        data = gEightQueen[index];

        if(value == data)
            return 0;

        if((index + data) == (loop + value))
            return 0;

        if((index - data) == (loop - value))
            return 0;
    }

    return 1;
}

void eight_queen(int index)
{
    int loop;

    for(loop = 0; loop < 8; loop++){
        if(check_pos_valid(index, loop)){
            gEightQueen[index] = loop;

            if(7 == index){
                gCount ++, print();
                gEightQueen[index] = 0;
                return;
            }

            eight_queen(index + 1);
            gEightQueen[index] = 0;
        }
    }
}

int main(int argc, char* argv[])
{
    eight_queen(0);
    printf("total = %dn", gCount);
    return 1;
}