Ｎ皇后问题解法（递归+回朔）-白红宇

Ｎ皇后问题解法（递归+回朔）

阅读量：639 次

发布时间：2019-03-15

本文共 1810 字，大约阅读时间需要 6 分钟。

解决八皇后问题的方法主要有两种：递归解法和回溯解法。以下是两个方法的实现代码及详细说明：

#include 
   
    #include 
    
     #define M 8  // 存在8个皇后bool check(int *c, int k) {    int i = 0;    for (i = k - 1; i >= 0; i--) {        if (c[i] == c[k] || (c[i] - c[k] == i - k) || (c[i] + i == c[k] + k)) {            return false;        }    }    return true;}void display(int *c, int n) {    int i = 0, j = 0;    for (i = 1; i <= n; i++) {        printf("%d  ", c[i]);    }    printf("\n");}void q(int k)  // 递归解法{    int i = 0;    for (i = 1; i <= M; i++) {        c[k] = i;        if (check(c, k)) {            if (k == M)  // 到达最后一层，输出            {                display(c, k);            }            else {                q(k + 1); // 向下搜索            }        }        c[k] = 0;    }}void qt(int k)  // 回溯解法{    while (k >= 1) {        while (c[k] < 0) {            k--;        }        if (k == 1) {            break;        }        int i = c[k - 1], j = k;        k--;        if (i <= j) {            c[k] = c[k - 1];            c[k - 1] = -1;            k++;        }    }}int main(void) {    q(1);  // 非递归    qt(1);  // 递归    return 0;}

详细说明

1. 递归解法

递归解法采用深度优先搜索的方式进行，适用于问题结构分明的情况。具体步骤如下：

建立索引数组：用于存储不同皇后位置的列索引。

递归函数 q(int k)：递归深度为k，依次尝试在第k行放置皇后。
- 放置皇后：遍历各列，尝试将皇后放在当前行的不同列中。
- 检查合法性：调用check函数，判断当前皇后是否与之前放置的皇后产生攻击。
- 递归搜索：如果合法，继续递归处理下一行；否则，尝试下一列。
- 输出结果：当达到第8行时，调用display函数输出当前解。

2. 回溯解法

回溯解法在每一步放置皇后后进行全面检查，剪枝不合法的情况，提高效率。具体步骤如下：

初始化数组：如c[20]，用于存储皇后位置。

递归函数 qt(int k)：从第k行开始尝试放置皇后。
- 搜索上层：寻找上一行的放置位置。
- 回溯检查：在第k行恢复已放置的皇后位置。
- 尝试放置：检查当前列、行和对角线是否合法，并进行递归处理。
- 终止条件：当最上一行也放置好皇后时，说明成功解开谜题。