求解数独问题的Python回溯算法

Question

从一些python代码开始，我试图使用发布的回溯算法here制作一个数独解算器

所以我现在有这个：

SUDOKU= [[0, 6, 0, 1, 0, 4, 0, 5, 0],
     [0, 0, 8, 3, 0, 5, 6, 0, 0],
     [2, 0, 0, 0, 0, 0, 0, 0, 1],
     [8, 0, 0, 4, 0, 7, 0, 0, 6],
     [0, 0, 6, 0, 0, 0, 3, 0, 0],
     [7, 0, 0, 9, 0, 1, 0, 0, 4],
     [5, 0, 0, 0, 0, 0, 0, 0, 2],
     [0, 0, 7, 2, 0, 6, 9, 0, 9],
     [0, 4, 0, 5, 0, 8, 2, 7, 0]]

     sublist = []

def validate(value, y, x, sudoku):

    # check linea
    for idx in range(0,9):
        if sudoku[y][idx] == value:
            return False   
    for idy in range(0, 9):
        if sudoku[idy][x] == value:
            return False
    return True


def validate_square(value, y, x, sudoku):

    if y < 3 and x < 3:
        aux_list = [aux_list[0:3] for aux_list in sudoku[0:3]]
        if value in [j for i in aux_list for j in i]:
            return False
        else:
            return True

    elif y < 3 and (x >= 3 and x < 6):
        aux_list = [aux_list[3:6] for aux_list in sudoku[0:3]]
        if value in [j for i in aux_list for j in i]:
            return False
        else:
            return True

    elif y < 3 and (x >= 6 and x < 9):
        aux_list = [aux_list[6:9] for aux_list in sudoku[0:3]]
        if value in [j for i in aux_list for j in i]:
            return False
        else:
            return True

    elif (y >= 3 and y < 6) and x < 3:
        aux_list = [aux_list[0:3] for aux_list in sudoku[3:6]]
        if value in [j for i in aux_list for j in i]:
            return False
        else:
            return True

    elif (y >= 3 and y < 6) and (x >= 3 and x < 6):
        aux_list = [aux_list[3:6] for aux_list in sudoku[3:6]]
        if value in [j for i in aux_list for j in i]:
            return False
        else:
            return True

    elif (y >= 3 and y <6) and (x >= 6 and x < 9):
        aux_list = [aux_list[6:9] for aux_list in sudoku[3:6]]
        if value in [j for i in aux_list for j in i]:
            return False
        else:
            return True

    elif (y >= 6 and y < 9) and x < 3:
        aux_list = [aux_list[0:3] for aux_list in sudoku[6:9]]
        if value in [j for i in aux_list for j in i]:
            return False
        else:
            return True

    elif (y >= 6 and y < 9) and (x >= 3 and x < 6):
        aux_list = [aux_list[3:6] for aux_list in sudoku[6:9]]
        if value in [j for i in aux_list for j in i]:
            return False
        else:
            return True

    elif (y >= 6 and y < 9) and (x >= 6 and x < 9):
        aux_list = [aux_list[6:9] for aux_list in sudoku[6:9]]
        if value in [j for i in aux_list for j in i]:
            return False
        else:
            return True
    else:
        return True

def auto_complete(sudoku):
    for idy in range(0,9):
        for idx in range(0,9):
            if sudoku[idy][idx] == 0:
                for attempt in range(1, 10):
                    if validate(attempt, idy, idx, sudoku) == True and validate_square(attempt, idy, idx, sudoku) == True:
                        sudoku[idy][idx] = attempt

if __name__ == "__main__":
    auto_complete(SUDOKU)
    for i in SUDOKU:
        print(i)

这就是我得到的解决方案：

[9, 6, 3, 1, 8, 4, 7, 5, 0]
[4, 7, 8, 3, 9, 5, 6, 2, 0]
[2, 5, 0, 7, 6, 0, 8, 9, 1]
[8, 9, 5, 4, 3, 7, 1, 0, 6]
[1, 2, 6, 8, 5, 0, 3, 0, 7]
[7, 3, 0, 9, 2, 1, 5, 8, 4]
[5, 8, 9, 0, 7, 3, 4, 6, 2]
[3, 1, 7, 2, 4, 6, 9, 0, 9]
[6, 4, 0, 5, 1, 8, 2, 7, 3]

这是一个期望值（正确的解决方案）： sudoku

在这一点上，我有一个算法，可以部分地做回溯，但当它涉及到一个值，不适合它的单元格（行，行，平方违反）它只是让它留空，从维基百科帖子我明白，我应该去一个位置向后（减去1到idx可能？）向该单元格中添加1并重新验证该值。你知道吗

我很迷茫，所以有什么建议，如何改善这个代码在pythonic的方式？你知道吗

另外，列表列表是构造数独数据的最佳方式吗？它们的工作方式似乎与数组有点不同（我就是从数组中来的，反正不是专家）

谢谢大家的阅读！你知道吗