On 5 July 2013 16:17, Helmut Jarausch <jarau...@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.
Oscar
--
http://mail.python.org/mailman/listinfo/python-list
