solution.py

assignments = []
rows = 'ABCDEFGHI'
cols = '123456789'
cols_rev = cols[::-1]

def cross(a,b):
    # Cross product of elements in A and elements in B.
    return [s+t for s in a for t in b]

boxes = cross(rows, cols)
row_units = [cross(r, cols) for r in rows]
column_units = [cross(rows, c) for c in cols]
square_units = [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')]

# Create two diagonal units:
diagonal_1 = [[rows[i]+cols[i] for i in range(len(rows))]]
diagonal_2 = [[rows[i]+cols_rev[i] for i in range(len(rows))]]

# Add the diagonal units to unitlist
unitlist = row_units + column_units + square_units + diagonal_1 + diagonal_2

units = dict((s, [u for u in unitlist if s in u]) for s in boxes)
peers = dict((s, set(sum(units[s],[]))-set([s])) for s in boxes)

def assign_value(values, box, value):
    """
    Please use this function to update your values dictionary!
    Assigns a value to a given box. If it updates the board record it.
    """
    values[box] = value
    if len(value) == 1:
        assignments.append(values.copy())
    return values

def get_duplicates(ary):
    """
    Args:
        ary(array): an array of integers or strings.

    Returns:
        duplicate items in the list.
    """
    dups = []
    for i, v1 in enumerate(ary):
        for j, v2 in enumerate(ary):
            if i != j and v1 == v2 and v1 not in dups:
                dups.append(v1)
    return dups

def is_subset(s1, s2):
    """
    Args:
        s1(string)
        s2(string)

    Returns:
        True if any element from the first string is
        present in the second, False otherwise.
    """
    a1 = [c for c in s1]
    a2 = [c for c in s2]
    return any(n in a1 for n in a2)

def naked_twins(values):
    """
    Strategy #3:
        Go through all the units, and if there is a unit
        that contains twins of length 2, eliminate those two
        digits from the box's peers.
    Args:
        values(dict): The sudoku in dictionary form
    
    Returns:
        The modified sudoku dictionary, with the naked twins eliminated from peers.
    """
    for pos, current_units in units.items():
        for unit in current_units:
            # Get all values for current unit
            possible_boxes = [values[box] for box in unit]
            # Get all values with length 2
            len_2 = [box for box in possible_boxes if len(box) == 2]
            # Get all twin values
            twins = get_duplicates(len_2)
            # If there are twin values, remove them from unit
            # unless the box contains exactly those values.
            for twin in twins:
                for box in unit:
                    v = values[box]
                    if len(v) > 1 and twin != v and is_subset(twin, v):
                        stripped_list = [n for n in sorted(v) if n not in sorted(twin)]
                        stripped_val = ''.join(stripped_list)
                        assign_value(values, box, stripped_val)
    return values


def grid_values(grid):
    """
    Convert grid into a dict of {square: char} with '123456789' for empties.
    Args:
        grid(string) - A grid in string form.
    Returns:
        A grid in dictionary form
            Keys: The boxes, e.g., 'A1'
            Values: The value in each box, e.g., '8'. If the box has no value, then the value will be '123456789'.
    """
    chars = []
    digits = '123456789'
    for c in grid:
        if c in digits:
            chars.append(c)
        if c == '.':
            chars.append(digits)
    assert len(chars) == 81
    return dict(zip(boxes, chars))

def display(values):
    """
    Display the values as a 2-D grid.
    Args:
        values(dict): The sudoku in dictionary form
    """
    width = 1+max(len(values[s]) for s in boxes)
    line = '+'.join(['-'*(width*3)]*3)
    for r in rows:
        print(''.join(values[r+c].center(width)+('|' if c in '36' else '')
                      for c in cols))
        if r in 'CF': print(line)
    return

def eliminate(values):
    """
    Strategy #1:
        Iterate over all the boxes in the puzzle that only
        have one value assigned to them, and remove this
        value from every one of its peers.
    Args:
        values(dict): The sudoku in dictionary form
    
    Returns:
        The modified sudoku dictionary.
    """
    solved_values = [box for box in values.keys() if len(values[box]) == 1]
    for box in solved_values:
        digit = values[box]
        for peer in peers[box]:
            values[peer] = values[peer].replace(digit,'')
    return values

def only_choice(values):
    """
    Strategy #2:
        Go through all the units, and if there is a unit
        with a digit that only fits in one possible box,
        assign that digit to that box.
    Args:
        values(dict): The sudoku in dictionary form
    
    Returns:
        The modified sudoku dictionary.
    """
    for unit in unitlist:
        for digit in '123456789':
            dplaces = [box for box in unit if digit in values[box]]
            if len(dplaces) == 1:
                values[dplaces[0]] = digit
    return values

def reduce_puzzle(values):
    stalled = False
    while not stalled:
        # Check how many boxes have a determined value
        solved_values_before = len([box for box in values.keys() if len(values[box]) == 1])

        # Eliminate Strategy
        values = eliminate(values)

        # Only Choice Strategy
        values = only_choice(values)

        # Naked Twins Strategy
        values = naked_twins(values)

        # Check how many boxes have a determined value, to compare
        solved_values_after = len([box for box in values.keys() if len(values[box]) == 1])
        # If no new values were added, stop the loop.
        stalled = solved_values_before == solved_values_after
        # Sanity check, return False if there is a box with zero available values:
        if len([box for box in values.keys() if len(values[box]) == 0]):
            return False
    return values

def search(values):
    # First, reduce the puzzle using the previous function
    values = reduce_puzzle(values)
    if values is False:
        return False ## Failed earlier
    if all(len(values[s]) == 1 for s in boxes): 
        return values ## Solved!
    # Choose one of the unfilled squares with the fewest possibilities
    n,s = min((len(values[s]), s) for s in boxes if len(values[s]) > 1)
    # Now use recurrence to solve each one of the resulting sudokus, and 
    for value in values[s]:
        new_sudoku = values.copy()
        new_sudoku[s] = value
        attempt = search(new_sudoku)
        if attempt:
            return attempt

def solve(grid):
    """
    Find the solution to a Sudoku grid.
    Args:
        grid(string): a string representing a sudoku grid.
            Example: '2.............62....1....7...6..8...3...9...7...6..4...4....8....52.............3'
    Returns:
        The dictionary representation of the final sudoku grid. False if no solution exists.
    """
    return search(grid_values(grid))
    

if __name__ == '__main__':
    diag_sudoku_grid = '2.............62....1....7...6..8...3...9...7...6..4...4....8....52.............3'
    display(solve(diag_sudoku_grid))

    try:
        from visualize import visualize_assignments
        visualize_assignments(assignments)

    except SystemExit:
        pass
    except:
        print('We could not visualize your board due to a pygame issue. Not a problem! It is not a requirement.')
#grid = '1.4.9..68956.18.34..84.695151.....868..6...1264..8..97781923645495.6.823.6.854179'
#display(reduce_puzzle(grid_values(grid)))
#display(solve(grid))