srikantrao / sudoku_solver

Artificial Intelligence Nanodegree

Introductory Project: Diagonal Sudoku Solver

Question 1 (Naked Twins)

Q: How do we use constraint propagation to solve the naked twins problem?
A: The problem can be broken down into identification of naked twins in a (row, column, square or diagonal) unit, followed by the enforcing the constraint on the values of the other elements in the unit.

Identification of Naked twins -

# Find all instances of naked twins
    for unit in unitlist:
        two_places = [box for box in unit if len(values[box]) == 2]
        # Cut short if there are less than two elements with only 2 values
        if(len(two_places) < 2):
            continue
            for elem in two_places:
                naked_twin = [twin for twin in two_places if values[twin] == values[elem]]
                if(len(naked_twin) == 2): # you have found naked twins

Application of Constraints imposed by the values of the naked twins

# Eliminate the naked twins as possibilities for their peers
                    # Remove the values from other cells in the unit
                    for box in unit:
                        # Do not edit the digits of the naked twins
                        if(box == naked_twin[1] or box == naked_twin[0]):
                            continue
                        # Use assign_values to update values
                        for digit in values[naked_twin[0]]:
                            new_value = values[box].replace(digit, '')
                            assign_value(values, box, new_value)
    return values

Question 2 (Diagonal Sudoku)

Q: How do we use constraint propagation to solve the diagonal sudoku problem?
A: The constraints have been applied in the form of units (row, column, square). To add diagonal constraints, the diagonal units need to be added to the unit list and these will alter the peers for the corresponding diagonal elements.

These additional constraints can be addded by adding the two diagonal units to the unit list as shown below -

# Create a list of the two diagonal units
diagonal_units = [[rows[i]+cols[i] for i in range(9)]]
diagonal_units.append([rows[i]+cols[8-i] for i in range(9)])

These are then added to the rest of the units -

# Create the unit list
unitlist = row_units + col_units + square_units + diagonal_units

Final Result

All three test cases passed for the naked twins and the diagonal sudoku.