How to make this faster

[Helmut Jarausch]

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
>>     Row_Digits[r].add(d)
>>     Col_Digits[c].add(d)
>>     Sqr_Digits[Sq_No].add(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))
    Row_Digits[r].add(d)
    Col_Digits[c].add(d)
    Sqr_Digits[Sq_No].add(d)
    
    Success= Solve(R_Cells-1)

    # remove d again
    Grid[(r,c)]= 0
    Remaining.add((r,c))
    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