On Fri, 05 Jul 2013 16:38:43 +0100, Oscar Benjamin wrote:
> 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.
>
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
--
http://mail.python.org/mailman/listinfo/python-list
