leetcode37. 数独求教

来源:8-8 回溯法是经典人工智能的基础 N Queens

qq_山上山_0

2022-04-15

波波老司,觉得逻辑没有错啊,就是递归不出结果(python3)

class Solution(object):

    res = []
    used = []

    def ninegong(self,i, j, board, num): #判断当前9宫是否包含此数字
        hang = int(i / 3)
        lie = int(j / 3)
        for h in range(hang*3, hang*3 + 3):
            for l in range(lie*3, lie*3 + 3):
                if board[h][l] == str(num):
                    return True
        return False

    def hang(self, i, board, num): #行不包括此数字
        return str(num) in board[i]

    def lie(self, j, borad, num): #列不包括此数字
        return str(num) in [exm[j] for exm in borad]

    def putSudo(self, borad, row, col):
        if row == col:
            self.res.append(borad)
            return True
        for j in range(col):
            if borad[row][j] != '.':
                continue
            for k in range(1, col + 1):
                if self.used[row][j] == False and self.hang(row, borad, k) == False and self.lie(j, borad, k) == False and self.ninegong(row, j, borad, k) == False:
                    self.used[row][j] = True
                    borad[row][j] = str(k)
                    if self.putSudo(borad, row + 1, col):
                        return True
                    borad[row][j] = '.'
                    self.used[row][j] = False
            return False
        return True # 这里不确定返回True还是False 貌似true是有解的

    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        self.res = []
        row = len(board)
        if row < 1:
            return []
        col = len(board[0])
        self.used = [[False]*row for i in range(col)]
        for i in range(row):
            for j in range(col):
                if board[i][j] == '.':
                    continue
                self.used[i][j] = True
        self.putSudo(board, 0, col)
        return self.res[0]
写回答

1回答

liuyubobobo

2022-04-15

抱歉,你这样扔给我一片代码我没法给你调试。我只能告诉你,你现在代码的问题,根本不是得到的解是不是正确的问题,而是根本得不到解的问题。


一个简单的调试方法是,用一个完整的数独,只扣掉一个数字。现在你的程序都无法拿到答案,


请使用如下的测试用例调试(只有 0, 0 的位置没有填数)去调试你的程序,看看你的程序为什么没有得到解。

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


依然是,请把你的问题锁定在:

你认为在什么测试用例下,你认为在程序执行的某一步,你觉得某个变量应该得到什么结果,但实际却是什么结果,所以你不理解。

如果你能把问题锁定成这个样子,说明你有调试,说明你有真的疑问,我接大你的疑问才有意义,你也能进步。


继续加油!:)

0
3
liuyubobobo
回复
qq_山上山_0
每一行里有可能有多个需要被填充的数字。当前行的一个数字搜索之后,不意味着就要搜索下一行,当前行后面可能还有别的数字需要搜索。继续加油!:)
2022-04-18
共3条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程