一步一步写算法（之八皇后）

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】

    八皇后是一道很具典型性的题目。它的基本要求是这样的：在一个8*8的矩阵上面放置8个物体，一个矩阵点只允许放置一个物体，任意两个点不能在一行上，也不能在一列上，不能在一条左斜线上，当然也不能在一条右斜线上。

    初看到这道题目，大家的第一印象是遍历，但是经过实践之后发现遍历其实不好写，而且复杂度很低。不仅需要遍历8*8*8*8*8*8*8*8*8 = 2^24次数据，还要判断各种条件，实际的计算复杂度还要比较这个高。其实我们仔细看一看，这中间很多的计算其实很多是不需要的，因为如果我们在某一行没有可以插入的数据的话，那么这后面的行其实就不用考虑了。也就是说，我们只有在保证前面 插入的物体都合法有效的情况下，才能进行下一次的物体插入。无谓的遍历只会是无用功。

   那么，我们应该怎么做呢？其实步骤不太难：

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

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

    （3）如果有可以插入的位置， 插入数据。此时再判断是否已经是最后一行，如果是，打印输出返回；反之继续对下一行数据进行试探处理。

    有了上面的步骤，我们就可以书写代码了。老规矩，朋友们可以自己先尝试一下。

    a）定义全局堆栈和打印函数

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"); 

} 

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）添加位置合法性的函数判断

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; 

} 

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; 

        } 

    } 

} 

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;

              }

       }

}

总结：

    （1）迭代递归是编程的难点，需要自己好好实践，看别人写一百遍，不如自己写一遍

    （2）递归的时候务必注意函数return的出口

    （3）递归函数中语句的顺序不要随意更换

    （4）递归函数中注意数据的保存和恢复

    （5）递归函数也要验证，可以用程序验证法，也可以用其他函数的结果来验证