为什么我的数独求解 Python 代码 运行 使用与更快代码相同的逻辑如此缓慢？
Why is my Sudoku Solving Python code running so slow using the same logic as a faster code?
我在 python 中编写了一个数独解法代码，紧跟 GeeksForGeeks 中给出的解法，但我的代码 运行 速度非常慢，尽管产生了正确的结果。
运行 用了 2 多分钟，而 GeeksForGeeks 代码用了不到一秒就解决了 2 个这样的数独：
我的代码：
import time
def printgrid(grid):
for i in range(9):
for j in range(9):
print(grid[i][j], end=' ')
print("")
def checkLocation(grid,x,y,val):
if val in grid[x]:
#print("x"+str(grid[x]))
return False
elif True in [val == grid[i][y] for i in range(9)]:
#print("y"+str(grid[:][y]))
return False
return True
def checkGrid(grid):
if True in [0 in grid[i] for i in range(9)]:
#print("grid has empty spots")
return False
rowmap = {1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
colmap = {1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
squmap = {1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
for i in range(9):
for j in range(9):
if rowmap[grid[i][j]] == 0:
rowmap[grid[i][j]] = 1
else:
return False
if colmap[grid[j][i]] == 0:
colmap[grid[j][i]] = 1
else:
return False
rowmap = {1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
colmap = {1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
for i in [0,3,6]:
for j in [0,3,6]:
for tx in [0,1,2]:
for ty in [0,1,2]:
if squmap[grid[i+tx][j+ty]] == 0:
squmap[grid[i+tx][j+ty]] = 1
else:
return False
squmap = {1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
return True
def solveSudoku(grid):
if checkGrid(grid):
return True
else:
for i in range(9):
for j in range(9):
if grid[i][j]!=0:
continue
else:
for k in range(1,10):
if checkLocation(grid,i,j,k):
#print("Tried "+str(k))
grid[i][j] = k
#print(grid)
if solveSudoku(grid):
return True
grid[i][j] = 0
return False
mydoku = [[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 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],
[0, 0, 0, 0, 8, 0, 0, 7, 9]]
codoku = [[5, 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]]
print(checkLocation(mydoku,1,1,2))
print(checkGrid(codoku))
#print(checkLocation(codoku,8,8,9))
#print(solveSudoku(codoku))
#printgrid(codoku)
#print(checkLocation(mydoku,0,3,6))
start = time.time()
print(solveSudoku(mydoku))
printgrid(mydoku)
diff = time.time() - start
print(diff)
输出：
True
True
5 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
135.41240525245667
GeeksForGeeks 代码：（删除评论）
import time
def print_grid(arr):
for i in range(9):
for j in range(9):
print(arr[i][j], end=' ')
print("")
def find_empty_location(arr, l):
for row in range(9):
for col in range(9):
if(arr[row][col]== 0):
l[0]= row
l[1]= col
return True
return False
def used_in_row(arr, row, num):
for i in range(9):
if(arr[row][i] == num):
return True
return False
def used_in_col(arr, col, num):
for i in range(9):
if(arr[i][col] == num):
return True
return False
def used_in_box(arr, row, col, num):
for i in range(3):
for j in range(3):
if(arr[i + row][j + col] == num):
return True
return False
def check_location_is_safe(arr, row, col, num):
return not used_in_row(arr, row, num) and not used_in_col(arr, col, num) and not used_in_box(arr, row - row % 3, col - col % 3, num)
def solve_sudoku(arr):
l =[0, 0]
if(not find_empty_location(arr, l)):
return True
row = l[0]
col = l[1]
for num in range(1, 10):
if(check_location_is_safe(arr,
row, col, num)):
arr[row][col]= num
if(solve_sudoku(arr)):
return True
arr[row][col] = 0
return False
if __name__=="__main__":
grid =[[0 for x in range(9)]for y in range(9)]
grid =[[3, 0, 6, 5, 0, 8, 4, 0, 0],
[5, 2, 0, 0, 0, 0, 0, 0, 0],
[0, 8, 7, 0, 0, 0, 0, 3, 1],
[0, 0, 3, 0, 1, 0, 0, 8, 0],
[9, 0, 0, 8, 6, 3, 0, 0, 5],
[0, 5, 0, 0, 9, 0, 6, 0, 0],
[1, 3, 0, 0, 0, 0, 2, 5, 0],
[0, 0, 0, 0, 0, 0, 0, 7, 4],
[0, 0, 5, 2, 0, 6, 3, 0, 0]]
start = time.time()
if(solve_sudoku(grid)):
print_grid(grid)
else:
print("No solution exists")
end = time.time()
print(end-start)
mydoku = [["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
for i in range(9):
for j in range(9):
if mydoku[i][j] == '.':
mydoku[i][j] = 0
else:
mydoku[i][j] = int(mydoku[i][j])
print("")
start = time.time()
if solve_sudoku(mydoku):
print_grid(mydoku)
else:
print("No Solution Exists")
end = time.time()
print(end-start)
输出：
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9
0.013003110885620117
5 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.05815267562866211
我的 code/coding 风格有什么问题导致我的代码花费了这么多时间？
请帮忙
如果您想知道为什么您的代码运行缓慢，运行 它在分析器 下。例如 Python.
附带的 cProfile
我已将您的代码保存为 mydoku.py，运行 以下命令：
python -m cProfile mydoku.py
这产生了以下输出：
True
True
5 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
155.7312035560608
186321197 function calls (173893648 primitive calls) in 155.731 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 155.731 155.731 mydoku.py:1(<module>)
111832944 35.234 0.000 61.143 0.000 mydoku.py:11(checkLocation)
37205501 25.909 0.000 25.909 0.000 mydoku.py:15(<listcomp>)
12427551 6.574 0.000 19.684 0.000 mydoku.py:21(checkGrid)
12427551 13.110 0.000 13.110 0.000 mydoku.py:22(<listcomp>)
1 0.000 0.000 0.000 0.000 mydoku.py:4(printgrid)
12427550/1 74.904 0.000 155.731 155.731 mydoku.py:52(solveSudoku)
1 0.000 0.000 155.731 155.731 {built-in method builtins.exec}
94 0.000 0.000 0.000 0.000 {built-in method builtins.print}
2 0.000 0.000 0.000 0.000 {built-in method time.time}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
如果您查看 tottime 列，这是在 函数中花费的时间，不包括 sub-function 调用中的 时间，而 cumtime 是 包括 sub-function 调用的时间量。
请注意 solveSudoku 如何重新调用自身超过 1200 万次！在 triple-nested 循环中使用递归调用肯定是低效的。
solveSudoku函数本身大约占总时间的一半。它调用的函数将完成其余的工作。
其中，checkLocation 中的列表理解速度较慢。
对比一下，看geeksforgeeks代码的简介：
119318 function calls (114341 primitive calls) in 0.079 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.079 0.079 geeksforgeeks.py:1(<module>)
4979 0.013 0.000 0.013 0.000 geeksforgeeks.py:11(find_empty_location)
44384 0.023 0.000 0.023 0.000 geeksforgeeks.py:21(used_in_row)
13712 0.008 0.000 0.008 0.000 geeksforgeeks.py:28(used_in_col)
6687 0.010 0.000 0.010 0.000 geeksforgeeks.py:35(used_in_box)
2 0.000 0.000 0.000 0.000 geeksforgeeks.py:4(print_grid)
44384 0.014 0.000 0.055 0.000 geeksforgeeks.py:43(check_location_is_safe)
4979/2 0.011 0.000 0.079 0.040 geeksforgeeks.py:52(solve_sudoku)
1 0.000 0.000 0.000 0.000 geeksforgeeks.py:78(<listcomp>)
1 0.000 0.000 0.079 0.079 {built-in method builtins.exec}
183 0.000 0.000 0.000 0.000 {built-in method builtins.print}
4 0.000 0.000 0.000 0.000 {built-in method time.time}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
我没有详细查看算法，但很明显 geeksforgeeks 代码使用的函数调用少了几个数量级。
请注意，如果您需要更详细的信息，我建议您安装例如line-profiler。
顾名思义，它可以为每一行代码生成一个配置文件。
我将 checkLocation 修改为如下所示，它节省了大约 25% 的执行时间：
def checkLocation(grid, x, y, val):
if val in grid[x]:
# print("x"+str(grid[x]))
return False
for i in range(9):
if val == grid[i][y]:
return False
return True
具体这部分：
elif True in [val == grid[i][y] for i in range(9)]:
#print("y"+str(grid[:][y]))
return False
已替换为：
for i in range(9):
if val == grid[i][y]:
return False
原因是列表理解，每次都检查所有9个值，然后再进行一次比较。
替换循环遍历每个值并进行比较，一旦满足第一个 true 条件就返回 False（根据需要）。
在 GeekForGeeks 版本中，solveSudoku 函数只求解一个位置（使用 find_empty_location），它会选择它遇到的第一个零值位置，然后迭代以找到匹配的数字，其中每个交互递归调用 solve sudoku 函数。
在您的代码中，solveSudoku 求解所有位置，并且对 solveSudoku 的递归调用是在嵌套循环中进行的
for i in range(9):
for j in range(9):
if grid[i][j]!=0:
continue
else:
for k in range(1,10):
... solveSudoku(grid) ...
进行递归调用时，并不意味着忘记了当前调用，而是重新开始执行函数；控制最终会回来，这意味着它不必要地多次解决同一个位置。我希望这是有道理的。
这样重写，不到 3 秒就会 运行:
import time
def printgrid(grid):
for i in range(9):
for j in range(9):
print(grid[i][j], end=' ')
print("")
def checkLocation(grid, x, y, val):
if val in grid[x]:
# print("x"+str(grid[x]))
return False
elif True in [val == grid[i][y] for i in range(9)]:
# print("y"+str(grid[:][y]))
return False
return True
def checkGrid(grid):
if True in [0 in grid[i] for i in range(9)]:
#print("grid has empty spots")
return False
rowmap = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
colmap = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
squmap = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
for i in range(9):
for j in range(9):
if rowmap[grid[i][j]] == 0:
rowmap[grid[i][j]] = 1
else:
return False
if colmap[grid[j][i]] == 0:
colmap[grid[j][i]] = 1
else:
return False
rowmap = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
colmap = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
for i in [0, 3, 6]:
for j in [0, 3, 6]:
for tx in [0, 1, 2]:
for ty in [0, 1, 2]:
if squmap[grid[i+tx][j+ty]] == 0:
squmap[grid[i+tx][j+ty]] = 1
else:
return False
squmap = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
return True
def find_empty_location(arr, l):
for row in range(9):
for col in range(9):
if(arr[row][col] == 0):
l[0] = row
l[1] = col
return True
return False
def solveSudoku(grid):
if checkGrid(grid):
return True
else:
l = [0, 0]
if(not find_empty_location(grid, l)):
return True
i = l[0]
j = l[1]
for k in range(1, 10):
if checkLocation(grid, i, j, k):
grid[i][j] = k
if solveSudoku(grid):
return True
grid[i][j] = 0
return False
if __name__ == "__main__":
mydoku = [[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 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],
[0, 0, 0, 0, 8, 0, 0, 7, 9]]
codoku = [[5, 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]]
# print(checkLocation(mydoku, 1, 1, 2))
# print(checkGrid(codoku))
start = time.time()
print(solveSudoku(mydoku))
printgrid(mydoku)
diff = time.time() - start
print(diff)
我在 python 中编写了一个数独解法代码，紧跟 GeeksForGeeks 中给出的解法，但我的代码 运行 速度非常慢，尽管产生了正确的结果。
运行 用了 2 多分钟，而 GeeksForGeeks 代码用了不到一秒就解决了 2 个这样的数独：
我的代码：
import time
def printgrid(grid):
for i in range(9):
for j in range(9):
print(grid[i][j], end=' ')
print("")
def checkLocation(grid,x,y,val):
if val in grid[x]:
#print("x"+str(grid[x]))
return False
elif True in [val == grid[i][y] for i in range(9)]:
#print("y"+str(grid[:][y]))
return False
return True
def checkGrid(grid):
if True in [0 in grid[i] for i in range(9)]:
#print("grid has empty spots")
return False
rowmap = {1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
colmap = {1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
squmap = {1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
for i in range(9):
for j in range(9):
if rowmap[grid[i][j]] == 0:
rowmap[grid[i][j]] = 1
else:
return False
if colmap[grid[j][i]] == 0:
colmap[grid[j][i]] = 1
else:
return False
rowmap = {1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
colmap = {1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
for i in [0,3,6]:
for j in [0,3,6]:
for tx in [0,1,2]:
for ty in [0,1,2]:
if squmap[grid[i+tx][j+ty]] == 0:
squmap[grid[i+tx][j+ty]] = 1
else:
return False
squmap = {1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
return True
def solveSudoku(grid):
if checkGrid(grid):
return True
else:
for i in range(9):
for j in range(9):
if grid[i][j]!=0:
continue
else:
for k in range(1,10):
if checkLocation(grid,i,j,k):
#print("Tried "+str(k))
grid[i][j] = k
#print(grid)
if solveSudoku(grid):
return True
grid[i][j] = 0
return False
mydoku = [[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 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],
[0, 0, 0, 0, 8, 0, 0, 7, 9]]
codoku = [[5, 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]]
print(checkLocation(mydoku,1,1,2))
print(checkGrid(codoku))
#print(checkLocation(codoku,8,8,9))
#print(solveSudoku(codoku))
#printgrid(codoku)
#print(checkLocation(mydoku,0,3,6))
start = time.time()
print(solveSudoku(mydoku))
printgrid(mydoku)
diff = time.time() - start
print(diff)
输出：
True
True
5 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
135.41240525245667
GeeksForGeeks 代码：（删除评论）
import time
def print_grid(arr):
for i in range(9):
for j in range(9):
print(arr[i][j], end=' ')
print("")
def find_empty_location(arr, l):
for row in range(9):
for col in range(9):
if(arr[row][col]== 0):
l[0]= row
l[1]= col
return True
return False
def used_in_row(arr, row, num):
for i in range(9):
if(arr[row][i] == num):
return True
return False
def used_in_col(arr, col, num):
for i in range(9):
if(arr[i][col] == num):
return True
return False
def used_in_box(arr, row, col, num):
for i in range(3):
for j in range(3):
if(arr[i + row][j + col] == num):
return True
return False
def check_location_is_safe(arr, row, col, num):
return not used_in_row(arr, row, num) and not used_in_col(arr, col, num) and not used_in_box(arr, row - row % 3, col - col % 3, num)
def solve_sudoku(arr):
l =[0, 0]
if(not find_empty_location(arr, l)):
return True
row = l[0]
col = l[1]
for num in range(1, 10):
if(check_location_is_safe(arr,
row, col, num)):
arr[row][col]= num
if(solve_sudoku(arr)):
return True
arr[row][col] = 0
return False
if __name__=="__main__":
grid =[[0 for x in range(9)]for y in range(9)]
grid =[[3, 0, 6, 5, 0, 8, 4, 0, 0],
[5, 2, 0, 0, 0, 0, 0, 0, 0],
[0, 8, 7, 0, 0, 0, 0, 3, 1],
[0, 0, 3, 0, 1, 0, 0, 8, 0],
[9, 0, 0, 8, 6, 3, 0, 0, 5],
[0, 5, 0, 0, 9, 0, 6, 0, 0],
[1, 3, 0, 0, 0, 0, 2, 5, 0],
[0, 0, 0, 0, 0, 0, 0, 7, 4],
[0, 0, 5, 2, 0, 6, 3, 0, 0]]
start = time.time()
if(solve_sudoku(grid)):
print_grid(grid)
else:
print("No solution exists")
end = time.time()
print(end-start)
mydoku = [["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
for i in range(9):
for j in range(9):
if mydoku[i][j] == '.':
mydoku[i][j] = 0
else:
mydoku[i][j] = int(mydoku[i][j])
print("")
start = time.time()
if solve_sudoku(mydoku):
print_grid(mydoku)
else:
print("No Solution Exists")
end = time.time()
print(end-start)
输出：
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9
0.013003110885620117
5 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.05815267562866211
我的 code/coding 风格有什么问题导致我的代码花费了这么多时间？ 请帮忙
如果您想知道为什么您的代码运行缓慢，运行 它在分析器 下。例如 Python.
附带的cProfile
我已将您的代码保存为 mydoku.py，运行 以下命令：
python -m cProfile mydoku.py
这产生了以下输出：
True
True
5 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
155.7312035560608
186321197 function calls (173893648 primitive calls) in 155.731 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 155.731 155.731 mydoku.py:1(<module>)
111832944 35.234 0.000 61.143 0.000 mydoku.py:11(checkLocation)
37205501 25.909 0.000 25.909 0.000 mydoku.py:15(<listcomp>)
12427551 6.574 0.000 19.684 0.000 mydoku.py:21(checkGrid)
12427551 13.110 0.000 13.110 0.000 mydoku.py:22(<listcomp>)
1 0.000 0.000 0.000 0.000 mydoku.py:4(printgrid)
12427550/1 74.904 0.000 155.731 155.731 mydoku.py:52(solveSudoku)
1 0.000 0.000 155.731 155.731 {built-in method builtins.exec}
94 0.000 0.000 0.000 0.000 {built-in method builtins.print}
2 0.000 0.000 0.000 0.000 {built-in method time.time}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
如果您查看 tottime 列，这是在 函数中花费的时间，不包括 sub-function 调用中的 时间，而 cumtime 是 包括 sub-function 调用的时间量。
请注意 solveSudoku 如何重新调用自身超过 1200 万次！在 triple-nested 循环中使用递归调用肯定是低效的。
solveSudoku函数本身大约占总时间的一半。它调用的函数将完成其余的工作。
其中，checkLocation 中的列表理解速度较慢。
对比一下，看geeksforgeeks代码的简介：
119318 function calls (114341 primitive calls) in 0.079 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.079 0.079 geeksforgeeks.py:1(<module>)
4979 0.013 0.000 0.013 0.000 geeksforgeeks.py:11(find_empty_location)
44384 0.023 0.000 0.023 0.000 geeksforgeeks.py:21(used_in_row)
13712 0.008 0.000 0.008 0.000 geeksforgeeks.py:28(used_in_col)
6687 0.010 0.000 0.010 0.000 geeksforgeeks.py:35(used_in_box)
2 0.000 0.000 0.000 0.000 geeksforgeeks.py:4(print_grid)
44384 0.014 0.000 0.055 0.000 geeksforgeeks.py:43(check_location_is_safe)
4979/2 0.011 0.000 0.079 0.040 geeksforgeeks.py:52(solve_sudoku)
1 0.000 0.000 0.000 0.000 geeksforgeeks.py:78(<listcomp>)
1 0.000 0.000 0.079 0.079 {built-in method builtins.exec}
183 0.000 0.000 0.000 0.000 {built-in method builtins.print}
4 0.000 0.000 0.000 0.000 {built-in method time.time}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
我没有详细查看算法，但很明显 geeksforgeeks 代码使用的函数调用少了几个数量级。
请注意，如果您需要更详细的信息，我建议您安装例如line-profiler。
顾名思义，它可以为每一行代码生成一个配置文件。
我将 checkLocation 修改为如下所示，它节省了大约 25% 的执行时间：
def checkLocation(grid, x, y, val):
if val in grid[x]:
# print("x"+str(grid[x]))
return False
for i in range(9):
if val == grid[i][y]:
return False
return True
具体这部分：
elif True in [val == grid[i][y] for i in range(9)]:
#print("y"+str(grid[:][y]))
return False
已替换为：
for i in range(9):
if val == grid[i][y]:
return False
原因是列表理解，每次都检查所有9个值，然后再进行一次比较。
替换循环遍历每个值并进行比较，一旦满足第一个 true 条件就返回 False（根据需要）。
在 GeekForGeeks 版本中，solveSudoku 函数只求解一个位置（使用 find_empty_location），它会选择它遇到的第一个零值位置，然后迭代以找到匹配的数字，其中每个交互递归调用 solve sudoku 函数。
在您的代码中，solveSudoku 求解所有位置，并且对 solveSudoku 的递归调用是在嵌套循环中进行的
for i in range(9):
for j in range(9):
if grid[i][j]!=0:
continue
else:
for k in range(1,10):
... solveSudoku(grid) ...
进行递归调用时，并不意味着忘记了当前调用，而是重新开始执行函数；控制最终会回来，这意味着它不必要地多次解决同一个位置。我希望这是有道理的。
这样重写，不到 3 秒就会 运行:
import time
def printgrid(grid):
for i in range(9):
for j in range(9):
print(grid[i][j], end=' ')
print("")
def checkLocation(grid, x, y, val):
if val in grid[x]:
# print("x"+str(grid[x]))
return False
elif True in [val == grid[i][y] for i in range(9)]:
# print("y"+str(grid[:][y]))
return False
return True
def checkGrid(grid):
if True in [0 in grid[i] for i in range(9)]:
#print("grid has empty spots")
return False
rowmap = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
colmap = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
squmap = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
for i in range(9):
for j in range(9):
if rowmap[grid[i][j]] == 0:
rowmap[grid[i][j]] = 1
else:
return False
if colmap[grid[j][i]] == 0:
colmap[grid[j][i]] = 1
else:
return False
rowmap = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
colmap = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
for i in [0, 3, 6]:
for j in [0, 3, 6]:
for tx in [0, 1, 2]:
for ty in [0, 1, 2]:
if squmap[grid[i+tx][j+ty]] == 0:
squmap[grid[i+tx][j+ty]] = 1
else:
return False
squmap = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
return True
def find_empty_location(arr, l):
for row in range(9):
for col in range(9):
if(arr[row][col] == 0):
l[0] = row
l[1] = col
return True
return False
def solveSudoku(grid):
if checkGrid(grid):
return True
else:
l = [0, 0]
if(not find_empty_location(grid, l)):
return True
i = l[0]
j = l[1]
for k in range(1, 10):
if checkLocation(grid, i, j, k):
grid[i][j] = k
if solveSudoku(grid):
return True
grid[i][j] = 0
return False
if __name__ == "__main__":
mydoku = [[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 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],
[0, 0, 0, 0, 8, 0, 0, 7, 9]]
codoku = [[5, 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]]
# print(checkLocation(mydoku, 1, 1, 2))
# print(checkGrid(codoku))
start = time.time()
print(solveSudoku(mydoku))
printgrid(mydoku)
diff = time.time() - start
print(diff)