## 1 Sudoku

### 1.1 The Game

• 9x9 board (81 cells)
• At least 17 cells populated to start (usually more)
• Fill each row, column, box with 1-9 (no dups!)

## 2 SOlver

### 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 964)
• 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 Implementation

### 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 Visualization

### 4.1 Elm

• Functional language, compiles to JavaScript