[LeetCode] 36. Valid Sudoku

1. Question

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Example 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false

Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

2. Thoughts

3. Tips learned

3.1. Print values in binary

To print values in bits in Python, you can use the bin() function, which converts an integer number to a binary string prefixed with "0b". If you want to print the bits without the "0b" prefix, you can slice the string to remove the first two characters. For more sophisticated formatting, you might also use format strings. Here are a few examples:

Using bin() for Simple Conversion

number = 10  # Example number
bits = bin(number)
print(bits)  # Outputs '0b1010'

Removing the '0b' Prefix

number = 10
bits = bin(number)[2:]  # Slice off the first two characters
print(bits)  # Outputs '1010'

4. My solution

class Solution:
    def isDuplicate(self,digit,num):
        new_num = digit ^ (1 << (num-1))

        #Exist Duplicate
        if new_num < digit:
            return -1
        else:
            return new_num

    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for i in range(9):
            digits_row = 1 << 9
            digits_col = 1 << 9
            for j in range(9):
                num_str_row = board[i][j]               
                num_str_col = board[j][i]
                
                if num_str_row != '.':
                    digits_row = self.isDuplicate(digits_row, int(num_str_row))
                    if digits_row == -1:
                        return False

                if num_str_col != '.':
                    digits_col = self.isDuplicate(digits_col, int(num_str_col))
                    if digits_col == -1:
                        return False

        threeByThree = [[0,1,2],[3,4,5],[6,7,8]]
        for I in threeByThree:
            for J in threeByThree:
                digits=1 << 9
                for i in I:
                    for j in J:
                        num_str = board[i][j]               
                        if num_str != '.':
                            digits = self.isDuplicate(digits, int(num_str))
                            if digits == -1:
                                return False

        return True

8/8 cases passed (89 ms)
Your runtime beats 75.01% of python3 submissions
Your memory usage beats 64.12 % of python3 submissions (16.54 MB)

5. AI Solution and Improvements

Your approach to validating a Sudoku board by using bitwise operations for efficiency is quite ingenious. It leverages bit manipulation to track the existence of digits in rows, columns, and sub-boxes. This method provides a compact and fast way to check for duplicates. However, your implementation could be slightly refined for readability and efficiency. Here are a few suggestions and an alternative approach:

Improvements to Your Approach

1. Clarify isDuplicate Method: Your isDuplicate function checks for the existence of a digit by using bitwise operations, which is clever. However, the name isDuplicate might be slightly misleading since it actually updates the tracker or returns an error code -1 if a duplicate is found. Consider renaming this method to reflect its functionality more accurately, such as updateDigitTracker.

2. Optimize 3x3 Sub-Box Checking: Your method for checking the 3x3 sub-boxes is correct but involves nested loops that make it slightly harder to follow. It's already quite efficient, but consider using a single loop to iterate over the sub-boxes with calculated indices to make it clearer.

Alternative Approach: Using Sets

If you're open to an alternative that doesn't use bitwise operations but is still efficient and perhaps more straightforward, consider using sets to track seen numbers in rows, columns, and boxes.

class Solution:
    def isValidSudoku(self, board):
        row_sets = [set() for _ in range(9)]
        col_sets = [set() for _ in range(9)]
        box_sets = [set() for _ in range(9)]
        
        for row in range(9):
            for col in range(9):
                num = board[row][col]
                if num == '.':
                    continue
                
                # Check the box index
                box_index = (row // 3) * 3 + col // 3
                
                if (num in row_sets[row] or 
                    num in col_sets[col] or 
                    num in box_sets[box_index]):
                    return False
                
                row_sets[row].add(num)
                col_sets[col].add(num)
                box_sets[box_index].add(num)
                
        return True

This version uses three lists of sets to keep track of the numbers that have appeared in each row, column, and 3x3 sub-box. It iterates through each cell on the board and adds the number to the corresponding row, column, and box sets. If a number already exists in any of these sets, the board is invalid.

Conclusion

Both approaches have their merits. The bitwise operation approach is compact and fast, especially for large datasets or in environments where memory usage is a concern. The set-based approach is more readable and straightforward, making it easier to understand and maintain. Depending on your priorities (speed, memory usage, readability), you can choose the approach that best fits your needs.