UD889_prv_Ls3_SudokuAI_7_Constraint_Propagation.py

# Wayne H Nixalo - 2017-Jun-16 01:33
# UD889 - Udacity AIND prv
# Lesson 3: Solving a Sudoku with AI
# 7: Constraint Propagation
################################################################################
# Now that you see how we apply Constraint Propagation to this problem, let's
# try to code it! In the following quiz, combine the functions eliminate and
# only_choice to write the function reduce_puzzle, which receives as input an
# unsolved puzzle and applies our two constraints repeatedly in an attempt to
# solve it.

from utils import *

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])

        # Your code here: Use the Eliminate Strategy
        values = eliminate(values)

        # Your code here: 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

# #################
# # OUTUT:
# Looks good!
# 4 8 3 |9 2 1 |6 5 7
# 9 6 7 |3 4 5 |8 2 1
# 2 5 1 |8 7 6 |4 9 3
# ------+------+------
# 5 4 8 |1 3 2 |9 7 6
# 7 2 9 |5 6 4 |1 3 8
# 1 3 6 |7 9 8 |2 4 5
# ------+------+------
# 3 7 2 |6 8 9 |5 1 4
# 8 1 4 |2 5 3 |7 6 9
# 6 9 5 |4 1 7 |3 8 2
# ################## ################## ################## #################

# however for:
grid2 = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
values2 = grid_values(grid2)

# reduce_puzzle(values2) won't solve the puzzle. It'll only reduce to a set of
# possibilities. Need to go further.


################################################################################
# utils.py
################################################################################
rows = 'ABCDEFGHI'
cols = '123456789'

def cross(a, 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')]
unitlist = row_units + column_units + square_units
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 display(values):
    """
    Display the values as a 2-D grid.
    Input: The sudoku in dictionary form
    Output: None
    """
    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 grid_values(grid):
    """
    Convert grid into a dict of {square: char} with '123456789' for empties.
    Input: A grid in string form.
    Output: 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 eliminate(values):
    """
    Go through all the boxes, and whenever there is a box with a value, eliminate this value from the values of all its peers.
    Input: A sudoku in dictionary form.
    Output: The resulting sudoku in dictionary form.
    """
    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):
    """
    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: A sudoku in dictionary form.
    Output: The resulting sudoku in dictionary form.
    """
    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