回溯法 (Backtracking)

回溯法是一个通用的算法，能够找到一些计算问题的所有解， 通常是一些满足约束问题。 通过遍历的方法寻找解，不断深入搜索，如果确定这部分不可能有解，则放弃这部份的搜索， 继续下一部分的搜索

回溯法的算法本质是：n 叉树的遍历

递归版本

类似对 n 叉树进行遍历，且遍历起始编号为 0. 在遍历中加入约束与限界，以此确定一些子树不需要遍历

大致代码如下，以及一些解释：

• data 需要用到的数据
• data->depth 需要遍历的深度
• depth 遍历的当前深度
• solution(data) 处理得到的解
• path[depth] 记录了根到当前节点的路径，可替换为其它需要在各个遍历节点处理的代码
• constraint(data, depth) 约束函数，满足约束返回 TRUE, 否则返回 FALSE
• bound(data, depth) 限界函数，满足减枝条件返回 TRUE, 否则返回 FALSE

void backtracking_iter(struct data *data, int depth)
{
    if (data->depth == depth) {
        solution(data);
        return;
    }

    for (int i = 0; i < data->depth; i++) {
        data->path[depth] = i;
        if (constraint(data, depth) == TRUE && bound(data, depth) == FALSE) {
            backtracking(data, depth + 1);
        }
    }
}

void backtracking(struct data *data)
{
    backtracking_iter(data, 0);
}