number theory - Improve upon algorithm for finding a specific perfect square in a range of two very large integers $(10^{28})$

Assume you are given a set of digits that represent every other digit in a perfect square, how can you find the root of a number that would have the same pattern - guaranteed to exist and to be unique.

For example, $8*7*6$, if you replace the asterisks with all $0$’s and all $9$’s you would have $89796$ and $80706$. If you take the square of each, you get $299$ and $284$ (rounding to an integer). You can then iterate through each integer from $284$, to $299$, square them, until you find a number that matches the same pattern. Turns out the answer is $286^2$ which equals $81796$.

We also know with the units digit being a $6$, that the first two digits are limited to a set of numbers, 96 being one of them. So just by knowing the last digit is $6$, one partial solution could be $8*796$, but could also be $8*744$. Regardless, there are very few options and the result set is narrowed. Just by applying $0-9$ to $8*796$, iterate through them, you would stumble across 81796 with a square root of $286$.

If the problem was restricted to perfect squares with relatively smaller numbers, the solution would be simple - just find the max/min roots $(284-299)$, square them and find the perfect squares that satisfy the pattern of $8*7*6$, for example. Another example is $1*2*3*4$ where the square root is $1312^2 = 1721344$.

However, using this algorithm, my program takes forever to run with very large integers. Seems like there would be a way of building the square by applying perfect square properties, or applying another algorithm that reduces the possibilities.

EDITED:
The larger examples are: $23209192748299230494155021081$ which is a perfect square and its root is: $152345635803259$. The numbers provided are: $229978920915201$, which, using the example above: $2*2*9*9*7*8*9*2*0*9*1*5*2*0*1$ with the asterisks being a placeholder for a digit. Another example: $232091909800969$ is the perfect square, and the square root is: $15234563$. The numbers provided are:$22999099$ meaning: $2*2*9*9*9*0*9*9$ with the asterisks being placeholders. The algorithm I detailed above (finding the min/max roots, squaring, and comparing) works fine for the perfect square: $232091909800969$, but not on the perfect square: $23209192748299230494155021081$ -- takes too long.

Hope this makes sense.

Edited:
The following is the code I used. It is Python 3.6.3 running on a MacPro 10.13.3, 2.7 GHz 12-Core Intel Xeon E5, 64GB RAM:

# !/bin/python3

import sys, math, time


def removeOdds(num):
    result = ""
    num = str(num)
    for i in range(0, len(num), 2):
        result = result + num[i]

    return int(result)


def findRoot(n, num):
    def perfect_squares():
        if num[-1] == 0:
            return (x for x in range(lowSq, highSq + 1) if (x % 10 == 0) and removeOdds(x ** 2) == num1)
        if num[-1] == 1:
            return (x for x in range(lowSq, highSq + 1) if (x % 10 == 1 or x % 10 == 9) and removeOdds(x ** 2) == num1)
        if num[-1] == 4:

            return (x for x in range(lowSq, highSq + 1) if (x % 10 == 2 or x % 10 == 8) and removeOdds(x ** 2) == num1)
        if num[-1] == 5:
            return (x for x in range(lowSq, highSq + 1) if (x % 10 == 5) and removeOdds(x ** 2) == num1)
        if num[-1] == 6:
            return (x for x in range(lowSq, highSq + 1) if (x % 10 == 4 or x % 10 == 6) and removeOdds(x ** 2) == num1)
        if num[-1] == 9:
            return (x for x in range(lowSq, highSq + 1) if (x % 10 == 3 or x % 10 == 7) and removeOdds(x ** 2) == num1)

    low = int('0'.join(str(x) for x in num))
    high = int('9'.join(str(x) for x in num))

    num1 = int(''.join(str(x) for x in num))
    lowSq = int(math.ceil(math.sqrt(low)))
    highSq = int(math.floor(math.sqrt(high)))
    x = perfect_squares()
    y = x.__next__()
    return y


def main(n, num):
    start = time.clock()

    root = findRoot(n, num)
    print(root)
    print ("execution time: ", time.clock() - start)


if __name__ == '__main__':
    n  = 3
    num = [8,7,6]
    #n = 4
    #num = [1, 2, 3, 4]

    # n = 8 takes approx 0.89 sec to run, expected result: 15234563
    #n = 8  # int(input().strip())
    #num = [2, 2, 9, 9, 9, 0, 9, 9]  # list(map(int, input().strip().split(' ')))
    # n = 10 takes approx 120 sec to run, expected result: 1234567890
    # n = 10
    # num = [1, 2, 1, 7, 7, 0, 9, 5, 1, 0]
    # n = 15 I've never been patient enough to see if it will complete
    #n = 15
    #num = [2, 2, 9, 9, 7, 8, 9, 2, 0, 9, 1, 5, 2, 0, 1]


    main(n, num)