How to make this faster

From	Helmut Jarausch <jarausch@igpm.rwth-aachen.de>
Newsgroups	comp.lang.python
Subject	How to make this faster
Date	2013-07-05 08:22 +0000
Message-ID	<b3ne2rFojnkU1@mid.dfncis.de> (permalink)

Show all headers | View raw

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

Back to comp.lang.python | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 08:22 +0000
  Re: How to make this faster Fábio Santos <fabiosantosart@gmail.com> - 2013-07-05 10:38 +0100
  Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 10:07 +0000
  Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 11:13 +0100
  Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 10:53 +0000
    Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-05 12:02 +0000
    Re: How to make this faster Fábio Santos <fabiosantosart@gmail.com> - 2013-07-05 13:44 +0100
    Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 14:41 +0100
    Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 14:28 +0000
      Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 15:45 +0100
    Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 14:48 +0000
      Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 16:26 +0100
    Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 14:54 +0000
      Re: How to make this faster Fábio Santos <fabiosantosart@gmail.com> - 2013-07-05 16:18 +0100
      Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-05 16:24 +0000
    Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 15:17 +0000
      Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 16:38 +0100
      Re: How to make this faster MRAB <python@mrabarnett.plus.com> - 2013-07-05 17:25 +0100
      Re: How to make this faster Joshua Landau <joshua.landau.ws@gmail.com> - 2013-07-06 02:45 +0100
    Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 15:47 +0000
      Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-05 16:52 +0000
    Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 16:07 +0000
      Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-05 16:50 +0000
        Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 18:39 +0000
          Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-06 03:05 +0000
          Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-06 07:25 +0000
    Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 18:42 +0000

csiph-web