Yet another Java solution


  • 0
    S

    Hi guys!

    In my recursive solution I tried to not simply pick all possible values for an empty cell but to make two optimisations:

    1. We pick only valid values that are not violating the constraints of a row, column and box.

    2. We choose as the next cell to fill the one with the minimum number of possible values.

    Check it out below.


    public class Solution {
        
        /* Auxiliary class for empty cells with the set of possible values. */ 
        private static class Cell {
            public final int x, y;
            public final Set<Integer> possibilities;
            public Cell(int x, int y, Set<Integer> possibilities) {
                this.x = x; this.y = y; this.possibilities = possibilities;
            }
        }
        
        /* Returns all possible values for the given cell. */
        private static Set<Integer> getPossibilities(char[][] board, int x, int y) {
            Set<Integer> res = new HashSet<>(Arrays.asList(1,2,3,4,5,6,7,8,9));
            for (int i = 0; i < 9; i++) {
                res.remove(board[x][i] - '0');
                res.remove(board[i][y] - '0');
                res.remove(board[3*(x/3) + i/3][3*(y/3) + i%3] - '0');
            }
            return res;
        }
        
        /* Returns the cell with the minimum number of possible values. */
        private static Cell findBestEmptyCell(char[][] board) {
            Cell res = null;
            int minPos = Integer.MAX_VALUE;
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    if (board[i][j] == '.') {
                        Set<Integer> pos = getPossibilities(board, i, j);
                        if (pos.size() < minPos) {
                            res = new Cell(i, j, pos);
                            minPos = pos.size();
                        }
                    }
                }
            }
            return res;
        }
        
        /* 
         * 1. Finds the best empty cell with its' possible values.
         * 2. Checks if the best cell is with 0 possible values. 
         *    If so then the current board is not solvable 
         *    and backtracks with false return value. 
         * 3. If the board is solvable tries all possible values for the best cell 
         *    and makes further recursive calls.
         */
        public static boolean recSolve(char[][] board) {
            Cell best = findBestEmptyCell(board);
            if (best != null) {
                if (!best.possibilities.isEmpty()) {
                    for (int p : best.possibilities) {
                        board[best.x][best.y] = (char) (p + '0');
                        if (recSolve(board)) return true;
                    }
                    board[best.x][best.y] = '.';
                }
                return false;
            }
            return true;
        }
    
        public void solveSudoku(char[][] board) {
            recSolve(board);
        }
    }

Log in to reply
 

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