[LeetCode] 37. Sudoku Solver

Problem :  https://leetcode.com/problems/sudoku-solver/

Simulate the process to fill the empty cell with number 1 to 9, then validate whether it is a valid filling. If the number is valid, move the next empty cell. Otherwise back to the last cell and try another number.

Because all the previous filled numbers have been verified, it only needs to validate the number of current cell.

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        ROW = 9
        COLUMN = 9
        
        rowMask = [0] * 9
        columnMask = [0] * 9
        subboxMask = [0] * 9
        
        
        for y in range(ROW):
            for x in range(COLUMN):
                if board[y][x] != '.':
                    n = int(board[y][x])

                    rowMask[y] |= (1 << n)
                    columnMask[x] |= (1 << n)
                    
                    subboxMask[3*(y//3) + x//3] |= (1<<n)
        
        
        def helper(y, x):
            if y >= ROW:
                return True
            
            nx = x + 1
            ny = y
            
            if nx >= COLUMN:
                nx = 0
                ny += 1
            
            if board[y][x] != '.':
                return helper(ny, nx)
            else:
                for i in range(1, 10):
                    if rowMask[y] & (1 << i):
                        continue
                    
                    if columnMask[x] & (1 << i):
                        continue
                    
                    if subboxMask[3*(y//3) + x//3] & (1 << i):
                        continue
                    
                    board[y][x] = str(i)
                    rowMask[y] |= (1 << i)
                    columnMask[x] |= (1 << i)
                    subboxMask[3*(y//3) + x//3] |= (1 << i)
                    
                    if helper(ny, nx):
                        return True
                    
                    board[y][x] = '.'
                    rowMask[y] ^= (1 << i)
                    columnMask[x] ^= (1 << i)
                    subboxMask[3*(y//3) + x//3] ^= (1 << i)
                
                return False
        
        helper(0,0)

Edited on 08/21/2021. Use bitmask to improve performance.