# How to make this faster

Helmut Jarausch jarausch at igpm.rwth-aachen.de
Fri Jul 5 18:07:03 CEST 2013

```On Fri, 05 Jul 2013 16:38:43 +0100, Oscar Benjamin wrote:

> On 5 July 2013 16:17, Helmut Jarausch <jarausch at igpm.rwth-aachen.de> wrote:
>>
>> 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
>
> Sorry, I think what I meant was that you should have a structure
> called e.g. Remaining which is the set of all (r, c) pairs that you
> want to loop over here. Then there's no need to check on each
> iteration whether or not Grid[(r, c)] > 0. When I said "sparse" I
> meant that you don't need to set keys in Grid unless you actually have
> a value there so the test "Grid[(r, c)] > 0" would look like "(r, c)
> in Grid". Remaining is the set of all (r, c) pairs not in Grid that
> you update incrementally with .add() and .remove().
>
> Then this
>
>    for r,c in Grid :
>      if  Grid[(r,c)] > 0 : continue
>
> becomes
>
>     for r, c in Remaining:
>
>>     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))
>
> All_digits= set(range(1, 10))
>
> or
>
> All_digits = {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
>
> No it's not and you're not using it in your innermost loops anyway.
> Probably the loop I referred to isn't your bottleneck.
>

I've tried your suggestion, but unless I've misunderstood your suggestion it's a bit slower
than the solution above.

The solution above take 0.79 seconds (mean of 100 calls) while the following version
take 1.05 seconds (mean of 100 calls):

Grid = {(i,j):0 for i in range(9) for j in range(9)}
Remaining= {(i,j) for i in range(9) for j in range(9)}
Row_Digits = [set() for r in range(9)]
Col_Digits = [set() for c in range(9)]
Sqr_Digits = [set() for s in range(9)]

.... remove some pairs from Remaining for the initial set of the given Sudoku

def find_good_cell() :
Best= None
minPoss= 10
for r,c in Remaining :
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(range(1,10))

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
Remaining.remove((r,c))

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

```