My two year old taught me constraint solving
11 days ago
- The author explores the algorithmic challenge of building closed Brio train track layouts using a set of pieces.
- Three solvers are compared: backtracking search (exponential, simple), constraint solving with forward checking and backjumping (improved but still limited), and SAT solver with clause learning (allows selecting pieces, more powerful but slower).
- The son's insights guide the author: constraint satisfaction, global constraints, and SAT solving for optimization.
- Key lesson: different questions (e.g., 'does this set close?' vs. 'what pieces make the most complex network?') require different algorithmic approaches.