I made a sudoku solving code in python, closely following the solution given on GeeksForGeeks, but my code runs really slowly, albeit producing correct results.
It took over 2 minutes to run, whereas the GeeksForGeeks code took under a second to solve 2 such Sudokus:
My Code:
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)
Output:
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 Code: (comments removed)
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)
Output:
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
What is wrong with my code/coding style that my code takes so much more time? Please help
CodePudding user response：
If you want to know why your code is slow, run it under a profiler. For example cProfile that comes with Python.
I have saved your code as mydoku.py, and ran the following command:
python -m cProfile mydoku.py
This produced the following output:
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}
If you look at the tottime column, this is the amount of time spent in a function excluding time in sub-function calls, while cumtime is the amount of time including sub-function calls.
The solveSudoku function itself takes about half of the total time. The functions that it calls take the rest.
Among those, the list comprehension in checkLocation is slow.
In contrast, look at the profile of the geeksforgeeks code:
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}
I haven't looked at the algorithms in detail, but it is clear that the geeksforgeeks code uses several orders of magnitude less function calls.
Note that if you want more detailed information, I would suggest installing e.g. line-profiler.
As the name suggests, it can generate a profile for every line of code.
CodePudding user response：
I modified checkLocation to look like this and it saved about 25% execution time:
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
Specifically this portion:
elif True in [val == grid[i][y] for i in range(9)]:
#print("y" str(grid[:][y]))
return False
has been replaced with:
for i in range(9):
if val == grid[i][y]:
return False
The reason is that with the list comprehension, all 9 values are being checked every time, followed by another comparison.
The replacement loops through each value and does the comparison, returning False (as desired) as soon as the first true condition is met.