题目链接：Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

这道题的要求是填充数独，其中空位置用‘.’填充，有唯一解。

这道题算是Valid Sudoku的升级版，同样的地方是可以使用3个数组记录每行、每列、每个九宫格出现过的数字。要填充数独，就是要对每个空位逐个填写1~9，查看能否解决。这是一个回溯的问题，可以通过递归来解决。

递归回溯前，使用数组place记录数独中的空位置，用used1、used2和used3标记每行、每列、每个九宫格出现过的数字，然后遍历数独，对其进行初始化设置。然后递归进行回溯处理，每次均循环填充1~9，查看能否填写进去。如果可以，递归进入下一位置；否则，尝试填写下一个数字。

时间复杂度：O(???)

空间复杂度：O(n2)

 1 class Solution
 2 {
 3     int used1[9][9], used2[9][9], used3[9][9];
 4     
 5 public:
 6     void solveSudoku(vector
   
     > &board) 7 { 8 vector
    
     > place; 9 for(int i = 0; i < board.size(); ++ i) 10 for(int j = 0; j < board[i].size(); ++ j) 11 { 12 if(board[i][j] == '.') 13 place.push_back({i, j}); 14 else 15 { 16 int num = board[i][j] - '0' - 1, k = i / 3 * 3 + j / 3; 17 used1[i][num] = used2[j][num] = used3[k][num] = 1; 18 } 19 } 20 21 DFS(board, place, place.size() - 1); 22 } 23 24 private: 25 bool DFS(vector
     
      > &board, vector
      
       > &place, int n) 26 { 27 if(n < 0) 28 return true; 29 30 int i = place[n][0], j = place[n][1]; 31 32 for(int num = 0; num < 9; ++ num) 33 { 34 int k = i / 3 * 3 + j / 3; 35 if(!used1[i][num] && !used2[j][num] && !used3[k][num]) 36 { 37 used1[i][num] = used2[j][num] = used3[k][num] = 1; 38 board[i][j] = num + '0' + 1; 39 40 if(DFS(board, place, n - 1)) 41 return true; 42 43 used1[i][num] = used2[j][num] = used3[k][num] = 0; 44 board[i][j] = '.'; 45 } 46 } 47 48 return false; 49 } 50 };
      
     
    
   

转载请说明出处：LeetCode --- 37. Sudoku Solver