德阳网站优化,南昌寻南昌网站设计,wifi扩展器做网站,公司注册地址出租回溯算法理论基础
回溯和递归密不可分#xff0c;有回溯就有递归#xff0c;所谓回溯就是基于一个叉树#xff0c;可能是二叉树或者是三叉树#xff0c;从root节点开始深度优先搜索遍历节点#xff0c;当遍历到一个子节点时#xff0c;回溯到上一个根节点选择另外一个子…回溯算法理论基础
回溯和递归密不可分有回溯就有递归所谓回溯就是基于一个叉树可能是二叉树或者是三叉树从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#includebits/stdc.h
using namespace std;vectorvectorchar board(9,vectorchar(9));
bool isValid(int row, int col, char val, vectorvectorchar 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(vectorvectorchar 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 judgetrue;while(judge){for(int i0;i9;i){for(int j0;j9;j){char c;scanf(%c,c);if(ce){judgefalse;return 0;}board[i][j]c;}}if(backtracking(board)){for(int i0;i9;i){for(int j0;j9;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这是一个判断条件在递归时代表
