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.
𐃏
Constraint Satisfaction Problems
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.
Backlinks (4)
1. Hashiwokakero (Bridges) Solver /wiki/ai/csp/hashiwokakero/
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.
𐃏
2. Sudoku /wiki/ai/csp/sudoku/
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.
3. Wiki /wiki/
Knowledge is a paradox. The more one understand, the more one realises the vastness of his ignorance.