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() -- http://mail.python.org/mailman/listinfo/python-list