回溯算法是一种可以找到全部或部分解的通用算法。跟暴力穷举法相比，由于可以对搜索域剪枝，因此效率要高。所谓回溯，就是走到某处后如果发现此路不通，会立即退回到上一步，而不是像暴力法那样仍不管不顾地都试一次。因此，回溯法是一种选优搜索法，又称为试探法。

回溯算法的编写格式：

boolean backtrack(candidate) {
    // 递归终止条件
    if (isSolution(candidate)) {
        output(solution);
        return true;
    }

    // 标记当前结点（比如把当前结点标记在路径里）
    place(candidate);

    // 遍历和尝试所有下一级的结点
    for (nextCandidate : listOfCandidates) {
        // 剪枝：对于不合适的结点，直接跳过
        if (isValid(nextCandidate)) {
            // 继续深入到下一层。如果最终能找到解，返回；否则尝试下一个下级结点
            if (backtrack(nextCandidate)) {
                return true;
            }
        }
    }

    // 清除当前结点的标记（比如把当前结点从路径上移除，这意味着从其他结点还能继续来这里）
    remove(candidate);
    return false;
}

说明：

• backtrack函数是一个调用自己的递归函数，所以要有终止递归的条件
• 里面有一个循环，用于尝试所有下一级的结点。比如迷宫问题，当走到了某点后，继续尝试相邻的三个结点（前一个结点除外）。循环里应该有剪枝，避免不必要的递归调用开销。
• 经常需要标记当前结点，并在尝试完从这里开始的所有可能性后清除标记。（比如，不要重复访问已标记的地方）

例题：N皇后问题（八皇后问题）

暴力穷举法：把第一个皇后放置在第一行的每个位置，然后搜索所有的解（尝试把第二个皇后放在其他所有位置，再尝试把第三个皇后放在其他所有位置……）。其实这已经不太“暴力”了，因为完全的“暴力搜索”应该是把第一个皇后也放在棋盘的所有位置，最后再去掉重复的解。

回溯法：把第一个皇后放在第一行的每个位置，由于第一行肯定不能再放置皇后，因此，尝试把第二个皇后放在第二行的每个位置，判断一下是否满足条件，把不满足条件的跳过，然后再在第三行尝试放置第三个皇后……

进一步优化：保存一个长度为N的数组，在某一列放置过皇后的话，就把相应的数组位置设置为true。这样，在下一行放置下一个皇后时，先跳过所有置为true的各列，然后再判断某位置是否符合条件（因为还有斜向的攻击）。在退出前从数组中把其列标志清除。

总结：女人真可怕……我本人的话，性格应该跟“车”比较相似。