数据结构之栈与递归的应用（八皇后递归解法）

妖狐艹你老母 2022-05-31 06:16 184阅读 0赞

前面几节讲述了递归的一般应用，本节讲一下递归的另一个重要的应用场合回溯算法，利用函数调用的活动对象可以保存回溯算法中重要的变量信息 。

**递归与回溯**

递归在程序设计中也常用于需要回溯算法的场合。  
回溯算法的基本思想：  
1.从问题的某一种状态出发，搜索可以到达的所有状态；  
2，当某个状态到达后，可向前回退，并继续搜索其它可达状态；  
3.当所有状态都到达后，回溯算法结束。  
程序设计中可利用函数的活动对象保存回溯算法的状态数据，因此可以利用递归完成回溯算法。 对于回溯算法我们可以研究一个经典的问题，八皇后问题：在一个8×8国际象棋盘上，有8个皇后，每个皇后占一格；要求皇后间不会出现相互“攻击”的现象，即不能有两个皇后处在同一行、同一列或同一对角线上。

![70][]

要想实现此算法，首先得初始化一个8\*8的棋盘，代码如下：

#define N 8

// 定义一个二维数组，模拟棋盘
    static char board[N+2][N+2];
    
    void init()
    {
        int i = 0;
        int j = 0;
        // #号代表棋盘边沿
        for(i=0; i<N+2; i++)
        {
            board[0][i] = '#';
            board[N+1][i] = '#';
            board[i][0] = '#';
            board[i][N+1] = '#';
        }
        // 棋盘方格用空格代替
        for(i=1; i<=N; i++)
        {
            for(j=1; j<=N; j++)
            {
                board[i][j] = ' ';
            }
        }
    }

棋盘光模拟出来还不行，还需要将其打印出来：

void display()
    {
        int i = 0;
        int j = 1;
        
        for(i=0; i<N+2; i++)
        {
            for(j=0; j<N+2; j++)
            {
                printf("%c", board[i][j]);
            }
            
            printf("\n");
        }
    }

打印结果如图：

![70 1][]

至此，棋盘已经模拟出来并且可以显示了，我们就要寻找皇后的放置位置，在这之前得检测指定位置是否可以放置皇后，查找的方法：

１.查找该位置的前一行的当前列及左右对角线是否有皇后；

２.如果有该位置就不可以防止皇后，否则，可以放置皇后。

图示如下（黄底红字的就是需要检测的位置）：

![70 2][]

实现代码如下：

typedef struct _tag_Pos
    {
        int ios;
        int jos;
    } Pos;

// 定义一个结构体数组，存放寻找可否放置皇后位置偏移量
    static Pos pos[] = { {-1, -1}, {-1, 0},{-1, 1} };
    
    //　可以放置皇后返回１，否则返回０
    int check(int i, int j)
    {
        int ret = 1;
        int p = 0;
        
        for(p=0; p<3; p++)
        {
            int ni = i;
            int nj = j;
            //在棋盘范围内，不等于×号的位置表示可以放置皇后
            while( ret && (board[ni][nj] != '#') )
            {
                ni = ni + pos[p].ios;
                nj = nj + pos[p].jos;
                
                ret = ret && (board[ni][nj] != '*');
            }
        }
        
        return ret;
    }

寻找皇后方法的算法如下：

1.初始化：i = 1  
2. 初始化：j = 1  
3. 从第i行开始，恢复j的当前值，判断第j个位置  
a. 位置j可放入皇后：标记位置(i, j)， i++，转步骤2  
b. 位置j不可放入皇后：j++, 转步骤a  
c. 当j>8时，i--，转步骤3

4. 结束：第8行有位置可放入皇后 ，打印棋盘现状。

代码如下：

static int count = 0;

void find(int i)
    {
        int j = 0;
        
        if( i > N )
        {
            count++;
            
            printf("Solution: %d\n", count);
            
            display();
            
            printf("按回车键打印其他摆放方式");
            
            getchar();
        }
        else
        {
            for(j=1; j<=N; j++)
            {
                if( check(i, j) )
                {
                    board[i][j] = '*';
                    
                    find(i+1);
                    
                    board[i][j] = ' ';
                }
            }
        }
    }

int main()
    {
        init();
        find(1);
        
        return 0;
    }

运行结果如下：

![70 3][]

[递归应用C语言实现][C]

[70]: /images/20220531/9c36ecc9a1c9412d9a786432a2a089af.png
[70 1]: /images/20220531/a088db557ac544afb99cfca2a3895fc3.png
[70 2]: /images/20220531/176715e522d1467eb774528267708ad4.png
[70 3]: /images/20220531/27599a8dfc4a4e2bbe578fe9cafa9c8c.png
[C]: http://download.csdn.net/download/u014754841/10246751