Python while循环提前终止

Question

我正在尝试制作一个Python程序，它可以大量地解决数独难题。它随机生成一个图块的坐标，如果该图块中已经有一个数字，它将重试。然后它生成一个介于1和9之间的数字放在那里，如果这个数字还不在那一行、列或节中，它将赋值并将这些坐标添加到被占用的平铺列表中。一旦所有的图块都填满了，它就应该退出循环并返回完成的网格。你知道吗

问题是，它总是在大约70次循环后无缘无故地停止，导致程序冻结。你知道吗

下面是我所说的函数的代码：

def populate(grid):
    usedCoords = []
    populated = False
    while not populated:
        x = random.randrange(len(grid))
        y = random.randrange(len(grid))
        while [x,y] in usedCoords:
            x = random.randrange(len(grid))
            y = random.randrange(len(grid))
        value = random.randrange(1, len(grid) + 1)
        if not rowCheck(grid, x, y, value) and not columnCheck(grid, x, y, value) and not squareCheck(grid, x, y, value):
            grid[x][y] = value
            usedCoords.append([x,y])
            print(len(usedCoords))
        if len(usedCoords) == len(grid) ** 2:
            populated = True
    return grid

下面是它引用的函数的代码：

def rowCheck(grid, x, y, value):
    for i in range(len(grid)):
        if not i == x:
            if grid[i][y] == value:
                return True
    return False

def columnCheck(grid, x, y, value):
    for i in range(len(grid)):
        if not i==y:
            if grid[x][i] == value:
                return True
    return False

def squareCheck(grid, x, y, value):
    grid2 = [0] * (sectionSide) #new grid for the specific section
    for i in range(len(grid2)):
        grid2[i] = [0] * sectionSide
    for i in range(x - (sectionSide - 1), x + sectionSide): #scanning only nearby coordinates
        for j in range(y - (sectionSide - 1), y + sectionSide):
            try:
                if i // sectionSide == x // sectionSide and j // sectionSide == y // sectionSide:
                    grid2[i][j] = grid[x][y]
            except IndexError:
                pass
    for i in range(len(grid2)):
        for j in range(len(grid2[i])):
            if grid2[i][j] == value and not (i == x and j == y):
                return True
    return False

Answer 1

可能还有其他问题，但代码的一个大问题是，如果发现创建了无法解决的板状态，就无法回溯。考虑一下如果您的代码将以下值放在板的前两行上会发生什么：

1 2 3 4 5 6 7 8 9
4 5 6 7 8 1 2 3

到目前为止放置的数字都是合法的，但是没有可以放在第二行最后一个空格的数字。我猜，当你的代码创建了一堆这样的董事会职位时，你的代码最终会被卡住，而这些职位不能有任何价值。如果没有任何合法的行动，它将继续循环永远。你知道吗

你需要一个更复杂的算法来避免这个问题。你知道吗