我有一个递归求解数独的代码,并打印出它找到的一个解. 但我想找出多种解决方案的数量. 您将如何修改代码以查找所有可能的解决方案并给出解决方案的数量? 谢谢!:)

代码:


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


def solve(bo):
    find = find_empty(bo)
    if not find:
        return True
    else:
        row, col = find

    for num in range(1,10):
        if valid(bo, num, (row, col)):
            bo[row][col] = num          

            if solve(bo):                 
                return True

            bo[row][col] = 0              

    return False


def valid(bo, num, pos):
    # Check row
    for field in range(len(bo[0])):                     
        if bo[pos[0]][field] == num and pos[1] != field:
            return False

    # Check column
    for line in range(len(bo)):
        if bo[line][pos[1]] == num and pos[0] != line:
            return False

    # Check box
    box_x = pos[1] // 3
    box_y = pos[0] // 3

    for i in range(box_y*3, box_y*3 + 3):
        for j in range(box_x * 3, box_x*3 + 3):
            if bo[i][j] == num and (i,j) != pos:
                return False

    return True


def print_board(bo):
    for i in range(len(bo)):
        if i % 3 == 0 and i != 0:
            print("- - - - - - - - - - - - - ")

        for j in range(len(bo[0])):
            if j % 3 == 0 and j != 0:
                print(" | ", end="")

            if j == 8:
                print(bo[i][j])
            else:
                print(str(bo[i][j]) + " ", end="")


def find_empty(bo):
    for i in range(len(bo)):
        for j in range(len(bo[0])):
            if bo[i][j] == 0:
                return (i, j)  # row, col

    return None
if __name__ == "__main__":
    print_board(board)
    solve(board)
    print("___________________")
    print("")
    print_board(board)


我已经try 在Solve(Bo)函数中将返回True项更改为Return None/Delete(对于两个返回项),它将继续… 然后算法继续并找到多个解,但最终将最后找到的解中的正确数字再次填入0.这就是随后打印出的解.

推荐答案

如所问:

您将如何修改代码以查找所有可能的解决方案并给出解决方案的数量?

如果您不想返回("分发")解决方案本身,而是number个解决方案,那么您需要维护一个计数器,并使用从递归调用中返回的计数来更新拥有的计数器:

def solve(bo):
    find = find_empty(bo)
    if not find:
        return 1

    count = 0
    row, col = find
    for num in range(1, 10):
        if valid(bo, num, (row, col)):
            bo[row][col] = num          
            count += solve(bo)
            bo[row][col] = 0              

    return count

在主程序中,您将不再打印电路板,因为您现在并不期待填充的电路板,而是一个数字:

    print(solve(board))  # Will output 1 for your example board.

获取所有解决方案

如果你不仅想知道count,而且想知道每个单独的解本身,那么我会找一个母函数,每个解yields:

def solve(bo):
    find = find_empty(bo)
    if not find:
        yield [row[:] for row in bo]  # Make a copy
        return
        
    row, col = find
    for num in range(1, 10):
        if valid(bo, num, (row, col)):
            bo[row][col] = num          
            yield from solve(bo)
            bo[row][col] = 0              

然后,主程序可以执行以下操作:

    count = 0
    for solution in solve(board):
        print("SOLUTION:")
        print_board(solution)
        count += 1
    print("NUMBER of SOLUTIONS:", count)

Python相关问答推荐

python panda ExcelWriter切换动态公式到数组公式

Tensorflow tokenizer问题.num_words到底做了什么?

从嵌套极轴列的列表中删除元素

裁剪数字.nd数组引发-ValueError:无法将空图像写入JPEG

Django在一个不是ForeignKey的字段上加入'

Seaborn散点图使用多个不同的标记而不是点

如何从数据框列中提取特定部分并将该值填充到其他列中?

Django抛出重复的键值违反唯一约束错误

使用xlsxWriter在EXCEL中为数据帧的各行上色

为什么按下按钮后屏幕的 colored颜色 保持不变?

关于数字S种子序列内部工作原理的困惑

如何在Django查询集中生成带有值列表的带注释的字段?

使用元组扩展字典的产品挑战

搜索结果未显示.我的URL选项卡显示:http://127.0.0.1:8000/search?";,而不是这个:";http://127.0.0.1:8000/search?q=name";

如何在Python中使用Polars向SQLite数据库写入数据?

向量化数据帧中的折叠过程

如何让QML菜单考虑布局镜像?

将MultiIndex列的级别转换为具有值的列(取消堆叠列)

Lambda调用未处理,3秒后超时?

为什么在涉及int和调用str()的多重继承的情况下,Python3.7和3.10的MRO似乎有所不同?