Csp

hashiwokakero (“build bridges”, nikoli) hands you a grid of numbered islands and asks you to join them with bridges until every number is spent. it is the friendliest possible introduction to constraint satisfaction: the constraints are few and visual, propagation alone solves most human-published puzzles, and when it doesn’t, you get to write a backtracking search. this page documents my solver at code/private/hashi/ — a go rewrite of a uni assignment originally in c — including the debugging session that writing this page forced on it. 𐃏

sudoku is the drosophila of constraint satisfaction: small enough to hold in your head, rich enough to demonstrate every solving paradigm that matters. this page works through four of them against my actual code — a backtracking solver with \(O(1)\) constraint sets (arcade/references/sudoku/solver.py), a dart port that also generates puzzles (arcade-mobile), an integer-programming formulation solved for real with scipy, and the exact-cover view that leads to knuth’s algorithm x. every timing below is a real run on this machine.

concurrency is structure: many logical tasks in flight, interleaved on however many cpus you have (possibly one). parallelism is hardware: tasks literally executing at the same instant. a single-core machine juggling 400 socket connections is concurrent, not parallel; a gpu multiplying matrices is parallel, barely concurrent. you design concurrency; you buy parallelism (Tanenbaum, Andrew S., 2008).

threads and shared memory#

a thread is an independent stream of execution inside one address space: own stack and registers, shared everything else. the sharing is the point — and the disease.