37. Sudoku Solver.md

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;
   	}
   }

C++ Version

• Method 1: backtrace

   class Solution {
   private:
   	bool dfs(vector<vector<char>>& board, int i_start, int j_start){
   		for(int i = 0; i < 9; ++i, j_start = 0){
   			for(int j = 0; j < 9; ++j){
   				if(board[i][j] != '.') continue;
   				for(char c = '1'; c <= '9'; ++c){
   					if(check(board, i, j, c)){
   						board[i][j] = c;
   						if(dfs(board, i, j + 1)) return true;
   						board[i][j] = '.';
   					}
   				}
   				return false;
   			}
   		}
   		return true;
   	}
   	bool check(vector<vector<char>>& board, int row, int col, char c){
   		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;
   	}
   public:
   	void solveSudoku(vector<vector<char>>& board) {
   		dfs(board, 0, 0);
   	}
   };