Clean python code with Bit Manipulation and Backtracking


  • 0
    class Solution(object):
        def search(self, count, board, horizontal, vertical, grid):
            while count < 81:
                i, j = divmod(count, 9)
                if board[i][j] == '.':
                    break
                count += 1
            else:
                return True
    
            for candidate in xrange(1, 10):
                shift = 1 << candidate
                if not (horizontal[i] & shift or vertical[j] & shift or
                        grid[i/3][j/3] & shift):
    
                    board[i][j] = str(candidate)
                    horizontal[i] |= shift
                    vertical[j] |= shift
                    grid[i/3][j/3] |= shift
    
                    if self.search(count + 1, board, horizontal, vertical, grid):
                        return True
    
                    shift = ~shift
    
                    board[i][j] = '.'
                    horizontal[i] &= shift
                    vertical[j] &= shift
                    grid[i/3][j/3] &= shift
    
            return False
    
        def solveSudoku(self, board):
            horizontal, vertical, grid = [1]*9, [1]*9, [[1]*3 for _ in xrange(3)]
    
            for i, row in enumerate(board):
                for j, val in enumerate(row):
                    if val == '.':
                        continue
    
                    shift = 1 << ord(val) - 48
    
                    horizontal[i] |= shift
                    vertical[j] |= shift
                    grid[i/3][j/3] |= shift
    
            self.search(0, board, horizontal, vertical, grid)

Log in to reply
 

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