两岁儿子教我constraint solving
My two year old taught me constraint solving
我的两岁儿子是个Brio木质火车迷，却有个奇怪规矩：只许我看，不许我碰。为了陪他玩，我开始研究轨道布局的算法逻辑。没想到，这个看似简单的玩具背后藏着复杂的constraint solving问题。从简单的圆形轨道到加入交叉口的复杂网络，我尝试用backtracking搜索和SAT solver来寻找最优解。在这个过程中，儿子不仅纠正了我的几何术语，还展现出惊人的逻辑直觉。原来，最深刻的算法灵感，有时就藏在孩子的游戏里。
我意识到，这是一个有趣的算法问题，正躺在我面前的地板上。
HN 评论区
37- hexasquid
太神了。我两岁的儿子在讲解 Curry-Howard-Lambek 对应关系时，居然忘了提 Lambek。小孩子啊。
- dmoy
虽然也是和两岁的孩子玩 Brio 积木，但我想到了文中没提到的另一个维度——超宽松的公差会让搜索空间变得非常奇怪。
按两岁孩子的典型作风，我的孩子会尽可能弯曲规则，硬是把零件塞到公差的极限，让本来拼不上的东西强行拼上。8 块拼成圆圈？行吧，挺酷。但如果你有一套传了 40 年的老 Brio 积木，你完全能拼出一个 7 块的“圆圈”。
所以我决定哪天要把这个做成一道面试题，看看大家能不能想出一个好办法：给定一组零件及其公差范围，判断它们能否连接起来等等。目前还没想透到能直接用于面试的程度，但总有一天会完善的。
- wiredfool
我和孩子们玩 Lego Duplo 轨道时也有过类似经历，拓扑结构差不多，但道岔引入了系统状态。火车“倒车”通过道岔时，会设定下次从反方向来时返回该方向。
于是我们的目标就是让火车表现出有趣的行为，比如自主跑完整个轨道，自己推动道岔。我记得最复杂的一次是做了一个 4 位计数器。
这孩子现在正在读计算机科学和数学学位的最后一年，看来是验证成功了。
- olooney
我为这个项目写了好几个多格骨牌求解器：
https://www.oranlooney.com/demos/soma-forest/
其中一个用了 Z3 进行约束求解，速度确实还不错。但最快的那个其实是一个用 Rust 写的简单回溯求解器，它利用位运算技巧来快速检测重叠。对于多格骨牌这类问题，根据棋盘大小，这能带来 10 到 100 倍的常数级速度提升。再聪明的求解器也达不到这个效果。
- elcaro
10 年前我读过一篇类似的文章，涵盖了一些相同的内容，里面还有一些很棒的 SVG 图。