Short Java Solution using Bit Manipulation


  • 0
    C
    public class Solution {
        public boolean isValidSudoku(char[][] board) {
            int[] rows = new int[9], cols = new int[9], sqrs = new int[9];
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] == '.') continue;
                    int mask = 1 << (board[i][j] - '0');
                    int sqrNum = (i / 3) * 3 + (j / 3);
                    if ((rows[i] & mask) == 0 && (cols[j] & mask) == 0 && (sqrs[sqrNum] & mask) == 0) {
                        rows[i] |= mask;
                        cols[j] |= mask;
                        sqrs[sqrNum] |= mask;
                    } else {
                        return false;
                    }
                }
            }
            return true;
        }
    }
    

  • 0
    M

    Can you please explain what does the masking do? Is it just a representation of the number in bits?

    int mask = 1 << (board[i][j] - '0');

    Also, what does this line represent?

    int sqrNum = (i / 3) * 3 + (j / 3);

    I understand that doing an AND with mask means it doesn't exist and doing an OR sets the mask but what do the arrays rows, cols and sqrs represent?

    Thanks and your code is cleaner than other solutions I have found here. Best.


Log in to reply
 

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