数独求解程序运行过慢甚至无法完成，求问题排查指点

以下数独求解代码在空单元格较少时可以正常运行，但当网格g中添加更多0（代表空单元格）时，程序运行时间会大幅增加，甚至无法完成计算。并非需要代码评审，仅希望指出可能被忽略的问题点：

def is_solved(grid):
    for row, col in zip(grid, [*zip(*grid)]):
        for i in range(1, 10):
            if (i not in row) or (i not in col):
                return False
    return True


def square_available(rows, x, y, n):
    if 0 <= x < 3:
        rows = rows[:3]
    elif 3 <= x < 6:
        rows = rows[3:6]
    else:
        rows = rows[6:]
    if 0 <= y < 3:
        return not any([n in r[:3] for r in rows])
    elif 3 <= y < 6:
        return not any([n in r[3:6] for r in rows])
    else:
        return not any([n in r[6:] for r in rows])


def is_valid(grid, x, y, n):
    columns = [*zip(*grid)]
    return (
        square_available(grid, x, y, n) and n not in grid[x] and (n not in columns[y])
    )


def solve(grid, empty_cells):
    if is_solved(grid):
        return grid
    for x, y in empty_cells:
        for n in range(1, 10):
            if is_valid(grid, x, y, n):
                grid[x][y] = n
                empty_cells.remove((x, y))
                if solve(grid, empty_cells):
                    return grid
                else:
                    grid[x][y] = 0
                    empty_cells.append((x, y))


if __name__ == '__main__':
    solution = [
        [5, 3, 4, 6, 7, 8, 9, 1, 2],
        [6, 7, 2, 1, 9, 5, 3, 4, 8],
        [1, 9, 8, 3, 4, 2, 5, 6, 7],
        [8, 5, 9, 7, 6, 1, 4, 2, 3],
        [4, 2, 6, 8, 5, 3, 7, 9, 1],
        [7, 1, 3, 9, 2, 4, 8, 5, 6],
        [9, 6, 1, 5, 3, 7, 2, 8, 4],
        [2, 8, 7, 4, 1, 9, 6, 3, 5],
        [3, 4, 5, 2, 8, 6, 1, 7, 9],
    ]
    g = [
        [0, 0, 0, 6, 0, 8, 9, 1, 0],
        [6, 0, 2, 0, 9, 0, 3, 4, 0],
        [1, 9, 8, 3, 0, 0, 0, 6, 7],
        [0, 5, 9, 0, 0, 0, 4, 2, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 1, 3, 0, 2, 0, 8, 0, 0],
        [9, 6, 0, 5, 3, 7, 2, 8, 0],
        [2, 0, 0, 4, 1, 0, 0, 3, 0],
        [3, 4, 0, 2, 8, 0, 1, 7, 9],
    ]
    empty = []
    for i in range(9):
        for j in range(9):
            if not g[i][j]:
                empty.append((i, j))
    solved = solve(g, empty)
    assert g == solution

我尝试用以下方式重新实现，但结果更差，甚至无法解决原本能处理的数独问题：

from collections import defaultdict


def get_possibilities(rows, columns, x, y, visited):
    if (x, y) in visited:
        return visited[x, y]
    x0 = (x // 3) * 3
    x1 = x0 + 3
    y0 = (y // 3) * 3
    y1 = y0 + 3
    possibilities = set()
    for n in range(1, 10):
        square_rows = rows[x0:x1]
        for row in square_rows:
            if n in row[y0:y1]:
                continue
        if (n not in rows[x]) and (n not in columns[y]):
            visited[x, y].add(n)
            possibilities.add(n)
    return possibilities


def solve(rows, columns, empty_cells, visited):
    if not empty_cells:
        return rows
    for x, y in empty_cells:
        for n in get_possibilities(rows, columns, x, y, visited):
            rows[x][y] = n
            columns[y][x] = n
            visited[x, y].remove(n)
            if solve(rows, columns, empty_cells - {(x, y)}, visited):
                return rows
            else:
                rows[x][y] = 0
                columns[y][x] = 0
                visited[x, y].add(n)


if __name__ == '__main__':
    solution = [
        [5, 3, 4, 6, 7, 8, 9, 1, 2],
        [6, 7, 2, 1, 9, 5, 3, 4, 8],
        [1, 9, 8, 3, 4, 2, 5, 6, 7],
        [8, 5, 9, 7, 6, 1, 4, 2, 3],
        [4, 2, 6, 8, 5, 3, 7, 9, 1],
        [7, 1, 3, 9, 2, 4, 8, 5, 6],
        [9, 6, 1, 5, 3, 7, 2, 8, 4],
        [2, 8, 7, 4, 1, 9, 6, 3, 5],
        [3, 4, 5, 2, 8, 6, 1, 7, 9],
    ]
    r = [
        [0, 0, 0, 6, 0, 8, 9, 1, 0],
        [6, 0, 2, 0, 9, 0, 3, 4, 0],
        [1, 9, 8, 3, 0, 0, 0, 6, 7],
        [0, 5, 9, 0, 0, 0, 4, 2, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 1, 3, 0, 2, 0, 8, 0, 0],
        [9, 6, 0, 5, 3, 7, 2, 8, 0],
        [2, 0, 0, 4, 1, 0, 0, 3, 0],
        [3, 4, 0, 2, 8, 0, 1, 7, 9],
    ]
    c = [list(r) for r in [*zip(*r)]]
    cells = set()
    for i in range(9):
        for j in range(9):
            if not r[i][j]:
                cells.add((i, j))
    v = defaultdict(set)
    solved = solve(r, c, cells, v)
    assert r == solution

内容的提问来源于stack exchange，提问作者watch-this