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

- 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
^{64}) - Approach: iterative reduce possible sets

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

- 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 }

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

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

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

- 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
```

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