代码随想录30——回溯：332重新安排行程、51N皇后、37解数独
文章目录
1.332重新安排行程
1.1.题目
1.2.解答
1.2.1.思路
1.题目理解
这道题目还是比较复杂的，但是只是题目的意思和最后代码稍微复杂一点，但是实际上并不难。这道题目其实就像是一个图，图中有很多节点，然后给了不同节点之前的连接箭头；给你一个起点，让你遍历整个图的所有节点，同时要使用完所有的箭头，不能多用也不能少用。只不过这道题把图的节点换成了机场，把箭头换成了机票，更加有实际意义。
解答的方法和回溯的穷举法是一样的，因为题目先给了所有的机票，也就是所有的箭头，即从哪里出发，可以飞往哪里。比如从机场A出发，可以飞往机场BCD，比如给了机票是[A, B], [A, B], [A, C], [A, D]，其实就是从A出发，A→B有两张机票（两个箭头，注意相同的起止点可以有多张机票）、A→C有一张机票，A→D有一张机票。
那么其实问题就变成，从某个点出发之后，他可以飞往多个下一个目的地；然后从新的下一个目的地出发，又可以飞往多个下下个目的地…依次类推，直到用完所有的机票飞往所有的目的地。但是这个过程中，可能会陷入胡同，比如下图（1）所示，如果一开始就从A飞往C，结果是无法用完所有机票遍历所有机场，而A→B→A→C满足最终要求。那么如何判断收集的一条飞行路径是遍历完了所有节点，并且用完了所有机票呢？如下图（2）所示，其实只需要统计我们飞行的路径中，机场的个数和机票的张数的关系，如果机场的的个数=机票的张数+1，那么说明就用完了所有的机票（只要是用完了所有的机票，自然就遍历完了所有的节点，所以其实用完所有机票才是真正的要求）
2.遍历过程
其实理解了上面的题目要求之后，很容易发现这个和之前的排列问题是很相似的，其实就是每次选择当前的空的所有可能，然后调用递归选择下一个空的数的选择。本题以输入：[["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]为例，抽象为树形结构如下：
所以这里在代码实现上就有两点需要注意：
- 记录当前机场的目的机场，即当前机场可以飞往哪里
- 记录当前机场飞往目的机场的剩余机票张数，比如A→B有两张机票，飞一次的话就少一张，至少有一张机票才能飞
所以这里使用的数据结构是map<string, map<string, int>，表示<起飞机场，<目的地，剩余机票张数>>。但是这里还需要思考一下，是否可以优化数据结构提高效率，因为map有map和unordered_map的区别：unordered_map底层是哈希表，查询搜索是O(1)；而map底层是红黑树，可以增删，查询搜索是O(logn)，另外map的键是有序的。
由于查询出发机场需要快速查找，所以使用unordered_map更好。
那么达到机场使用哪个呢？注意到题目要求中是返回字典序号靠前的结果，所以我们要把目标机场的存储就按照键的值进行有序存储，这样遍历目标机场的时候自然就会遍历字典序号在前面的机场，自然就满足了题目的要求。所以到达机场使用map的数据结构更好。
此外注意，题目要求返回字典序号靠前的那个路线就可以了，而不是要求返回所有的路线，所以我们并不是要利用回溯的特性寻找所有可能的解，而是只需要找到其中的一个解。一旦找到了第一个解，那么整个递归函数就立马结束，不用再递归了。所以这里递归函数需要有返回值。
1.2.2.代码
上面就是给出了自己的讲解，具体更加详细的讲解可以去看代码随想录网站上的讲解。但是只要理解了上面的步骤，可以直接看下面的代码，有详细的注释，本题并不是特别难。
注意：这道题其实也是一道图论中深度优先搜索的题目，只不过在深度优先搜索中也涉及到回溯，所以这里按照回溯来理解也是没有问题的。
// unordered_map<出发机场, map<到达机场, 航班次数>> targets
// 注意为什么要用这种方式：因为我们要记录从当前机场出发，可以往哪些机场飞。比如出发机场是A，到达机场
// 可以是BCD等。还有一个问题是每张机票只能用一次，所以我们还要记录从出发机场飞往达到机场的剩余机票的张数，
// 比如可能有三张从A飞往B的机票，那么每次遍历机场A的时候，如果向往机场B非，就要先判断是否还有A->B的机票
// 如果有就可以飞
unordered_map<string, map<string, int>> targets;
// ticketNum是一共有多少张机票，result是最终的飞行路线结果
bool backtracking(int ticketNum, vector<string> &result)
{
// 递归终止条件：如果飞行路线中机场个数 = 机票张数 + 1，则说明把所有机票都用完了，
// 即收集到了一个可能路线
if (result.size() == ticketNum + 1)
{
return true;
}
// 开始递归：从路线中最后一个机场出发（也就是上一次到达的机场，或者最初起飞的机场），遍历所有
// 它可能飞往的达到机场，寻找一条路径
for (pair<const string, int> &target : targets[result[result.size() - 1]])
{
// 如果从当前机场，飞往到达机场的机票还有剩余，那么就还能飞
if (target.second > 0)
{
result.push_back(target.first); // 飞往到达机场，加到路线中
target.second--; // 当前机场->到达机场，所以机票张数-1
// 重要：递归调用，从下一个机场作为起飞点，再次寻找飞往的目的地
// (1)如果调用下一个机场的结果是true，说明找到了一条路线，则直接返回
// (2)如果调用下一个机场的结果是false，说明没有找到一条完整路线（即走到了死胡同里）
// 那么就到了下面回溯的过程：即把当前for循环选择的到达机场弹出，换另一个到达机场
if (backtracking(ticketNum, result))
return true; // 找到一条路线就返回
result.pop_back(); // 回溯
// 注意：这里一定不要忘了机票数量++，因为上面--是因为当前位置的到达机场为当前for循环选择的值
// （假设是B）的时候，后面调用递归安排后面的路线。一旦后面递归完成，说明当前位置选择
// 这个for循环的值B经过测试不能满足要求了，所以要把当前选择的到达机场B弹出，然后把
// 它的机票张数也复原，然后重新选择另一个达到机场C，此时B的机票张数应该还是原来的张数
// 所以这里回溯的时候一定要把机票张数也++，对机票张数进行复原
target.second++;
}
}
return false;
}
vector<string> findItinerary(vector<vector<string>> &tickets)
{
targets.clear();
vector<string> result;
for (const vector<string> &vec : tickets)
{
// vec[0]是触发机场的名称，targets[vec[0]]就是取出键对应的值，即<到达机场，剩余机票次数>
targets[vec[0]][vec[1]]++; // 记录映射关系
}
result.push_back("JFK"); // 起始机场
backtracking(tickets.size(), result);
return result;
}
2.51N皇后
参考：代码随想录，51N皇后
2.1.题目
2.2.解答
都知道n皇后问题是回溯算法解决的经典问题，但是用回溯解决多了组合、切割、子集、排列问题之后，遇到这种二维矩阵还会有点不知所措。
首先来看一下皇后们的约束条件：
- 不能同行
- 不能同列
- 不能同对角线
注意：上面的图中黄色和灰色不代表任何含义，只是为了让棋盘看起来更加有区分度，对于下棋没有任何约束。
确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树。下面用一个 3 * 3 的棋盘，将搜索过程抽象为一棵树，如图：
其实思路就很简单了，分两步：
- 递归的层数就是棋盘的行数，每一层就是在选择棋盘的每一行。
- 对于某一行，用
for循环从头开始遍历所有它可能能够放置皇后的位置。如果能够放置皇后，那么就在这里放置一个皇后，然后继续遍历下一行，放置下一行的皇后。
而递归的终止条件就是如果当前遍历到了第n行（因为是从0行开始，所以就相当于此时遍历出了棋盘范围），则说明每一个行都放置了一个合法位置的皇后（如果这一行的所有位置都不能放置的话，相当于for循环什么都没干，所以无法进入内部的if，也就无法再次调用递归选择下一行的放置皇后的位置，相当于递归到这一行就提前结束了），说明此时的棋盘就是一种合法的放置方式。
所以这里的代码写法和之前是一样的，之前用的都是path收集当前的路径，这里就是用一个chess_board收集当前的放置方法。直接给出代码如下，很简单：
vector<vector<string>> result; // 最终收集的所有可能的放置方案
vector<string> chess_board; // 当前放置的棋盘格，就是之前组合问题中的path
// 传入棋盘格的大小，当前要放置皇后的行，当前要放置皇后的列，已经放置的棋盘格，
// 判断是否能够在当前位置放置皇后
bool isValid(int n, int row, int col)
{
// 判断列
for(int i = 0; i < row; i++)
if(chess_board[i][col] == 'Q') // 每一行的当前列
return false;
// 注意：这里不用判断行是否在同一行，因为我们是逐行放置皇后，即遍历当前行的时候，之前一定是没有放置过的
// 判断左上角对角线
for(int i = row-1, j = col-1; i>=0 && j>=0; i--, j--)
if(chess_board[i][j] == 'Q')
return false;
// 判断右上角对角线
for(int i = row-1, j = col+1; i>=0 && j<n; i--, j++)
if(chess_board[i][j] == 'Q')
return false;
return true;
}
void backtracking(int n, int row)
{
// 递归终止条件：遍历到第n行了（从0开始），说明棋盘已经放置满了，所以是一种合理的结果
if(n == row)
{
result.push_back(chess_board);
return;
}
// 遍历当前行的每一个位置，判断是否可以放置皇后
for(int col = 0; col < n; col++)
{
if(isValid(n, row, col)) // 如果当前位置可以放置皇后
{
chess_board[row][col] = 'Q'; // 放置皇后
backtracking(n, row + 1); // 放置下一行的皇后
chess_board[row][col] = '.'; // 回溯，删除当前位置放置的皇后
}
}
}
vector<vector<string>> solveNQueens(int n)
{
// 初始化nxn的棋盘格为空，没有放置任何皇后
for(int i = 0; i < n; i++)
chess_board.push_back(string(n, '.'));
result.clear();
backtracking(n, 0); // 从棋盘格第0行开始放置皇后
return result;
}
3.37解数独
参考：代码随想录，37解数独
3.1.题目
3.2.解答
3.2.1.正确解法
这里具体的思路直接去看代码随想录的网站讲解吧，或者看下面代码的详细注释。根据注释仔细理清思路：
- 首先两个
for循环和之前N皇后问题是不一样的，因为N皇后问题每次一行中只需要选择一个空放置皇后，然后遍历每一行。但是数独问题一行中有多个空，同样还要遍历所有的行。所以数独需要有两个for循环：一个for(i)遍历数独的所有行，这个是总体看数独；一个for(j)遍历某一行中所有列的空位。对于每一个空位，使用for循环是遍历它可以填写的数字的所有可能。 - 数独是存在唯一解的，所以其唯一的解在代码中对应就是每一个空位选择的数字都满足
isValid的要求，从而调用递归函数继续填写整个数独。此时虽然代码是每次都从头遍历整个数独，但是真正要填的数字是从上一次填写的位置后面开始的。只有每一个空位都满足isValid的要求，这样不断的递归下去，直到把for(j)和for(i)的两个for循环都遍历完了，说明找到了最终的解。所以在for(i)外面会return true。
bool isValid(vector<vector<char>>& board, int row, int col, char num)
{
int n = board.size();
// 同一行不能有相同的
for(int j = 0; j < n; j++)
if(board[row][j] == num)
return false;
// 同一列不能有相同的
for(int i = 0; i < n; i++)
if(board[i][col] == num)
return false;
// 同一个小的九宫格不能有相同的
int start_row = row / 3;
start_row *= 3;
int start_col = col / 3;
start_col *= 3;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
if(board[start_row + i][start_col + j] == num)
return false;
return true;
}
// 正确解法
bool backtracking(vector<vector<char>>& board)
{
// 遍历数独的每一行
for(int row = 0; row < board.size(); row++)
{
// 遍历数独的每一列
for(int col = 0; col < board[0].size(); col++)
{
// 当前位置原来就有数字，或者之前填过数字了，就不用填了
if(board[row][col] != '.')
continue;
// 否则遍历1-9，查找哪些数字可能填入当前的空中
for(char num = '1'; num <= '9'; num++)
{
if(isValid(board, row, col, num))
{
board[row][col] = num; // 修改棋盘格，当前位置填入num
// 递归，再次填数独，这样下次递归的函数里面直接会走上面的continue，因为这个位置已经填了数了
if(backtracking(board))
return true;
board[row][col] = '.'; // 回溯
}
}
// 重要：这里才是递归的终止条件，或者说是提前结束的剪枝操作。能够执行到这里，说明在上面的for循环中，
// 选择1-9通过isValid判断都不合法，因为如果合法的话就会进去再次调用递归函数，然后继续递归。
// 而如果不合法的话，上面的for循环中if判断都不合法，即在这个空的上一个空选择的数是错的，导致
// 这次不管填什么数字都不满足数独要求了，所以才会出for循环运行到这里。那么此时就直接return
// fasle，告诉上次的递归函数选择的数字是错误的。
// 其实这里也可以看出来，数独的唯一解就是每一次都选择正确的数字，所以每一次都满足isValid的条件
// 所以就不断递归，直到把所有的空都填满，也就是for(i)和for(j)都循环完毕，也就到了最下面的return
// true，再层层向上返回，得到唯一的解。
return false;
}
// 注意：这里没有return false。因为上面的for循环填每一行的空位，虽然上面说了唯一的解就是每一个空位
// 都满足isValid的条件，然后层层递归。但是也有可能这一行中没有空位，也就是都是走了continue的路线，
// 那么这一行就不会调用任何递归函数，所以for(i)正常执行遍历下一行，此时也是合法的。所以这里不能直接
// return fasle，也就是这里不需要做任何处理。
}
// 如果能够执行到这里，说明for(i)和for(j)都循环完毕了，也就是每一个空位都找到了合适的解，也就是
// 整个数独问题找到了唯一的答案。所以这里return true，然后true会层层返回给上一层的递归函数，
// 直到返回给最高层的递归函数
return true;
}
void solveSudoku(vector<vector<char>> &board)
{
backtracking(board);
}
3.2.2.自己的写法，没有AC，待二刷看
下面是自己参考N皇后，想写的解法。但是这种方法会存在很多问题，要考虑到各个地方的细节，所以没有AC通过。所以感觉还是上面的解法更加通用，虽然说每次调用递归函数的时候，都又是从头开始遍历整个数独的每一个元素，但是方法更加简单，唯一争取的解就是每一次都满足isValid然后层层调用递归函数的那种选择。下面自己的写法就是想每次调用递归的函数的时候都只从上一次选择的数后面开始遍历数独，但是这样存在很多问题。二刷再看吧，今天已经花了很多时间了。
// 自己写的错误解法，无法AC
bool backtracking(int n, int row, int col, vector<vector<char>>& board)
{
if(row == n)
return true;
// 遍历当前行的所有空位，每一个空位都需要填一个数
for(int j = col; j < n; j++)
{
if(board[row][j] != '.')
continue;
for(char num = '1'; num < '9'; num++)
{
if(isValid(board, row, j, num))
{
board[row][j] = num;
if(backtracking(n, row, j + 1, board))
return true;
board[row][j] = '.'; // 回溯
}
}
// 执行到这里，说明上述是错的，即使止损
return false;
}
// 上面遍历完了这一行，然后从0开始继续遍历下一行
if(backtracking(n, row + 1, 0, board))
return true;
return false;
}
void solveSudoku(vector<vector<char>> &board)
{
backtracking(board.size(), 0, 0, board);
}