题目描述（困难难度）

37. Sudoku Solver - 图1

给定一个数独棋盘，输出它的一个解。

解法一 回溯法

从上到下，从左到右遍历每个空位置。在第一个位置，随便填一个可以填的数字，再在第二个位置填一个可以填的数字，一直执行下去直到最后一个位置。期间如果出现没有数字可以填的话，就回退到上一个位置，换一下数字，再向后进行下去。

  1. public void solveSudoku(char[][] board) {
  2.     solver(board);
  3. }
  4. private boolean solver(char[][] board) {
  5.     for (int i = 0; i < 9; i++) {
  6.         for (int j = 0; j < 9; j++) {
  7.             if (board[i][j] == '.') {
  8.                 char count = '1';
  9.                 while (count <= '9') {
  10.                     if (isValid(i, j, board, count)) {
  11.                         board[i][j] = count;
  12.                         if (solver(board)) {
  13.                             return true;
  14.                         } else {
  15.                             //下一个位置没有数字，就还原，然后当前位置尝试新的数
  16.                             board[i][j] = '.';
  17.                         }
  18.                     }
  19.                     count++;
  20.                 }
  21.                 return false;
  22.             }
  23.         }
  24.     }
  25.     return true;
  26. }
  28. private boolean isValid(int row, int col, char[][] board, char c) {
  29.     for (int i = 0; i < 9; i++) {
  30.         if (board[row][i] == c) {
  31.             return false;
  32.         }
  33.     }
  35.     for (int i = 0; i < 9; i++) {
  36.         if (board[i][col] == c) {
  37.             return false;
  38.         }
  39.     }
  41.     int start_row = row / 3 * 3;
  42.     int start_col = col / 3 * 3;
  43.     for (int i = 0; i < 3; i++) {
  44.         for (int j = 0; j < 3; j++) {
  45.             if (board[start_row + i][start_col + j] == c) {
  46.                 return false;
  47.             }
  48.         }
  50.     }
  51.     return true;
  52. }

时间复杂度：

空间复杂度：O（1）。

总

回溯法一个很典型的应用了。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情