37. 解数独

dfs是把一堆东西塞到某一个地方，塞的时候要注意约束条件
这道题就是把1-9的数字塞进数独表格里面
约束条件是：一行1-9出现一次，一列1-9出现一次，一个3*3格子1-9出现一次

class Solution {
   bool dfs(int rowidx, int colidx, vector<vector<char>>& board, vector<vector<bool>> rows, vector<vector<bool>> cols, vector<vector<bool>> grid)
   {
       if(colidx == board[0].size())
       {
           rowidx++;
           colidx = 0;
       }
       if(rowidx == board.size())
           return true;
       if(board[rowidx][colidx] != '.')
       {
           if(dfs(rowidx, colidx + 1,board, rows, cols, grid))
               return true;
           return false;
       }
       else
       {
           for(int i = 1; i <= 9; i++)
           {
               if(grid[1 + 3*(rowidx/3) + colidx/3][i] ||rows[rowidx][i] || cols[colidx][i])
                   continue;
               board[rowidx][colidx] = '0' + i;
               grid[1 + 3*(rowidx/3) + colidx/3][i] = rows[rowidx][i] = cols[colidx][i] = true;
               if(dfs(rowidx, colidx + 1,board, rows, cols, grid))
                   return true;
               grid[1 + 3*(rowidx/3) + colidx/3][i] = rows[rowidx][i] = cols[colidx][i] = false;
               board[rowidx][colidx] = '.';
           }
           return false;
       }
   }
public:
   void solveSudoku(vector<vector<char>>& board) {
       if(!board.size() || !board[0].size())
           return;
       int n = board.size(), m = board[0].size();
       int total = 0;
       vector<vector<bool>> rows(n, vector<bool>(9 + 1, false)), cols(m, vector<bool>(9 + 1, false));
       vector<vector<bool>> grid(10, vector<bool>(9 + 1, false));
       for(int i = 0; i < n; i++)
       {
           for(int j = 0; j < m; j++)
           {
               if(board[i][j]!='.')
               {
                   total++;
                   int val = board[i][j] - '0';
                   rows[i][val] = true;
                   cols[j][val] = true;
                   grid[1 + 3*(i/3) + j/3][val] = true;
               }
           }
       }
       if(total == m * n)
           return;
       dfs(0, 0, board, rows, cols, grid);
   }
};

可以通过优化状态存储来节省空间：

第二次写题
创建了三个数组，分别用来存储，某一行某一个数字能不能用，某一列某一个数字能不呢用，某一个格子某一个数字能不能用。然后使用dfs的方式来进行搜索，如果搜索到了，那么填好的格子就可以用来返回了。我这个代码需要注意的是，我把输入的变成了_board，它返回的也应该是_board，所以最后有一步是_board = board

class Solution {
    vector<vector<bool>> rows;
    vector<vector<bool>> cols;
    vector<vector<bool>> grids;
    vector<vector<char>> board;
    bool found;
    void dfs(int x, int y)
    {
        // cout << x << ' ' << y << endl;
        if(found) return; 
        if(y == 9)
        {
            y = 0;
            x++;
        }
        if(x == 9) 
        {
            found = true;
            return;
        }
        if(board[x][y] != '.') dfs(x, y + 1);
        else
        {
            for(int k = 1; k <= 9; k++)
            {
                char c = k + '0';
                if(!rows[x][k]) continue;
                if(!cols[y][k]) continue;
                if(!grids[(x/3) * 3 + y/3][k]) continue;
                board[x][y] = c;
                rows[x][k] = false;
                cols[y][k] = false;
                grids[x/3 * 3 + y/3][k] = false;
                dfs(x, y + 1);
                if(found) return; 
                board[x][y] = '.';
                rows[x][k] = true;
                cols[y][k] = true;
                grids[(x/3) * 3 + y/3][k] = true;
            }
        }
    }
public:
    void solveSudoku(vector<vector<char>>& _board) {
        board = _board;
        found = false;
        rows = vector<vector<bool>>(10, vector<bool>(10, true));
        cols = vector<vector<bool>>(10, vector<bool>(10, true));
        grids = vector<vector<bool>>(10, vector<bool>(10, true));
        for(int r = 0; r < board.size() ; r++)
        {
            for(int c = 0; c < board[0].size(); c++)
            {
                if(board[r][c] == '.') continue;
                int dig = board[r][c] - '0';
                rows[r][dig] = false;
                cols[c][dig] = false;
                grids[(r/3) * 3 + c/3][dig] = false; 
            }
        }
        dfs(0, 0);
        _board = board;
    }
};