回溯算法---数独问题

回溯算法理论基础

回溯和递归密不可分，有回溯就有递归，所谓回溯就是基于一个叉树，可能是二叉树或者是三叉树，从root节点开始深度优先搜索遍历节点，当遍历到一个子节点时，回溯到上一个根节点选择另外一个子节点继续进行遍历，就叫做回溯。
回溯算法的标准解题模板：viod backTracking(参数){
结束条件
处理逻辑
递归
回溯
}

PTA数独游戏

输入格式:
The input test file will contain multiple cases. Each test case consists of a single line containing 81 characters, which represent the 81 squares of the Sudoku grid, given one row at a time. Each character is either a digit (from 1 to 9) or a period (used to indicate an unfilled square). You may assume that each puzzle in the input will have exactly one solution. The end-of-file is denoted by a single line containing the word “end”.

注意： 本题输入数据量较大，cin, getline可能会超时，建议使用scanf。

输出格式:
For each test case, print a line representing the completed Sudoku puzzle.

输入样例:
在这里给出一组输入。例如：

.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

输出样例:
在这里给出相应的输出。例如：

527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936

#include<bits/stdc++.h>
using namespace std;vector<vector<char>> board(9,vector<char>(9));
bool isValid(int row, int col, char val, vector<vector<char>>& board) {for (int i = 0; i < 9; i++) { // 判断行里是否重复if (board[row][i] == val) {return false;}}for (int j = 0; j < 9; j++) { // 判断列里是否重复if (board[j][col] == val) {return false;}}int startRow = (row / 3) * 3;int startCol = (col / 3) * 3;for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复for (int j = startCol; j < startCol + 3; j++) {if (board[i][j] == val ) {return false;}}}return true;
}
bool backtracking(vector<vector<char>>& board) {for (size_t i = 0; i < board.size(); i++) {        // 遍历行for (size_t j = 0; j < board[0].size(); j++) { // 遍历列if (board[i][j] != '.') continue;for (char k = '1'; k <= '9'; k++) {     // (i, j) 这个位置放k是否合适if (isValid(i, j, k, board)) { board[i][j] = k;                // 放置kif (backtracking(board)) return true; // 如果找到合适一组立刻返回board[i][j] = '.';              // 回溯，撤销k}}return false;                           // 9个数都试完了，都不行，那么就返回false}}return true; // 遍历完没有返回false，说明找到了合适棋盘位置了
}int main(){bool judge=true;while(judge){for(int i=0;i<9;i++){for(int j=0;j<9;j++){char c;scanf("%c",&c);if(c=='e'){judge=false;return 0;}board[i][j]=c;}}if(backtracking(board)){for(int i=0;i<9;i++){for(int j=0;j<9;j++){printf("%c",board[i][j]);}}cout<<'\n';}char c;scanf("%c",&c);}
}

我们使用回溯法来解决这个问题，会有一个十叉树，如果数独表这个地方是空格，会尝试十个数字0~9，如果十个数字都不符合，则返回false，如果有符合的数字，则将board[i][j]改为这个数字，进行递归，如果递归函数的结果是true,则返回true。如果递归函数的结果是false,则回溯，就是将board[i][j]重新置空。

在backTracking函数中，为什么没有开头的结束条件呢。因为我们只需要有一条通路，填满这个九宫格就可以。如果我们需要每个通路的内容，则需要有结束条件来记录每个通路。同时我们的backTracking函数的返回值为bool，这是一个判断条件，在递归时代表