鱼C论坛

 找回密码
 立即注册
查看: 1084|回复: 1

回溯法提问,像大神请教

[复制链接]
发表于 2018-3-29 14:34:43 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
自己写了一个解数独的程序(回溯法)但是为什么没有结果?望大神指点
import sys
sys.setrecursionlimit(1000000) #例如这里设置为一百万
sudoku = [
    [5,3,4,6,7,0,0,0,2],
    [6,0,0,1,9,5,0,0,0],
    [0,9,8,0,0,0,0,6,0],
    [8,5,9,0,6,0,0,0,3],
    [4,0,0,8,0,3,0,0,1],
    [7,0,0,0,2,0,0,0,6],
    [0,6,0,0,0,0,2,8,0],
    [0,0,0,4,1,9,0,0,5],
    [3,4,5,2,8,6,0,7,9]
]

def conflict(x,h,l,num):
    if num in x[h]:
        return False
    for i in range(9):
        if num == x[i][l]:
            return False
    start_h = h//3
    start_l = l//3
    list_jiugong = []
    for i in range(3):
        for j in range(3):
            list_jiugong.append(x[start_h+i][start_l+j])
    if num in list_jiugong:
        return False
    return True

def solve(sudoku):
    for h in range(9):
        for l in range(9):
            if sudoku[h][l] == 0:
                for num in [1,2,3,4,5,6,7,8,9]:
                    if conflict(sudoku,h,l,num) and solve(sudoku):
                        sudoku[h][l] = num
                        return True
                    sudoku[h][l] = 0
                return False
    return True


if solve(sudoku):
    print(sudoku)

结果只有一个Process finished with exit code 0 并没有打印Sudoku?请大神指点,谢谢
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2018-3-29 14:42:32 | 显示全部楼层
1楼solve函数改成2楼内容
def solve(sudoku):
    for h in range(9):
        for l in range(9):
            if sudoku[h][l] == 0:
                for num in [1,2,3,4,5,6,7,8,9]:
                    sudoku[h][l] = num
                    if conflict(sudoku,h,l,num) and solve(sudoku):
                        return True
                    sudoku[h][l] = 0
                return False
    return True
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-12-28 23:34

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表