不知道从什么时候养成的习惯，过年也开始读书，写算法，也可能自己太穷想多挣钱，也可能想做出一款像王者荣耀那样巅峰产品，好向家里或者周围的人炫耀，哪种可能都有。尽管资质不高，距梦想差距很大，只要每天做正向积累，努力争取，总有机会被你抓住。
学习回溯算法后，做了习题0-1背包、八皇后、数独，归纳一下：递归函数用于进入下一层选择，如果下层选择失败，退回当层重置状态，再次进入下层试探。结束条件一定在递归函数开头。
回溯算法，数独代码：
1 int MaxLen = 9; 2 bool Check(vector<vector<char>>& board, int nX, int nY, char szWillSet)//都是从0开始 nX nY 为要检查的行列 3 { 4 //此行，此列，此9宫格 5 for (int i = 0; i < MaxLen; ++i) 6 { 7 if (board[nX][i] == szWillSet || board[i][nY] == szWillSet) 8 { 9 return false; 10 } 11 } 12 //计算坐标所在定点位置 13 int nPointX = (nX/3) * 3; 14 int nPointY = (nY/3) * 3; 15 for (int i = nPointX; i < nPointX + 3; ++i) 16 { 17 if (i != nX) 18 { 19 for (int j = nPointY; j < nPointY+3; ++j) 20 { 21 if (board[i][j] == szWillSet) 22 { 23 return false; 24 } 25 } 26 } 27 } 28 return true; 29 } 30 31 bool TrySet(vector<vector<char>>& board, int i, int j)//xy为考察到哪个坐标了 32 { 33 //考察下个坐标 34 int nNextX = i; 35 int nNextY = j; 36 if (j < MaxLen-1) 37 { 38 ++nNextY; 39 } 40 else if (i < MaxLen-1) 41 { 42 ++nNextX; 43 nNextY=0; 44 } 45 else 46 { 47 return true; 48 } 49 if (board[nNextX][nNextY] == '.') 50 { 51 bool bHave = false; 52 for (char szDian = '1'; szDian <= '9'; ++szDian) 53 { 54 if(Check(board,nNextX,nNextY,szDian)) 55 { 56 bHave = true; 57 board[nNextX][nNextY] = szDian; 58 59 if(!TrySet(board, nNextX, nNextY)) 60 { 61 board[nNextX][nNextY] = '.'; 62 bHave = false; 63 } 64 } 65 } 66 if (!bHave) 67 { 68 return false; 69 } 70 } 71 else 72 { 73 return TrySet(board, nNextX, nNextY); 74 } 75 return true; 76 } 77 void solveSudoku(vector<vector<char>>& board) { 78 TrySet(board, 0, -1); 79 } 80 //------------------------------ 81 //----------以下是测试代码------- 82 //------------------------------ 83 void Print(vector<vector<char>>& board) 84 { 85 for (int i = MaxLen-1; i>=0 ;--i) 86 { 87 for (int j = 0; j<MaxLen;++j) 88 { 89 cout<<board[i][j]; 90 } 91 cout<<endl; 92 } 93 cout<<endl; 94 cout<<"--------------------"<<endl; 95 } 96 int main() 97 { 98 vector<vector<char>> board; 99 char arrp1[9] = {'.','.','.','2','7','5','9','.','.'}; 100 char arrp2[9] = {'.','.','.','.','.','.','.','.','6'}; 101 char arrp3[9] = {'.','.','.','8','.','3','.','2','.'}; 102 char arrp4[9] = {'.','9','8','.','.','.','3','.','.'}; 103 char arrp5[9] = {'.','6','4','.','1','.','5','9','.'}; 104 char arrp6[9] = {'.','.','7','.','.','.','2','4','.'}; 105 char arrp7[9] = {'.','2','.','1','.','9','.','.','.'}; 106 char arrp8[9] = {'7','.','.','.','.','.','.','.','.'}; 107 char arrp9[9] = {'.','.','9','7','4','8','.','.','.'}; 108 /*char arrp1[9] = {'5','3','.','.','7','.','.','.','.'}; 109 char arrp2[9] = {'6','.','.','1','9','5','.','.','.'}; 110 char arrp3[9] = {'.','9','8','.','.','.','.','6','.'}; 111 char arrp4[9] = {'8','.','.','.','6','.','.','.','3'}; 112 char arrp5[9] = {'4','.','.','8','.','3','.','.','1'}; 113 char arrp6[9] = {'7','.','.','.','2','.','.','.','6'}; 114 char arrp7[9] = {'.','6','.','.','.','.','2','8','.'}; 115 char arrp8[9] = {'.','.','.','4','1','9','.','.','5'}; 116 char arrp9[9] = {'.','.','.','.','8','.','.','7','9'};*/ 117 vector<char> vectemp9(arrp9, arrp9 + 9); 118 vector<char> vectemp8(arrp8, arrp8 + 9); 119 vector<char> vectemp7(arrp7, arrp7 + 9); 120 vector<char> vectemp6(arrp6, arrp6 + 9); 121 vector<char> vectemp5(arrp5, arrp5 + 9); 122 vector<char> vectemp4(arrp4, arrp4 + 9); 123 vector<char> vectemp3(arrp3, arrp3 + 9); 124 vector<char> vectemp2(arrp2, arrp2 + 9); 125 vector<char> vectemp1(arrp1, arrp1 + 9); 126 board.push_back(vectemp9); 127 board.push_back(vectemp8); 128 board.push_back(vectemp7); 129 board.push_back(vectemp6); 130 board.push_back(vectemp5); 131 board.push_back(vectemp4); 132 board.push_back(vectemp3); 133 board.push_back(vectemp2); 134 board.push_back(vectemp1); 135 Print(board); 136 solveSudoku(board); 137 Print(board); 138 return 0; 139 }
1 #include <iostream> 2 #include <math.h> 3 #include <string> 4 #include <vector> 5 using namespace std; 6 7 const int MaxLen = 9; 8 //以下三个数组用于判断是否有重复，避免循环查找重复元素 9 char ArrRow[MaxLen][MaxLen] = {0}; //用于快速判断行内有没有重复元素 10 char ArrCol[MaxLen][MaxLen] = {0}; //用于快速判断列内有没有重复元素 11 char ArrGlb[MaxLen][MaxLen] = {0}; //用于快速判断每9个格子里有没有重复元素 12 13 void SetMark(int nX,int nY, int nIdx, int nCheck, int nSet) 14 { 15 ArrRow[nX][nCheck] = nSet; 16 ArrCol[nY][nCheck] = nSet; 17 ArrGlb[nIdx][nCheck] = nSet; 18 } 19 20 bool TrySet(vector<vector<char>>& board, int nNextX, int nNextY)//xy为考察到哪个坐标了 21 { 22 while (board[nNextX][nNextY] != '.')//考察下个坐标 23 { 24 if (nNextY < MaxLen-1) 25 { 26 ++nNextY; 27 } 28 else if (nNextX < MaxLen-1) 29 { 30 ++nNextX; 31 nNextY=0; 32 } 33 else 34 { 35 return true; 36 } 37 } 38 bool bHave = false; 39 int nIndex = (nNextX / 3) * 3 + nNextY / 3; 40 for (int szDian = 0; szDian < 9; ++szDian) 41 { 42 if(ArrRow[nNextX][szDian] == 1 || ArrCol[nNextY][szDian] == 1 || ArrGlb[nIndex][szDian] == 1) 43 continue; 44 45 bHave = true; 46 board[nNextX][nNextY] = '1' + szDian; 47 48 SetMark(nNextX, nNextY, nIndex, szDian, 1); 49 if(!TrySet(board, nNextX, nNextY)) 50 { 51 board[nNextX][nNextY] = '.'; 52 bHave = false; 53 SetMark(nNextX, nNextY, nIndex, szDian, 0); 54 } 55 } 56 if (!bHave) 57 { 58 return false; 59 } 60 return true; 61 } 62 void solveSudoku(vector<vector<char>>& board) 63 { 64 //把vector元素映射到检查辅助数组 65 int nTemp = 0; 66 int nIndex = 0; 67 int nIndexX = 0; 68 for (int i = 0; i<MaxLen ;++i) 69 { 70 nIndexX = (i / 3) * 3; 71 for (int j = 0; j<MaxLen;++j) 72 { 73 if (board[i][j] != '.') 74 { 75 nTemp = board[i][j] - '1'; 76 nIndex = nIndexX + j / 3; 77 SetMark(i,j,nIndex,nTemp,1); 78 } 79 } 80 } 81 82 TrySet(board, 0, 0); 83 } 84 //------------------------------ 85 //----------以下是测试代码------- 86 //------------------------------ 87 void Print(vector<vector<char>>& board) 88 { 89 for (int i = MaxLen-1; i>=0 ;--i) 90 { 91 for (int j = 0; j<MaxLen;++j) 92 { 93 cout<<board[i][j]; 94 } 95 cout<<endl; 96 } 97 cout<<endl; 98 cout<<"--------------------"<<endl; 99 } 100 int main() 101 { 102 vector<vector<char>> board; 103 char arrp1[9] = {'.','.','.','2','7','5','9','.','.'}; 104 char arrp2[9] = {'.','.','.','.','.','.','.','.','6'}; 105 char arrp3[9] = {'.','.','.','8','.','3','.','2','.'}; 106 char arrp4[9] = {'.','9','8','.','.','.','3','.','.'}; 107 char arrp5[9] = {'.','6','4','.','1','.','5','9','.'}; 108 char arrp6[9] = {'.','.','7','.','.','.','2','4','.'}; 109 char arrp7[9] = {'.','2','.','1','.','9','.','.','.'}; 110 char arrp8[9] = {'7','.','.','.','.','.','.','.','.'}; 111 char arrp9[9] = {'.','.','9','7','4','8','.','.','.'}; 112 /*char arrp1[9] = {'5','3','.','.','7','.','.','.','.'}; 113 char arrp2[9] = {'6','.','.','1','9','5','.','.','.'}; 114 char arrp3[9] = {'.','9','8','.','.','.','.','6','.'}; 115 char arrp4[9] = {'8','.','.','.','6','.','.','.','3'}; 116 char arrp5[9] = {'4','.','.','8','.','3','.','.','1'}; 117 char arrp6[9] = {'7','.','.','.','2','.','.','.','6'}; 118 char arrp7[9] = {'.','6','.','.','.','.','2','8','.'}; 119 char arrp8[9] = {'.','.','.','4','1','9','.','.','5'}; 120 char arrp9[9] = {'.','.','.','.','8','.','.','7','9'};*/ 121 vector<char> vectemp9(arrp9, arrp9 + 9); 122 vector<char> vectemp8(arrp8, arrp8 + 9); 123 vector<char> vectemp7(arrp7, arrp7 + 9); 124 vector<char> vectemp6(arrp6, arrp6 + 9); 125 vector<char> vectemp5(arrp5, arrp5 + 9); 126 vector<char> vectemp4(arrp4, arrp4 + 9); 127 vector<char> vectemp3(arrp3, arrp3 + 9); 128 vector<char> vectemp2(arrp2, arrp2 + 9); 129 vector<char> vectemp1(arrp1, arrp1 + 9); 130 board.push_back(vectemp9); 131 board.push_back(vectemp8); 132 board.push_back(vectemp7); 133 board.push_back(vectemp6); 134 board.push_back(vectemp5); 135 board.push_back(vectemp4); 136 board.push_back(vectemp3); 137 board.push_back(vectemp2); 138 board.push_back(vectemp1); 139 Print(board); 140 solveSudoku(board); 141 Print(board); 142 return 0; 143 }
改进的内容：
1.检查行列及9个方格时，不必再循环检查，直接通过索引来确定是否已经存在。
2.已经存在数字的方格，不需要再进入递归函数，减少函数调用次数。