回溯算法示例数独问题求解

回溯（backtracking）是遍历整个求解空间的一种常见的方式，一些有名的小游戏如数独的解法，八皇后游戏等都可以通过回溯的方法去求解。回溯的思想基本是通过递归进行的实现。这里以一个数独的场景为例向大家介绍一下实现的思路。

首先对数独的尚未填上数字的格子依次从左到右，从上到下的顺序进行填数字尝试，每填写当前的格子，可以按照条件首先筛选出可能的数字，并尝试将这些数字依次进行尝试填到格子里，当可以填写一个候选时，就跳到下一个还未填写数字的格子。如果后来发现下一个未填写的格子没有解（填写数字不能满足数独条件），则尝试下一个候选，如果所有候选都尝试后整个过程还是无解，则返回上一个格子的下一个候选再进行类似的尝试过程。

回溯过程也可以将看成时一个树的搜索过程，比如在数独场景，第一层节点可以看成是第一个格子的所有候选数字节点，回溯的过程是一个动态扩展这棵树的深度优先遍历的过程。如下示例代码显示了其过程，通过递归进行的实现，如果当前填写满足条件则继续下一个格子的填写，如果不满足则当前格子不填（撤回填写的数字）并考虑下一个候选，如果所有的候选都不满足，则退回到上一层搜索的状态继续搜索树的动态构建。

bool solveSudoku(std::vector<std::vector<char>>& board) {
    bool solved = true;
    for(int i = 0; i < board.size(); i++)
    {
        for(int j =0; j < board.size(); j++)
        {
            if(board[i][j] == '.')
            {
                solved = false;
                std::vector<char> chars = getCandidateChars(i, j, board);
                if(chars.size() == 0){return false;}
                for(auto c : chars)
                {
                    board[i][j] = c;
                    if(solveSudoku(board))return true;
                    board[i][j] = '.';
                }
            }
            if(board[i][j] == '.')
            {
                return false;
            }
        }
    }
    return solved;
}

完整示例代码可以参考如下链接。data-structures-algorithms/backtracking at main · kindlytree/data-structures-algorithms (github.com)