37. Sudoku Solver

Question:

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

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character ‘.’.

Thinking:

• Method:回溯

class Solution {
    public void solveSudoku(char[][] board){
        solveSudoku(board, 0, 0);
    }
    public boolean solveSudoku(char[][] board, int iStart, int jStart){
        for(int i = iStart ; i < 9; i++, jStart = 0)	//自己没写对的地方：在i增加的时候，需要将jStart归零
            for(int j = jStart; j < 9; j++)
                if(board[i][j] == '.'){
                    for(char p = '1'; p <= '9'; p++){
                        if(isValidSudoku(board, i, j, p)){
                            board[i][j] = p;
                            if(solveSudoku(board, i, j+1))  return true;
                            else    board[i][j] = '.';
                        }
                    }
                    return false;
                }
        return true;
    }
    public boolean isValidSudoku(char[][] board, int row, int column, char num) {
        for(int i = 0; i < 9; i++){
            int tempRow = 3 * (row / 3) + i / 3;
            int tempCol = 3 * (column / 3) + i % 3;
            if(num == board[i][column])  return false;
            if(num == board[row][i]) return false;
            if(num != '.' && board[3 * (row / 3) + i / 3][ 3 * (column / 3) + i % 3] == num)
                return false;
        }
        return true;
    }
}

二刷

还是通过回溯法，对于每一个位置进行判断。

class Solution {
    public void solveSudoku(char[][] board) {
        solve(board, 0, 0);
    }
    private boolean solve(char[][] board, int iStart, int jStart){
        for(int i = iStart; i < 9; i++, jStart = 0){
            for(int j = jStart; j < 9; j++){
                if(board[i][j] != '.') continue;
                for(char p = '1'; p <= '9'; p++){
                    if(check(board, i, j, p)){
                        board[i][j] = p;
                        if(solve(board, i, j + 1)) return true;
                        else board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    private boolean check(char[][] board, int row, int column, char num){
        for(int i = 0; i < 9; i++){
            if(num == board[i][column])  return false;
            if(num == board[row][i]) return false;
            if(num != '.' && board[3 * (row / 3) + i / 3][ 3 * (column / 3) + i % 3] == num)
                return false;
        }
        return true;
    }
}

Third time

• Method 1: dfs
  • for each of the for-loop, its function is to find the next ‘.’.

      class Solution {
      public void solveSudoku(char[][] board) {
          dfs(board, 0, 0);
      }
      private boolean dfs(char[][] board, int iStart, int jStart){
          for(int i = iStart; i < 9; i++, jStart = 0){
              for(int j = jStart; j < 9; j++){
                  if(board[i][j] != '.') continue;
                  for(char c = '1'; c <= '9'; c++){
                      if(check(board, c, i, j)){
                          board[i][j] = c;
                          if(dfs(board, i, j + 1)) return true;
                          else board[i][j] = '.';
                      }
                  }
                  return false;
              }
          }
          return true;
      }
      private boolean check(char[][] board, char c, int row, int col){
          for(int i = 0; i < 9; i++){
              if(board[row][i] == c) return false;
              if(board[i][col] == c) return false;
              if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] == c)
                  return false;
          }
          return true;
      }
      }