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"]]
依然是,请把你的问题锁定在:
你认为在什么测试用例下,你认为在程序执行的某一步,你觉得某个变量应该得到什么结果,但实际却是什么结果,所以你不理解。
如果你能把问题锁定成这个样子,说明你有调试,说明你有真的疑问,我接大你的疑问才有意义,你也能进步。
继续加油!:)
032022-04-18
相似问题