Recursive java solution with explanation (beats 90%)


  • 0
    A

    I couldn't find any perfect math formula or greedy/dp solution to the problem. Seems there is no other way than recursively place valid numbers to cell [r, c] and move forward to cell [r, c + 1] or to [r + 1, 0] in case current row has finished. The main problem is the number of checks for the "validness" of some number inside specific cell - it's huge (as each recursive call invokes it 9 times and it turns into O(9 ^ m*n) complexity). If the check is performed using brute-force solution (e.g. scan the column, row and square and check if the number is not present there) than the problem gets exponential complexity.
    So the main goal is to make answer to the question "is number v valid for column c and row r and square [r / 3, c / 3]?" linear. To do this we need to cache all occupied numbers for column, row and square using the following 2 dimensional arrays:

            columns = new boolean[m][10];
            rows = new boolean[n][10];
            squares = new boolean[n / 3][m / 3][10];
    

    next thing is just to recurse through the board, skip already specified cells and try any valid number for the others. This would backtrack as soon as there are no valid numbers left for some cell.

    public class Solution {
        boolean[][] columns;
        boolean[][] rows;
        boolean[][][] squares;
        char[][] board;
        
        public void solveSudoku(char[][] board) {
            if (board == null || board.length == 0 || board[0].length == 0) return;
            int n = board.length, m = board[0].length;
            
            // These arrays show filled cells. Initially all of them are empty (filled = false)
            columns = new boolean[m][10];
            rows = new boolean[n][10];
            squares = new boolean[n / 3][m / 3][10];
            this.board = board;
            
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                   // check row, column and square
                   if (board[i][j] != '.') fillArrays(i, j, board[i][j] - '1', true);
                }
            }
            solveRecursively(0, 0);
        }
        
        private boolean solveRecursively(int r, int c) {
            // If we came to row next to last - then we found the combination
            if (r == board.length) return true;
            
            int nextR = r, nextC = c + 1;
            if (c == board[0].length - 1) {
                nextR = r + 1; 
                nextC = 0;
            }
            if (board[r][c] != '.') 
                return solveRecursively(nextR, nextC);
            
            // Trying all numbers for current cell
            for (int i = 0; i < 9; i++) {
                if (isValid(r, c, i)) {
                    fillArrays(r, c, i, true);
                    if (solveRecursively(nextR, nextC)) return true;
                    fillArrays(r, c, i, false);
                }
            }
            return false;
        }
        
        private boolean isValid(int r, int c, int v) {
            return !columns[c][v] && !rows[r][v] && !squares[r / 3][c / 3][v];
        }
        
        private void fillArrays(int r, int c, int v, boolean filled) {
            rows[r][v] = filled;
            columns[c][v] = filled;
            squares[r / 3][c / 3][v] = filled;
            board[r][c] = filled ? (char)(v + '1') : '.';
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.