【重拾C语言】十二、C语言程序开发（穷举与试探——八皇后问题）

Qomolangma

发布于 2024-07-30 08:54:20

750

发布于 2024-07-30 08:54:20

文章被收录于专栏：C语言深度学习

前言

八皇后问题是一个经典的计算机科学问题，要求在一个8×8的棋盘上放置8个皇后，使得它们互相之间不能攻击到对方。这个问题可以通过穷举和试探的方法来解决。

穷举法是一种解决问题的方法，它通过尝试所有可能的解决方案来找到满足条件的解。这种方法适用于解空间较小的问题，例如八皇后问题、0/1 背包问题等。在 C 语言中，我们可以通过编写循环来遍历所有可能的解决方案，并判断是否满足条件。
试探法是一种基于经验或启发式规则的方法，它通过逐步搜索解空间来找到满足条件的解。这种方法适用于解空间较大或问题具有启发式特征的情况。在 C 语言中，我们可以通过编写递归或循环来实现试探法，例如深度优先搜索（DFS）或广度优先搜索（BFS）。

十二、C语言程序开发

12.1~3 自顶向下、逐步求精；结构化程序设计原则；程序风格

【重拾C语言】十二、C语言程序开发（自顶向下、逐步求精；结构化程序设计原则；程序风格）_QomolangmaH的博客-CSDN博客

https://blog.csdn.net/m0_63834988/article/details/133825033?spm=1001.2014.3001.5502 在C语言程序开发中，可以使用自顶向下、逐步求精的方法解决问题，遵循结构化程序设计原则，同时注重良好的程序风格，这可以帮助开发者编写可读性强且易于维护的代码。

12.4 八皇后——穷举与试探

12.4.1 穷举法

穷举法（Exhaustive Search）是一种常见的算法设计方法，用于在给定的搜索空间中尝试所有可能的解决方案，以找到满足特定条件的解。

在C语言中，可以使用循环结构和条件语句来实现穷举法。一般步骤如下：
- 定义问题的搜索空间和解的表示方式。
- 使用循环结构遍历搜索空间中的所有可能解。
- 对于每个可能解，使用条件语句判断是否满足问题的条件。
- 如果满足条件，执行相应的操作，例如输出结果或保存解决方案。
- 继续循环，直到遍历完整个搜索空间。
示例：寻找一个整数的平方根

#include <stdio.h>

int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);

    int i;
    for (i = 0; i <= num; i++) {
        if (i * i == num) {
            printf("Square root of %d is %d\n", num, i);
            break;
        }
    }

    if (i > num) {
        printf("No square root found for %d\n", num);
    }

    return 0;
}

通过循环遍历从0到输入的数字，逐个尝试每个可能的平方根。如果找到一个平方根，就输出结果并结束循环。如果循环结束后仍然没有找到平方根，就输出相应的提示信息。

输出：

这只是一个简单的示例，实际上，穷举法可以应用于各种问题，包括组合优化、密码破解等。但是需要注意的是，穷举法的计算复杂度通常较高，随着搜索空间的增大，计算时间会呈指数级增长。因此，在实际应用中，需要根据问题的规模和要求，权衡计算时间和解的准确性。

12.4.2 试探法

试探法（Backtracking）是一种基于经验或启发式规则的方法，它通过逐步搜索解空间来找到满足条件的解。通常通过递归的方式进行搜索，尝试每一种可能的选择，并在满足条件的情况下继续向下搜索，如果不满足条件，则回溯到上一步选择的状态，重新选择其他可能的路径。

在C语言中，可以使用递归函数和条件语句来实现试探法。一般步骤如下：
- 定义问题的搜索空间和解的表示方式。
- 编写一个递归函数，在每一步选择中进行尝试，并根据条件判断是否满足问题的要求。
- 如果满足条件，执行相应的操作，例如输出结果或保存解决方案。
- 继续递归调用函数，进入下一步选择。
- 如果不满足条件，回溯到上一步选择的状态，重新选择其他可能的路径。
- 继续递归调用函数，进行下一步尝试。
示例：计算给定数字的阶乘

#include <stdio.h>

int factorial(int n) {
    // 基本情况：当 n 为 0 或 1 时，阶乘为 1
    if (n == 0 || n == 1) {
        return 1;
    }
    // 递归情况：调用自身来计算 n 的阶乘
    else {
        return n * factorial(n - 1);
    }
}

int main() {
    int n = 5;
    int result = factorial(n);
    printf("%d 的阶乘为 %d\n", n, result);
    return 0;
}

输出：

试探法可以应用于各种问题，如组合优化、图的遍历、八皇后问题等。通过不断地试探和回溯，可以找到所有可能的解决方案。请注意，试探法的计算复杂度也可能较高，特别是在搜索空间较大时。因此，在实际应用中，需要谨慎选择搜索策略和剪枝技巧，以提高算法的效率。同时，合理设计问题的表示方式和条件判断，可以帮助减少搜索空间，加快求解过程。

12.4.3 穷举与试探（八皇后问题）-递归实现

穷举法是一种简单但低效的解决方法，它通过尝试所有可能的皇后布局来找到满足条件的解。具体步骤如下：

从第一行开始，依次尝试在每一列放置皇后。
检查当前的布局是否满足没有皇后互相攻击的条件。
如果满足条件，继续到下一行，重复上述步骤。
如果在某一行无法找到合适的位置放置皇后，回溯到上一行，尝试下一个列。
当放置完最后一行的皇后并且满足条件时，找到一个解。

穷举法的缺点是需要尝试大量的组合，因此在较大的棋盘上效率较低。

#include <stdio.h>

#define N 8

void printBoard(int board[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%c ", board[i][j] ? 'Q' : '.');
        }
        printf("\n");
    }
    printf("\n");
}

int isSafe(int board[N][N], int row, int col) {
    // 检查当前位置的左侧是否有皇后
    for (int i = 0; i < col; i++) {
        if (board[row][i]) {
            return 0;
        }
    }

    // 检查当前位置的左上方是否有皇后
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j]) {
            return 0;
        }
    }

    // 检查当前位置的左下方是否有皇后
    for (int i = row, j = col; i < N && j >= 0; i++, j--) {
        if (board[i][j]) {
            return 0;
        }
    }

    return 1;
}
int count = 0; // 全局变量用于计数解的数量
void solveNQueens(int board[N][N], int col) {
    // 所有皇后都放置完毕，打印解决方案，增加解的数量并返回
    if (col == N) {
        printBoard(board);
        count++;
        return;
    }

    // 逐行尝试放置皇后
    for (int i = 0; i < N; i++) {
        if (isSafe(board, i, col)) {
            // 放置皇后
            board[i][col] = 1;

            // 递归地尝试下一列
            solveNQueens(board, col + 1);

            // 回溯，撤销当前位置的皇后
            board[i][col] = 0;
        }
    }
}

int main() {
    int board[N][N] = {0};

    solveNQueens(board, 0);
    printf("Number of solutions: %d\n", count);
    return 0;
}

输出：