# How to make this faster

Helmut Jarausch jarausch at igpm.rwth-aachen.de
Fri Jul 5 17:17:08 CEST 2013

```On Fri, 05 Jul 2013 15:45:25 +0100, Oscar Benjamin wrote:

> Presumably then you're now down to the innermost loop as a bottle-neck:
>
>       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 you make it so that e.g. Row_Digits[r] is a set of indices rather
> than a list of bools then you can do this with something like
>
>     Possibilities = len(Row_Digits[r] | Col_Digits[c] | Sqr_Digits[Sq_No])
>
> or perhaps
>
>     Possibilities = len(set.union(Row_Digits[r], Col_Digits[c],
> Sqr_Digits[Sq_No]))
>
> which I would expect to be a little faster than looping over range
> since the loop is then performed under the hood by the builtin
> set-type.
>
> It just takes practice.

indeed

> It's a little less obvious in Python than in
> low-level languages where the bottlenecks will be and which operations
> are faster/slower but optimisation always involves a certain amount of
> trial and error anyway.
>
>
> Oscar

I've tried the following version

def find_good_cell() :
Best= None
minPoss= 10
for r,c in Grid :
if  Grid[(r,c)] > 0 : continue
Sq_No= (r//3)*3+c//3
Possibilities= 9-len(Row_Digits[r] | Col_Digits[c] | Sqr_Digits[Sq_No])
if ( Possibilities < minPoss ) :
minPoss= Possibilities
Best= (r,c)

if minPoss == 0 : Best=(-1,-1)
return Best

All_digits= set((1,2,3,4,5,6,7,8,9))

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 All_digits - (Row_Digits[r] | Col_Digits[c] | Sqr_Digits[Sq_No]) :
# put d into Grid
Grid[(r,c)]= d

Success= Solve(R_Cells-1)

# remove d again
Grid[(r,c)]= 0
Row_Digits[r].remove(d)
Col_Digits[c].remove(d)
Sqr_Digits[Sq_No].remove(d)

if Success :
Zuege.append((d,r,c))
return True

return False

which turns out to be as fast as the previous "dictionary only version".
Probably,  set.remove is a bit slow

Thanks,
Helmut

```