15 Lessons, including 4 Projects:
- sudoku game: due in 2017.4.20
- isolation game: due in 2017.5.15
- planning: due in 2017.6.12
- 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
Complete code implementation is https://github.com/jychstar/NanoDegreeProject/tree/master/AIND/sudoku
