2.1 Problem Space

• Incomplete cell is a set of candidates {1,2,…9}
• Singleton set {1} means the cell is "complete"
• In a 17-hint puzzle, 64 cells to complete
• Combinatorial explosion (though less than 9⁶⁴)
• Approach: iterative reduce possible sets

2.2 Prune

• For a given row, column, or box…
• If we find a singleton, remove from other cells

2.3 Fill

• For a given row, column, or box…
• If values only appear in one cell, remove other values from that cell

• {1,2,3} | {2,3,6} | {1,4,5,6}
• {1,2,3} | {2,3,6} | { 4,5 }

2.4 Extend

• The "search" part of the solver
• Pick a cell of smallest cardinality (> 1)
• Try next boards with each value as singleton

3.1 Python

while boards:
    board = boards.pop()    
    for f in (rows, cols, boxs):
        board = prune(f(board))
        board = f(fill(board))

    if complete(board): return show(board)
    if valid(board):            
        boards.extend(next_boards(board))

3.2 DFS

• DFS works way better than BFS
• Mostly becase it's not search-heavy

3.3 Functional Patterns

• rows, cols, boxs transform the board
• They are their own inverse ("involution")
• So prune and fill don't worry about board shape

for f in (rows, cols, boxs):
    board = prune(f(board))
    board = f(fill(board))

# a necessary unnecessary identify function
rows(rows(cols(cols(boxs(boxs(board)))))) == board

4.1 Elm

• Functional language, compiles to JavaScript
• Takes solver log in JSON, renders SVG

4.2 Demo