A Clash Course in Solving Sudoku (Functional Pearl)
summary
Builds an FPGA Sudoku solver by compiling Haskell with Clash Haskell-to-FPGA from a Bird 2006 functional pearl, translating a backtracking solver into fixed-size vectors, bit-vector masks for pruning, and a RAM-backed stack for backtracking. Most standard 9×9 puzzles finish in <100 cycles in cycle-accurate simulation; hard cases take thousands. Synthesized on an Artix‑7 at 200 MHz uses ~9,000 logic cells for 3×3 (25,000 for 3×4), communicates at 9,600 bps, and successfully runs on real hardware.
AI-written summary · about
chapters (19)
- 0:00Clash and Sudoku solver intro
- 1:45What is Clash in hardware design
- 3:34Clash fundamentals
- 7:03Sudoku solver approach
- 9:11Software to hardware translation
- 11:00Sudoku solver pruning
- 14:13Constraint structure and folding
- 17:52Branching in hardware
- 20:00Recursion with stack and RAM
- 22:08IO and serial setup
- 23:52Parser, solver, formatter
- 25:16Solver performance and testing
- 26:41Hardware implementation
- 28:09Parallel solvers and scaling
- 29:12Clash benefits for hardware
- 32:27Clash vs Haskell for hardware
- 34:35Getting started with Clash
- 35:18Power draw and racing
- 36:27Clash adoption barriers
related talks
03mVisions of the future (Clash 1.0)
09mOuvroir de Code Potentiel
38mSolving Problems with Automata
20mOn the paradigm of functional programming
28mScimitar: Functional Programs as Optimization Problems
49mRefactoring toward a more functional style in F#
40mSuperfusion: Eliminating Intermediate Data Structures via Inductive Synthesis
49mCode Jugalbandi