Problem description:

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 ‘.’.


A sudoku puzzle…


…and its solution numbers marked in red.

Note:

The given board contain only digits 1-9 and the character ‘.’.
You may assume that the given Sudoku puzzle will have a single unique solution.
The given board size is always 9x9.

Solution:

For this question, we can use recursive/backtracking to solve it.

  1. Find a '.' location that need to fill in a number
  2. Check if this position can be filled in with some number. The checking can be done by scanning the same row, the same column, the same 3*3 box.
  3. If we can fill the position with a number, then we use recursive to find next '.' position to be filled. One thing to notice is that, when we do the recursive, we might found out that this current result is false. At this time, we can use backtracking to previous level, and try to put other number in the previous position.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def isValid(board, row, col, x):
            if any(board[row][j] == x for j in range(9)): return False
            # Check col
            if any(board[i][col] == x for i in range(9)): return False
            # Check block
            br, bc = 3*(row//3), 3*(col//3)
            if any(board[i][j] == x for i in range(br, br+3) for j in range(bc, bc+3)): return False
            return True
        
        def solve(board, r, c):
            while board[r][c] != '.':
                c += 1
                if c == 9: c, r = 0, r+1
                if r == 9: return True
            # Try all options, backtracking if not work
            for k in "123456789":
                if isValid(board, r, c, k):
                    board[r][c] = str(k)
                    if solve(board, r, c):
                        return True
            board[r][c] = '.'
            return False
        
        solve(board, 0, 0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        /*
        1. find location, '.', to check 
        2. determine what number can this position use. 
            By checking whether if same row || same column || same box, have this number.
        3. after filling this position, we can pass this board to the recursive and check next '.' to be filled.
        */
        if(board.empty() || board[0].size() == 0) return;
        solve(board);
    }
    
    bool solve(vector<vector<char>>& board){
        for(int i= 0; i< board.size(); i++){
            for(int j= 0; j< board[0].size(); j++){
                if(board[i][j]== '.'){ //a location needs to be filled
                    for(char c= '1'; c<= '9'; c++){ //try from 1 through 9
                        if(isValid(board, i, j, c)){ //check if this 'c' can put in the position
                            board[i][j]= c; //put c into the location
                          if(solve(board)) //if this is the solution
                                return true;
                            else
                                board[i][j]= '.'; //go back and try another char
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    bool isValid(vector<vector<char>>& board, int row, int col, char c){
        for(int i= 0; i< 9; i++){
            if(board[i][col] != '.' && board[i][col]== c) return false; //check row by row, found c is already used
            if(board[row][i] != '.' && board[row][i]== c) return false;
            int boxR= 3*(row/3)+ i/3;
            int boxC= 3*(col/3)+ i%3;
            if(board[boxR][boxC] != '.' && board[boxR][boxC]== c) return false;
        }
        return true;
    }
    
};

reference:
https://www.youtube.com/watch?v=b6CxF17Y_k4
https://goo.gl/PaqSwh