Path: csiph.com!usenet.pasdenom.info!gegeweb.org!de-l.enfer-du-nord.net!feeder2.enfer-du-nord.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Date: Fri, 05 Jul 2013 17:25:54 +0100
From: MRAB <python@mrabarnett.plus.com>
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:17.0) Gecko/20130620 Thunderbird/17.0.7
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: How to make this faster
References: <b3ne2rFojnkU1@mid.dfncis.de> <b3nmtfFojnkU3@mid.dfncis.de> < b3o3gkFtc39U1@mid.dfncis.de> <mailman.4299.1373035554.3114.python-list@ python.org> <b3o6bkFtc39U4@mid.dfncis.de>
In-Reply-To: <b3o6bkFtc39U4@mid.dfncis.de>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: list
Reply-To: python-list@python.org
Newsgroups: comp.lang.python
Message-ID: <mailman.4303.1373041542.3114.python-list@python.org>
Lines: 204
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:50000

On 05/07/2013 16:17, Helmut Jarausch wrote:
> 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
>      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
>
For comparison, here's my solution:

from collections import Counter

problem = '''
_________
_____3_85
__1_2____
___5_7___
__4___1__
_9_______
5______73
__2_1____
____4___9
'''

# Build the grid.
digits = "123456789"

grid = []

for row in problem.splitlines():
   if not row:
     continue

   new_row = []

   for cell in row:
     if cell.isdigit():
       new_row.append({cell})
     else:
       new_row.append(set(digits))

   grid.append(new_row)

# Solve the grid.
changed = True
while changed:
   changed = False

   # Look for cells that contain only one digit.
   for r in range(9):
     for c in range(9):
       if len(grid[r][c]) == 1:
         digit = list(grid[r][c])[0]

         # Remove from other cells in same row.
         for c2 in range(9):
           if c2 != c and digit in grid[r][c2]:
             grid[r][c2].remove(digit)
             changed = True

         # Remove from other cells in same column.
         for r2 in range(9):
           if r2 != r and digit in grid[r2][c]:
             grid[r2][c].remove(digit)
             changed = True

         # Remove from other cells in the same block of 9.
         start_row = r - r % 3
         start_column = c - c % 3
         for r2 in range(start_row, start_row + 3):
           for c2 in range(start_column, start_column + 3):
             if (r2, c2) != (r, c) and digit in grid[r2][c2]:
               grid[r2][c2].remove(digit)
               changed = True

   # Look for digits that occur in only one cell in a row.
   for r in range(9):
     counts = Counter()
     for c in range(9):
       counts += Counter(grid[r][c])

     unique = {digit for digit, times in counts.items() if times == 1}

     for c in range(9):
       if len(grid[r][c]) > 1 and len(grid[r][c] & unique) == 1:
         grid[r][c] &= unique
         changed = True

   # Look for digits that occur in only one cell in a column.
   for c in range(9):
     counts = Counter()
     for r in range(9):
       counts += Counter(grid[r][c])

     unique = {digit for digit, times in counts.items() if times == 1}

     for r in range(9):
       if len(grid[r][c]) > 1 and len(grid[r][c] & unique) == 1:
         grid[r][c] &= unique
         changed = True

   # Look for digits that occur in only one cell in a block of 9.
   for start_row in range(0, 9, 3):
     for start_column in range(0, 9, 3):
       counts = Counter()
       for r in range(start_row, start_row + 3):
         for c in range(start_column, start_column + 3):
           counts += Counter(grid[r][c])

       unique = {digit for digit, times in counts.items() if times == 1}

       for r in range(start_row, start_row + 3):
         for c in range(start_column, start_column + 3):
           if len(grid[r][c]) > 1 and len(grid[r][c] & unique) == 1:
             grid[r][c] &= unique
             changed = True

# Display the solution.
for row in grid:
   for cell in row:
     print("".join(sorted(cell)), end=" ")

   print()