Leetcode: Sudoku Solver

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

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

Understand the problem:
The problem asks for finding an unique solution for a sudoku solver. We assume that there is an unique solution existed in the sudoku solver. So the basic idea could be using DFS, very similar with permutation and combination problem. We search all valid numbers for a slot, apply DFS, and go to the next. 

Solution:

public class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length != 9 || board[0].length != 9) {
            return;
        }
        
        solveHelper(board);
    }
    
    private boolean solveHelper(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char k = '1'; k <= '9'; k++) {
                        if (isValid(i, j, k, board)) {
                            board[i][j] = k;
                            if (solveHelper(board) == true) {
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean isValid(int row, int col, char target, char[][] board) {
        // check the row and column
        for (int i = 0; i < 9; i++) {
            if ((board[row][i] == target) || (board[i][col] == target)) {
                return false;
            }
        }
        
        // check the block
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int x = row / 3 * 3 + i; // nth block * block_size  + offset
                int y = col / 3 * 3 + j;
                if (board[x][y] == target) {
                    return false;
                }
            }
        }
        return true;
    }
}

Discussion:
Now let's analyze the complexity. Suppose the sudoku size is n (although in reality it is 9). For each slot which could be filled, we could have at most O(n) different combinations. For each number, it takes O(n) time to determine if it is a valid number. So we have total number of n^2 numbers in the board, the overall time complexity is O(n^4). For the real case where n equals to 9, the complexity is acceptable. 


Summary:
The problem follows the same idea as permutation and combination problem, where DFS is widely used in searching problems. Draw a recursion tree will help you understand the problem.