037-sudoku-solver

Question

https://leetcode.com/problems/sudoku-solver/description/

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.

Example:

Thought Process

1. Trial by Error and Backtrack
   1. Time complexity O(9^m), where m is number of blank cells
   2. Space complexity O(m)

Solution

class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length != 9) return;
        solve(board);
    }

    private boolean solve(char[][] board) {
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') {
                    for (char i = '1'; i <= '9'; i++) {
                        if (isValid(board, r, c, i)) {
                            board[r][c] = i;
                            if (solve(board)) return true;
                            else board[r][c] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int r, int c, char i) {
        for (int j = 0; j < 9; j++) {
            if (board[r][j] != '.' && board[r][j] == i) return false;
            if (board[j][c] != '.' && board[j][c] == i) return false;
            if (board[(r / 3) * 3 + j / 3][(c / 3) *3 + j % 3] != '.' && board[(r / 3) * 3 + j / 3][(c / 3) *3 + j % 3] == i) return false;
        }
        return true;
    }
}

Additional