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

    1. class Solution {
    2. bool dfs(int rowidx, int colidx, vector<vector<char>>& board, vector<vector<bool>> rows, vector<vector<bool>> cols, vector<vector<bool>> grid)
    3. {
    4. if(colidx == board[0].size())
    5. {
    6. rowidx++;
    7. colidx = 0;
    8. }
    9. if(rowidx == board.size())
    10. return true;
    11. if(board[rowidx][colidx] != '.')
    12. {
    13. if(dfs(rowidx, colidx + 1,board, rows, cols, grid))
    14. return true;
    15. return false;
    16. }
    17. else
    18. {
    19. for(int i = 1; i <= 9; i++)
    20. {
    21. if(grid[1 + 3*(rowidx/3) + colidx/3][i] ||rows[rowidx][i] || cols[colidx][i])
    22. continue;
    23. board[rowidx][colidx] = '0' + i;
    24. grid[1 + 3*(rowidx/3) + colidx/3][i] = rows[rowidx][i] = cols[colidx][i] = true;
    25. if(dfs(rowidx, colidx + 1,board, rows, cols, grid))
    26. return true;
    27. grid[1 + 3*(rowidx/3) + colidx/3][i] = rows[rowidx][i] = cols[colidx][i] = false;
    28. board[rowidx][colidx] = '.';
    29. }
    30. return false;
    31. }
    32. }
    33. public:
    34. void solveSudoku(vector<vector<char>>& board) {
    35. if(!board.size() || !board[0].size())
    36. return;
    37. int n = board.size(), m = board[0].size();
    38. int total = 0;
    39. vector<vector<bool>> rows(n, vector<bool>(9 + 1, false)), cols(m, vector<bool>(9 + 1, false));
    40. vector<vector<bool>> grid(10, vector<bool>(9 + 1, false));
    41. for(int i = 0; i < n; i++)
    42. {
    43. for(int j = 0; j < m; j++)
    44. {
    45. if(board[i][j]!='.')
    46. {
    47. total++;
    48. int val = board[i][j] - '0';
    49. rows[i][val] = true;
    50. cols[j][val] = true;
    51. grid[1 + 3*(i/3) + j/3][val] = true;
    52. }
    53. }
    54. }
    55. if(total == m * n)
    56. return;
    57. dfs(0, 0, board, rows, cols, grid);
    58. }
    59. };

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

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

    1. class Solution {
    2. vector<vector<bool>> rows;
    3. vector<vector<bool>> cols;
    4. vector<vector<bool>> grids;
    5. vector<vector<char>> board;
    6. bool found;
    7. void dfs(int x, int y)
    8. {
    9. // cout << x << ' ' << y << endl;
    10. if(found) return;
    11. if(y == 9)
    12. {
    13. y = 0;
    14. x++;
    15. }
    16. if(x == 9)
    17. {
    18. found = true;
    19. return;
    20. }
    21. if(board[x][y] != '.') dfs(x, y + 1);
    22. else
    23. {
    24. for(int k = 1; k <= 9; k++)
    25. {
    26. char c = k + '0';
    27. if(!rows[x][k]) continue;
    28. if(!cols[y][k]) continue;
    29. if(!grids[(x/3) * 3 + y/3][k]) continue;
    30. board[x][y] = c;
    31. rows[x][k] = false;
    32. cols[y][k] = false;
    33. grids[x/3 * 3 + y/3][k] = false;
    34. dfs(x, y + 1);
    35. if(found) return;
    36. board[x][y] = '.';
    37. rows[x][k] = true;
    38. cols[y][k] = true;
    39. grids[(x/3) * 3 + y/3][k] = true;
    40. }
    41. }
    42. }
    43. public:
    44. void solveSudoku(vector<vector<char>>& _board) {
    45. board = _board;
    46. found = false;
    47. rows = vector<vector<bool>>(10, vector<bool>(10, true));
    48. cols = vector<vector<bool>>(10, vector<bool>(10, true));
    49. grids = vector<vector<bool>>(10, vector<bool>(10, true));
    50. for(int r = 0; r < board.size() ; r++)
    51. {
    52. for(int c = 0; c < board[0].size(); c++)
    53. {
    54. if(board[r][c] == '.') continue;
    55. int dig = board[r][c] - '0';
    56. rows[r][dig] = false;
    57. cols[c][dig] = false;
    58. grids[(r/3) * 3 + c/3][dig] = false;
    59. }
    60. }
    61. dfs(0, 0);
    62. _board = board;
    63. }
    64. };