Java solution using brute-force search, backtracking and bitwise operations


  • 0
    B

    I solved this by using arrays to keep track of the available digits. There's one array for the rows, one for the columns and one for the squares.
    For example, row[0] = 109 (001110101 in binary) means that digits 1, 3, 5, 6 and 7 have not yet been used in the first row.

    With this approach, checking if a digit is available, updating the board and arrays and backtracking all take constant-time by using simple bitwise operations.

    Then, I use a recursive method starting from the first cell. Also, I don't use any division or modulo operations to get the square indexes which is a little bit faster.

    private static final int SIZE = 9;
    
    private static final int SQR_SIZE = 3;
    
    private static final int DBL_SQR_SIZE = 3 << 1;
    
    public static void solveSudoku(char[][] board) {
        // Each array contains the available digits in binary
        // If the k-th bit is set to 1, it means the digit k+1 has not yet been used
        int[] rows = new int[SIZE];
        int[] cols = new int[SIZE];
        int[] sqrs = new int[SIZE];
        // Initialization. At first, the 9 digits are available
        int allAvailable = -1 >>> 23;
        for (int i = 0; i < SIZE; ++i) {
            rows[i] = allAvailable;
            cols[i] = allAvailable;
            sqrs[i] = allAvailable;
        }
        
        // Remove the prefilled digits
        for (int row = 0; row < SIZE; ++row) {
            int sqrRow = (row < SQR_SIZE ? 0 : (row < DBL_SQR_SIZE ? 3 : 6));
            for (int col = 0; col < SIZE; ++col) {
                char cell = board[row][col];
                if (cell == '.')
                    continue;
                int cellBitmask = 1 << (cell - '1');
                int sqr = sqrRow + (col < SQR_SIZE ? 0 : (col < DBL_SQR_SIZE ? 1 : 2));
                // XOR removes the specified bit
                rows[row] ^= cellBitmask;
                cols[col] ^= cellBitmask;
                sqrs[sqr] ^= cellBitmask;
            }
        }
        
        // Start solving at the top-left corner
        solveSudoku(board, rows, cols, sqrs, 0, 0);
    }
    
    
    private static boolean solveSudoku(char[][] board, int[] rows, int[] cols, int[] sqrs, int row, int col) {
        // Correct coordinates if col is too big
        if (col == SIZE) {
            ++row;
            col = 0;
        }
        // Sudoku solved
        if (row == SIZE)
            return true;
        
        // Cell already filled, directly solve the next one
        if (board[row][col] != '.')
            return solveSudoku(board, rows, cols, sqrs, row, col + 1);
        
        // Compute square index
        int sqr = (row < SQR_SIZE ? 0 : (row < DBL_SQR_SIZE ? 3 : 6))
                + (col < SQR_SIZE ? 0 : (col < DBL_SQR_SIZE ? 1 : 2));
        
        // Brute-force search through all available values
        for (int i = 0, bitmask = 1; i < SIZE; ++i, bitmask <<= 1) {
            // If value is already used in the row or the column or the square, skip it
            if (((rows[row] & bitmask) == 0) || ((cols[col] & bitmask) == 0) || ((sqrs[sqr] & bitmask) == 0))
                continue;
            // Value is available. Remove it from the available lists and update board
            rows[row] ^= bitmask;
            cols[col] ^= bitmask;
            sqrs[sqr] ^= bitmask;
            board[row][col] = (char) (i + '1');
            // If a solution is found, returns with the board updated
            if (solveSudoku(board, rows, cols, sqrs, row, col + 1))
                return true;
            // Solution not found, backtrack
            board[row][col] = '.';
            rows[row] |= bitmask;
            cols[col] |= bitmask;
            sqrs[sqr] |= bitmask;
        }
        return false;
    }

Log in to reply
 

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