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

1.2 The Board

board.png

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

row.png

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
  • Takes solver log in JSON, renders SVG

4.2 Demo