回溯法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来丢弃该解，即回溯并尝试另一种可能。
回溯法通常用递归方式实现，它是一种选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术称为“回溯法”。
回溯法的基本思想：
- 路径：已经做出的选择。
- 选择列表：当前可以做的选择。
- 结束条件：到达决策树底层，无法再做选择的条件。
回溯法的框架：
void backtrack(路径, 选择列表) {
if (满足结束条件) {
添加结果;
return;
}
for (选择 : 选择列表) {
做选择;
backtrack(路径, 选择列表);
撤销选择;
}
}
回溯法适用于解决的问题包括但不限于：
- 组合问题：N个数里面按一定规则找出k个数的组合方式。
- 排列问题：N个数按一定规则全排列，有无重复数。
- 切割问题：一个字符串按一定规则有几种切割方式。
- 子集问题：一个N个数的集合里有多少符合条件的子集。
- 棋盘问题：N皇后、解数独等。
回溯法的关键在于：不断在每一层试错，如果发现当前选择不符合条件，就回退到上一层，再次尝试其他选项，直到找到所有符合条件的解。
分治法解决n皇后问题
n皇后问题是一个经典的回溯法应用问题，其目标是在n×n的棋盘上放置n个皇后，使得它们不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。以下是解决n皇后问题的C代码实现：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 8 // 定义棋盘大小和皇后数量
int board[N][N]; // 棋盘，0表示空，1表示放置了皇后
// 打印解决方案
void printSolution() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf(" %d ", board[i][j]);
printf("\n");
}
printf("\n");
}
// 检查在给定位置放置皇后是否安全
bool isSafe(int row, int col) {
int i, j;
// 检查这一列
for (i = 0; i < row; i++)
if (board[i][col])
return false;
// 检查左上对角线
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
// 检查右上对角线
for (i = row, j = col; i >= 0 && j < N; i--, j++)
if (board[i][j])
return false;
return true;
}
// 递归函数来解决n皇后问题
bool solveNQUtil(int row) {
// 如果所有皇后都放置好了
if (row >= N)
return true;
// 尝试在当前行的所有列中放置皇后
for (int i = 0; i < N; i++) {
// 检查是否可以在board[row][i]放置皇后
if (isSafe(row, i)) {
// 在board[row][i]放置皇后
board[row][i] = 1;
// 递归到下一行
if (solveNQUtil(row + 1))
return true;
// 如果放置皇后在board[row][i]导致解决方案失败，则移除皇后
board[row][i] = 0; // 回溯
}
}
// 如果当前行找不到一个位置放置皇后，则返回false
return false;
}
// 解决n皇后问题的函数
bool solveNQ() {
// 初始化棋盘
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
board[i][j] = 0;
if (!solveNQUtil(0)) {
printf("解决方案不存在");
return false;
}
// 打印解决方案
printSolution();
return true;
}
// 主函数
int main() {
solveNQ();
return 0;
}
这段代码首先定义了一个N×N的棋盘，然后通过递归和回溯的方式尝试在棋盘上放置皇后。isSafe函数用于检查在给定位置放置皇后是否安全。solveNQUtil是一个递归函数，它尝试在每一行放置一个皇后，并通过回溯法寻找所有可能的解决方案。如果找到一个解决方案，solveNQ函数将打印出棋盘的一个解决方案。
