Monday, April 24, 2017

Artificial intelligence ND A1, sudoku

15 Lessons, including 4 Projects:
  1. sudoku game: due in 2017.4.20
  2. isolation game: due in 2017.5.15
  3. planning: due in 2017.6.12
  4. hidden markov models: due in 2017.7.10
time commitment: 15 hours/week * 13 weeks
setup
source activate py3
pip install git+https://github.com/hmmlearn/hmmlearn.git
//Successfully installed hmmlearn-0.2.1
brew install sdl sdl_image sdl_mixer sdl_ttf portmidi mercurial
pip install pygame

3 project 1: Sudoku

This is a warm-up project. The major purpose is to get you familiar with the list/dictionary comprehension and depth-first search.
rows = 'ABCDEFGHI'
cols = '123456789'
def cross(a, b):
    return [s+t for s in a for t in b]
boxes = cross(rows, cols) # 81
row_units = [cross(r, cols) for r in rows]  # 9*9
column_units = [cross(rows, c) for c in cols]  # 9*9
square_units = [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')]
unitlist = row_units + column_units + square_units  # 27*9
units = {s: [u for u in unitlist if s in u] for s in boxes} # 81 keys*9
peers = {s: set(sum(units[s],[]))-set([s]) for s in boxes}  # 81 keys*20

diag_units = [["A1","B2","C3","D4","E5","F6","G7","H8","I9"],
          ["A9","B8","C7","D6","E5","F4","G3","H2","I1"]]
unitlist = row_units + column_units + square_units + diag_units # 29*9
units = {s: [u for u in unitlist if s in u] for s in boxes} # 81 keys*10
peers = {s: set(sum(units[s],[]))-set([s]) for s in boxes}  # 81 keys*20
def search(values):
    # Using depth-first search and propagation
    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 
    for value in values[s]:
        new_sudoku = values.copy()
        new_sudoku[s] = value
        attempt = search(new_sudoku)
        if attempt:
            return attempt
def reduce_puzzle(values):
    while True:
        solved_values_before = len([box for box in values.keys() if len(values[box]) == 1])
        values = eliminate(values)
        values = only_choice(values)
        values = naked_twins(values)
        solved_values_after = len([box for box in values.keys() if len(values[box]) == 1])
        if solved_values_before == solved_values_after:
            break
        # 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 eliminate(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]:
            values[peer]= values[peer].replace(digit,"")
    return values
def only_choice(values):
    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 naked_twins(values):
    for unit in unitlist:
        size2 = [box for box in unit if len(values[box])==2]
        dic = {}
        for box in size2:
            target = values[box]
            if len(target) == 1: continue # avoid changed target
            if target not in dic:
                dic[target] = box
            else:
                for each in unit:
                    digit = values[each]
                    if len(digit) > 1 and digit != target:
                        values[each]= digit.replace(target[0],"")
                        values[each]= values[each].replace(target[1],"")
    return values

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.