How to make this faster
Helmut Jarausch
jarausch at igpm.rwth-aachen.de
Fri Jul 5 04:22:51 EDT 2013
Hi,
I have coded a simple algorithm to solve a Sudoku (probably not the first one).
Unfortunately, it takes 13 seconds for a difficult problem which is more than 75 times slower
than the same algorithm coded in C++.
Is this to be expected or could I have made my Python version faster *** without *** sacrificing readability.
Profiling shows that the function find_good_cell is called (only) 45267 times and this take 12.9 seconds
CPU time (on a 3.2 GHz machine)
For your pleasure I include the full code below.
Many thanks for a hint,
Helmut
#!/usr/bin/python3
import numpy as np
Grid= np.zeros((9,9),dtype=int)
Row_Digits = np.asarray(np.zeros((9,10)),dtype=bool)
Col_Digits = np.asarray(np.zeros((9,10)),dtype=bool)
Sqr_Digits = np.asarray(np.zeros((9,10)),dtype=bool)
def Read_Sudoku(Input) :
r= -1
R_Cells= 81
for line in Input :
line= line.strip()
if len(line) == 0 or line[0] == '#' : continue
r+= 1
for (c,ch) in enumerate(line) :
if ch == '_' : continue
if not ch in "123456789_" :
raise ValueError("invalid character {0} in input line {1}".format(c,line))
Sq_No= (r//3)*3+c//3
d= int(ch)
Grid[r,c]= d
Row_Digits[r,d]= True
Col_Digits[c,d]= True
Sqr_Digits[Sq_No,d]= True
R_Cells-= 1
return R_Cells
def Print_Grid() :
Sep = "+---+---+---#---+---+---#---+---+---+"
SepK= "#####################################"
print(Sep)
for r in range(9) :
print('|',end='')
for c in range(9) :
d= Grid[r,c]
print(" {0} {1}".format( str(d) if d>0 else ' ',
'#' if (c+1)%3==0 and c>0 and c<8 else '|' ), end='')
print("\n{}".format(SepK if (r+1)%3==0 and r>0 and r<8 else Sep))
def find_good_cell() :
Best= None
minPoss= 10
for r in range(9) :
for c in range(9) :
if Grid[r,c] > 0 : continue
Sq_No= (r//3)*3+c//3
Possibilities= 0
for d in range(1,10) :
if Row_Digits[r,d] or Col_Digits[c,d] or Sqr_Digits[Sq_No,d] : continue
Possibilities+= 1
if ( Possibilities < minPoss ) :
minPoss= Possibilities
Best= (r,c)
if minPoss == 0 : Best=(-1,-1)
return Best
def Solve(R_Cells) :
if R_Cells == 0 :
print("\n\n++++++++++ S o l u t i o n ++++++++++\n")
Print_Grid()
return True
r,c= find_good_cell()
if r < 0 : return False
Sq_No= (r//3)*3+c//3
for d in range(1,10) :
if Row_Digits[r,d] or Col_Digits[c,d] or Sqr_Digits[Sq_No,d] : continue
# put d into Grid
Grid[r,c]= d
Row_Digits[r,d]= True
Col_Digits[c,d]= True
Sqr_Digits[Sq_No,d]= True
Success= Solve(R_Cells-1)
# remove d again
Grid[r,c]= 0
Row_Digits[r,d]= False
Col_Digits[c,d]= False
Sqr_Digits[Sq_No,d]= False
if Success :
Zuege.append((d,r,c))
return True
return False
from io import StringIO
Problem='''
_________
_____3_85
__1_2____
___5_7___
__4___1__
_9_______
5______73
__2_1____
____4___9
'''
Input= StringIO(Problem)
from time import process_time
R_Cells= Read_Sudoku(Input)
Print_Grid()
Zuege=[]
Start= process_time()
# import cProfile
# cProfile.run("Success = Solve(R_Cells)")
Success = Solve(R_Cells)
Stop= process_time()
print("after {} seconds:".format(Stop-Start))
if Success :
print("\nZuege:")
n=0
for Z in reversed(Zuege) :
print("{0} -> ({1},{2})\t".format(Z[0],Z[1]+1,Z[2]+1),end='')
n+= 1
if n%5 == 0 :
print()
print()
More information about the Python-list
mailing list