solution.py

from collections import defaultdict
import itertools

def cross(A, B):
    return [s+t for s in A for t in B]


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.
    """
    # Don't waste memory appending actions that don't actually change any values
    if values[box] == value:
        return values

    values[box] = value
    if len(value) == 1:
        assignments.append(values.copy())
    return values


def naked_twins(values):
    """Eliminate values using the naked twins strategy.
    Args:
      # values(dict): a dictionary of the form {'box_name': '123456789', ...}

    Returns:
      # the values dictionary with the naked twins eliminated from peers.
    """

    # there are 29 units in sudoku: row_units(9), column units(9),
    # square_units(9), and diagonal unit(2)
    #
    # the constraints will be propagated into every 29 units with this for loop.
    for unit in unitlist:

        # first, we don't care the numbers with a length of 1 in every 9 boxes.
        # so we'll get started by taking all the values whose length are
        # not 1 in a box as the `unsolved` one.

        # this is intented for the sake of avoiding unnecessary computations for
        # the solved ones in 9 boxes in a later.
        unsolved = [box for box in unit if len(values[box]) != 1]

        # next, we should investigate which one has the naked twins in 9 boxes.
        # therefore, in every 9 units, all the values whose length is 2 could
        # be considered as a candidate for the naked twins.
        two_digit_boxes = [box for box in unit if len(values[box]) == 2]

        # But to be the naked twins between the boxes with two-length values,
        # their values must duplicated in boxes.
        #
        # To find out which boxes are duplicated, we're going to introduce a
        # dictionary here, its keys is going to be each numbers in a box and
        # its values is going to be a list with the name of boxes (ex. D4, E6)
        # that has every duplicated numbers.
        dups = defaultdict(list)
        for box in two_digit_boxes:
            digit = values[box]
            dups[digit].append(box)

        # if, as the value in a dictionary, the length of the list is greater
        # than 1, it means there are duplicated boxes at where that value is
        # therefore, we can take all the boxes which is greater than 1 in a list
        # into the naked twins.
        twin_boxes = list(itertools.chain(*[v for k, v in dups.items() if len(v) > 1]))

        # So far, we could find out what the unsolved boxes and the naked twin
        # boxes are.
        # Now, we invastigate 9 boxes in a unit again with these boxes.
        for box in unit:
            # we're going to choose only the unsolved boxes from 9 boxes, and
            # also exclude the naked twin boxes itself from 9 boxes.
            if box in unsolved and box not in twin_boxes:
                # take one box from twin boxes
                for twin in twin_boxes:
                    # take one digit from the twin box
                    for digit in values[twin]:
                        # then replace the value of the unsolved box with the
                        # value of the naked twin box
                        assign_value(values, box, values[box].replace(digit, ''))
    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):
    """Eliminate values from peers of each box with a single value.

    Go through all the boxes, and whenever there is a box with a single value,
    eliminate this value from the set of values of all its peers.

    Args:
        values: Sudoku in dictionary form.
    Returns:
        Resulting Sudoku in dictionary form after eliminating values.
    """
    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]:
            assign_value(values, peer, values[peer].replace(digit,''))
    return values


def only_choice(values):
    """Finalize all values that are the only choice for a unit.

    Go through all the units, and whenever there is a unit with a value
    that only fits in one box, assign the value to this box.

    Input: Sudoku in dictionary form.
    Output: Resulting Sudoku in dictionary form after filling in only choices.
    """
    for unit in unitlist:
        for digit in '123456789':
            dplaces = [box for box in unit if digit in values[box]]
            if len(dplaces) == 1:
                assign_value(values, dplaces[0], digit)
    return values


def reduce_puzzle(values):
    """
    Iterate eliminate() and only_choice(). If at some point, there is a box with no available values, return False.
    If the sudoku is solved, return the sudoku.
    If after an iteration of both functions, the sudoku remains the same, return the sudoku.
    Input: A sudoku in dictionary form.
    Output: The resulting sudoku in dictionary form.
    """
    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])
        # Use the Eliminate Strategy
        values = eliminate(values)
        # Use the Only Choice Strategy
        values = only_choice(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):
    "Using depth-first search and propagation, try all possible 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.
    """
    # grid_values() function returns a dictionary representation of the sudoku
    # grid. then invoke search() function for the dictionary.
    values = search(grid_values(grid))
    return values


assignments = []
rows = 'ABCDEFGHI'
cols = '123456789'

diagonal_unit_1 = [rows[x] + cols[x] for x in range(len(rows))]
diagonal_unit_2 = [rows[::-1][x] + cols[x] for x in range(len(rows))]

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')]
unitlist = row_units + column_units + square_units + [diagonal_unit_1] + [diagonal_unit_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)


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.')