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() -- http://mail.python.org/mailman/listinfo/python-list