How to make this faster
Helmut Jarausch
jarausch at igpm.rwth-aachen.de
Fri Jul 5 20:42:56 CEST 2013
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()
More information about the Python-list
mailing list