概念

回溯法又叫试探法，literally，搜索过程中碰到死路径的时候回溯到先前的某个状态尝试下一条路径，

步骤

定义一个解空间，每一个解即为每一步采用的方法
利用适于搜索的方法组织解空间
深度优先法 (depth first) 搜索解空间

第三步可以用盲目 (blind) 搜索的方法。相对应的也有启发式 (heuristic) 的搜索方法，即考虑问题的特有性质，选用合适的规则从而提高搜索的效率。引用回溯法解决路径比较多，即解空间庞大的问题的时候会很笨拙，但确是系统性求解的方法。

Implementation

迷宫问题

典型的迷宫是一个不完全无向图，从一个节点（迷宫入口）开始搜索是否能到达另一个实现定好的节点（迷宫出口），并记录下途经格节点及其边（路径）
解空间即是各个路口的集合

#include <vector>
#include <iosteam>
using namespace std;

//express maze with a set of sequence of crossing

class Crossing
{
public:
    int turn1;
    int turn2;
    int turn3;

public:
    Crossing(int turn1, int turn2, int turn3) //constructor
    {
        Crossing::turn1 = turn1;
        Crossing::turn2 = turn2;
        Crossing::turn3 = turn3;
    };
}

class Maze
{
private:
    int exit;
    std::vector<Crossing> crossings; //set of crossings
    std::vector<int> result; //stack saving forks

public:
    Maze(int the_exit, std::vector<Crossing> the_crossings)
    {
        exit = the_exit;
        crossings = the_crossings;
    };

    findExit(int entrance);
    getResult();
};

Maze::findExit(int entrance)
{
    if (entrance)
    {
        if (entrance == Maze::exit || findExit(crossings[entrance].turn1) || findExit(crossings[entrance].turn2 || findExit(crossings[entrance].turn3)
        {
            result.push_back(entrance); //FIFO
            return 1;
        }
    }
    return 0;
}

Maze::getResult()
{
    findExit(1);
    std::vector<int>::iterator tra = result.rend();
    do
    {
        -- tra;
        cout << *tra << "->";
    }while (tra != result.begin());
    cout << "Exit" << endl;
}

int main()
{
    Crossing c1(2, 0, 0);
    Crossing c2(4, 0, 0);
    Crossing c3(0, 0, 0); //dead
    Crossing c4(3, 5, 0);
    Crossing c5(6, 0, 0);
    Crossing c6(7, 0, 0);
    Crossing c7(8, 9, 0);
    Crossing c8(0, 0, 0);
    Crossing c9(10, 0, 0);
    Crossing c0(0, 0, 0);

    std::vector<Crossing> crossings;
    crossings.push_back(c0);
    crossings.push_back(c1);
    crossings.push_back(c2);
    crossings.push_back(c3);
    crossings.push_back(c4);
    crossings.push_back(c5);
    crossings.push_back(c6);
    crossings.push_back(c7);
    crossings.push_back(c8);
    crossings.push_back(c9);

    Maze newMaze(10, crossings);
    newMaze.getResult();

    return 0;
}

Reference

左飞，《算法之美》