How to make this faster

[Helmut Jarausch]

On Fri, 05 Jul 2013 17:25:54 +0100, MRAB wrote:


> For comparison, here's my solution:

Your solution is very fast, indeed.
It takes 0.04 seconds (mean of 1000 runs) restoring "grid"
in between.
But that's a different algorithm which is IMHO more difficult to understand.
Many thanks,
Helmut

> 
> 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()