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
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
All three test cases passed for the naked twins and the diagonal sudoku.