How to make this faster

[Helmut Jarausch]

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()