Try to not to use Machine Learning —Rule #1 in Google’s Machine Learning Handbook
Backtracking
bananagrams hands you a fistful of letter tiles and one instruction: arrange all of them into a connected crossword before anyone else does.
𐃏
this page documents the real solver living in this repo at static/code/bananagrams/ — a haskell heuristic search in haskell-imp/ plus a playable js incarnation served at /code/bananagrams/ on this site — rather than a from-scratch design; a compact python reference solver (trie + backtracking) is developed at the end to make the algorithmic skeleton explicit.
constraint programming inverts the usual deal: you state what a solution must satisfy, and a general-purpose solver figures out how to find one. 𐃏 no objective gradient, no simplex tableau — just variables, finite domains, and constraints, attacked by an alternation of inference (prune values that cannot appear in any solution) and search (guess, propagate, backtrack). this page builds the machinery from the formalism up; the sudoku solver and hashiwokakero write-ups on this wiki are the same machinery pointed at actual puzzles.
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.
𐃏
You should not be permitted to write production code if you do not have an journeyman licence in regular expressions or floating point math. —Rob Pike
a regular expression is two things wearing one syntax: a seventy-year-old theorem about finite automata, and the single most-used text-processing tool on unix. 𐃏 this page takes both seriously: the theory tells you exactly what the notation can and cannot express, and the theory’s failure modes (backtracking blowups, backreference NP-hardness, the html-parsing folklore) are precisely where practitioners get burned.
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.