Sudoku Solver

def solveSudoku(board):
    grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
    # row_used[r][d] is True when digit d already sits in row r; same for
    # columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
    row_used = [[False] * 10 for _ in range(9)]
    col_used = [[False] * 10 for _ in range(9)]
    box_used = [[False] * 10 for _ in range(9)]
    empties = []
    for r in range(9):
        for c in range(9):
            d = grid[r][c]
            if d:
                row_used[r][d] = col_used[c][d] = box_used[(r // 3) * 3 + c // 3][d] = True
            else:
                empties.append((r, c))

    def backtrack(k):
        if k == len(empties):
            return True
        r, c = empties[k]
        b = (r // 3) * 3 + c // 3
        for d in range(1, 10):
            if not row_used[r][d] and not col_used[c][d] and not box_used[b][d]:
                grid[r][c] = d
                row_used[r][d] = col_used[c][d] = box_used[b][d] = True
                if backtrack(k + 1):
                    return True
                row_used[r][d] = col_used[c][d] = box_used[b][d] = False
        grid[r][c] = 0
        return False

    backtrack(0)
    return ["".join(str(d) for d in row) for row in grid]

def solveSudoku(board):
    grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
    # Bit d of rows[r] is set when digit d already sits in row r; same for
    # columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
    rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
    for r in range(9):
        for c in range(9):
            d = grid[r][c]
            if d:
                rows[r] |= 1 << d
                cols[c] |= 1 << d
                boxes[(r // 3) * 3 + c // 3] |= 1 << d

    def backtrack():
        # Pick the empty cell with the fewest digits left (the first one on a tie).
        best_r, best_c, best_allowed, best_count = -1, -1, 0, 10
        for r in range(9):
            for c in range(9):
                if grid[r][c] == 0:
                    # Bits 1 to 9 of 0x3FE are the nine digits.
                    allowed = ~(rows[r] | cols[c] | boxes[(r // 3) * 3 + c // 3]) & 0x3FE
                    count = bin(allowed).count("1")
                    if count < best_count:
                        best_r, best_c, best_allowed, best_count = r, c, allowed, count
        if best_r == -1:
            return True  # no empty cell is left: the board is solved
        r, c = best_r, best_c
        b = (r // 3) * 3 + c // 3
        for d in range(1, 10):
            bit = 1 << d
            if best_allowed & bit:
                grid[r][c] = d
                rows[r] |= bit
                cols[c] |= bit
                boxes[b] |= bit
                if backtrack():
                    return True
                rows[r] ^= bit
                cols[c] ^= bit
                boxes[b] ^= bit
        grid[r][c] = 0
        return False

    backtrack()
    return ["".join(str(d) for d in row) for row in grid]