回溯法与经典八皇后问题
- 算法
- 2024-07-05
- 285热度
- 0评论
基本概念
回溯法,其实就是一个“试错”的过程。就像你在解一个复杂的拼图或者迷宫游戏,你会尝试不同的路径,如果发现当前路径走不通,或者不符合条件,你就会退回到上一个分叉点,然后选择另一条路继续尝试。
在编程中,回溯法常用于解决组合问题、搜索问题、决策问题等。它的核心思想是:
定义问题的解空间:这就像是把迷宫的所有可能路径都列出来。
选择搜索策略:决定先尝试哪条路径。比如,你可以从起点开始,每次选择一条没走过的路。
进行剪枝:如果当前路径已经确定不可能达到目标,就及时放弃,不再继续搜索。这就像是在迷宫中,如果你发现前面是堵墙,那你就不会再往前走了。
举个例子,如果你用回溯法解决“八皇后”问题(在8x8的棋盘上放置八个皇后,使得任何一个皇后都不能攻击到其他的皇后,即任意两个皇后都不能处于同一行、同一列或同一斜线上),你会这样操作:
放置第一个皇后在第一行的某一列。
尝试放置第二个皇后在第二行,检查是否与第一个皇后冲突。
如果冲突,就退回第一步,换一列放置第一个皇后。
如果不冲突,继续放置第三个皇后,并检查冲突。
以此类推,直到所有皇后都放置好,或者确定无法放置。
在这个过程中,如果某个皇后放不下,就会退回之前的步骤,重新选择位置。这种不断尝试、不断回溯的过程,就是回溯法的核心。
八皇后问题
问题描述
在8×8的国际象棋棋盘上放置八个皇后,使得它们互不攻击。具体地说,就是任意两个皇后都不能处于同一行、同一列或同一斜线上。目标是找出所有可能的摆放方案。
解题步骤
初始化棋盘:创建一个8x8的棋盘,用于表示皇后的位置。可以使用一个一维数组来表示棋盘,其中board[i]表示第i行皇后的列号(0到7)。
定义回溯函数:这个函数将尝试在当前行的每一列放置一个皇后,并递归地调用自身来放置下一行的皇后。
检查冲突:在放置一个皇后之前,需要检查它是否与已放置的皇后冲突。这包括检查同一列、主对角线和副对角线上是否有皇后。
回溯:如果当前位置无法放置皇后(即存在冲突),需要回溯到上一行,并移动那一行的皇后到下一列。
打印解:当成功放置了八个皇后时,打印出当前棋盘的一个解。
主函数:在主函数中,调用回溯函数来开始搜索解空间。
代码实现
#include <stdio.h>
#include <stdbool.h>
#define SIZE 8
int board[SIZE]; // 棋盘,board[i]表示第i行皇后的列号
// 检查是否可以在(row, col)位置放置皇后
bool is_valid(int row, int col) {
for (int i = 0; i < row; i++) {
if (board[i] == col || // 检查列
board[i] - i == col - row || // 检查主对角线
board[i] + i == col + row) { // 检查副对角线
return false;
}
}
return true;
}
// 回溯函数,尝试放置皇后
void place_queen(int row) {
if (row == SIZE) { // 所有皇后都放置完毕,打印棋盘
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
printf("%2s", (board[i] == j) ? "Q " : ". ");
}
printf("\n");
}
printf("\n");
return;
}
for (int col = 0; col < SIZE; col++) {
if (is_valid(row, col)) { // 检查当前位置是否可以放置皇后
board[row] = col; // 放置皇后
place_queen(row + 1); // 递归放置下一行的皇后
}
}
}
int main() {
place_queen(0); // 从第一行开始放置皇后
return 0;
}
在上面的代码中,is_valid 函数用于检查给定位置是否可以放置皇后,place_queen 函数是一个递归函数,用于尝试在当前行的每一列放置皇后,并递归地调用自身以放置下一行的皇后。当所有皇后都成功放置时,打印出当前的棋盘状态。
算法分析
时间复杂度
八皇后问题中,棋盘的大小是固定的(8x8)。在最坏的情况下,需要检查棋盘上每一个位置是否可以放置皇后。由于棋盘有8行,每一行有8列,所以总共有 8^8 = 16,777,216 种可能的配置。因此,在最坏的情况下,时间复杂度为 O(8^n),其中 n 是棋盘的大小(在这个问题中是8)。
其实实际的执行时间通常会比这个上界要小得多,因为回溯算法会在找到解或确定当前路径不可行时提前停止搜索。因此虽然最坏情况下的时间复杂度很高,但实际运行时间可能要好得多。
空间复杂度
空间复杂度是评估算法执行时所需额外空间的度量。算法使用了一个大小为 SIZE 的数组 board 来存储棋盘的状态,以及几个循环变量和递归调用栈。
数组 board 的大小是固定的(8个整数),因此它的空间需求是常数。循环变量(如 i, j, col)通常也只需要固定大小的内存。
主要的空间开销来自于递归调用栈。在回溯过程中,每一层递归调用都会占用一定的栈空间。由于最多有 SIZE(8)层递归(对应于棋盘的每一行),所以递归调用栈的深度也是常数。
综上所述,该算法的空间复杂度是 O(1),即常数空间复杂度。算法的空间需求不随输入规模的增长而增长。
求解数独
问题描述
数独(Sūdoku),一种数学游戏。数独的游戏规则是在一个9x9的盘面上,每一行、每一列以及每一个由3x3小格子组成的粗线宫内,都必须包含数字1至9,且每个数字在每一行、每一列和每一个宫内都只能出现一次。游戏开始时,盘面上会给出一些已知的数字作为解题的线索,玩家的目标则是根据这些线索,通过逻辑推理和填数技巧,将剩余空格填满,使得整个盘面满足上述规则。
解题步骤
初始化数独网格:
创建一个9x9的二维数组来代表数独网格。
定义is_valid函数:
此函数用于检查在当前位置(row, col)放置数字num是否有效。
函数遍历当前行、当前列以及当前3x3子网格,检查是否存在与num相同的数字。
如果存在,则返回false,表示放置无效;否则返回true。
定义solveSudoku函数:
这是主要的回溯函数,用于解决数独问题。
它使用两个参数:row和col,表示当前要填充的网格位置。
函数首先检查是否已经遍历完整个网格(即col等于9且row也等于9),如果是,则返回true,表示找到了一个有效的解。
如果当前位置(row, col)已经有数字,则移动到下一个位置(row, col+1)。
如果当前位置为空(即没有数字),则尝试从1到9的数字,看哪个数字可以放置在当前位置。
对于每个尝试的数字,先检查是否有效(使用is_valid函数),如果有效,则放置该数字并递归地尝试下一个位置。
如果递归调用返回true,则表示找到一个有效解,直接返回true。
如果递归调用返回false,则表示当前尝试的数字不合适,需要回溯,即将当前位置的数字置为0,并尝试下一个数字。
如果尝试了1到9的所有数字都不合适,则返回false,表示当前分支无解。
代码实现
#include <stdio.h>
#include <stdbool.h>
#define SIZE 9
void printSudoku(int grid[SIZE][SIZE]) {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
printf("%2d ", grid[i][j]);
}
printf("\n");
if ((i + 1) % 3 == 0) {
printf("-------\n");
}
}
}
bool is_valid(int grid[SIZE][SIZE], int row, int col, int num) {
for (int i = 0; i < SIZE; i++) {
if (grid[row][i] == num) return false; // 检查行
if (grid[i][col] == num) return false; // 检查列
if (grid[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num) return false; // 检查3x3的宫格
}
return true;
}
bool solveSudoku(int grid[SIZE][SIZE], int row, int col) {
if (row == SIZE) return true; // 所有格子都填完了
if (col == SIZE) { // 当前行填完,填下一行
row++;
col = 0;
}
if (grid[row][col] != 0) { // 当前格子已经有数字了,填下一个格子
return solveSudoku(grid, row, col + 1);
}
for (int num = 1; num <= SIZE; num++) {
if (is_valid(grid, row, col, num)) {
grid[row][col] = num; // 尝试放置数字
if (solveSudoku(grid, row, col + 1)) {
return true; // 递归调用成功,返回true
}
grid[row][col] = 0; // 回溯,尝试下一个数字
}
}
return false; // 尝试完所有数字都不合适,返回false
}
int main() {
int grid[SIZE][SIZE] = {
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9}
};
if (solveSudoku(grid, 0, 0)) {
printSudoku(grid);
} else {
printf("数独无解\n");
}
return 0;
}
is_valid函数用于检查在当前位置(row, col)放置数字num是否有效。solveSudoku函数使用回溯法尝试填充数独网格,并返回是否找到解。
main函数初始化数独网格,并调用solveSudoku函数开始求解。如果找到解,则打印数。
算法分析
时间复杂度
时间复杂度主要取决于搜索树的大小,这取决于数独的填充程度和可能的解的数量。在最坏的情况下,需要尝试所有可能的数字组合,这会导致指数级的时间复杂度。然而,实际的数独问题通常不会达到这种最坏情况,因为有效的剪枝(即is_valid函数的检查)会大大减少需要探索的搜索空间。
空间复杂度
空间复杂度主要由递归调用栈和存储数独网格本身所需的空间决定。由于数独网格是固定大小的(9x9),因此存储网格本身的空间是常数。但递归调用栈的深度取决于搜索树的深度,在复杂的数独问题中,其深度可能会相当大。