C++刷LeetCode（37. 解数独）【回溯】

糖逗

题目描述：

1. 
   
2. 编写一个程序，通过已填充的空格来解决数独问题。
   
3. 
   
4. 一个数独的解法需遵循如下规则：
   
5. 
   
6. 数字 1-9 在每一行只能出现一次。
   
7. 数字 1-9 在每一列只能出现一次。
   
8. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
   
9. 空白格用 '.' 表示。
   
10. 
    
11. 
    
12. 
    
13. 一个数独。
    
14. 
    
15. 
    
16. 
    
17. 答案被标成红色。
    
18. 
    
19. Note:
    
20. 
    
21. 给定的数独序列只包含数字 1-9 和字符 '.' 。
    
22. 你可以假设给定的数独只有唯一解。
    
23. 给定数独永远是 9x9 形式的。

复制代码

1. class Solution {
   
2. private:
   
3.     int row[9][9] = {0};
   
4.     int col[9][9] = {0};
   
5.     int matrix[9][9] = {0};
   
6. public:
   
7.     bool dfs(vector<vector<char> >&board, int index1, int index2){
   
8.         if(index1 > 8) return true;
   
9.         if(board[index1][index2] == '.'){
   
10.             for(char number = '1' ; number <= '9'; number++){
    
11.                 int number1 = number - '1';
    
12.                 if(row[index1][number1] == 1 || col[index2][number1] == 1 || matrix[index1 / 3*3 + index2 /3][number1] == 1)continue;
    
13.                 row[index1][number1] = 1;
    
14.                 col[index2][number1] = 1;
    
15.                 matrix[index1 / 3*3 + index2 /3][number1] = 1;
    
16.                 board[index1][index2] = number;
    
17. 
    
18.                 if(dfs(board, index1 + (index2 + 1)/9, (index2 + 1)%9)) return true;
    
19.                 //回溯
    
20.                 board[index1][index2] = '.';
    
21.                 matrix[index1 / 3*3 + index2 /3][number1] = 0;
    
22.                 col[index2][number1] = 0;
    
23.                 row[index1][number1] = 0;
    
24.             }
    
25.         }
    
26.         else return dfs(board,index1 + (index2 + 1)/9, (index2 + 1)%9);
    
27.         return false;
    
28.     }
    
29.     void solveSudoku(vector<vector<char>>& board) {
    
30.         //初始化变量
    
31.         for(int i = 0 ; i < 9; i++){
    
32.             for(int j = 0; j < 9; j ++){
    
33.                 if(board[i][j] != '.'){
    
34.                     int number = board[i][j] - '1';
    
35.                     row[i][number] = 1;
    
36.                     col[j][number] = 1;
    
37.                     matrix[i / 3 * 3 + j / 3][number] = 1;
    
38.                 }
    
39.             }
    
40.         }
    
41.         dfs(board, 0, 0);
    
42.         return;
    
43.     }
    
44. };

复制代码

参考链接：https://leetcode-cn.com/problems ... i-ji-de-dai-ma-hen/


注意事项：注意函数dfs的写法。

糖逗

没写出来