用 Dancing Links 解决五格骨牌平铺问题
引言
Donald Knuth 在《The Art of Computer Programming》Volume 4B 中提出了 Dancing Links (DLX) 算法——一种优雅地解决精确覆盖问题的回溯算法。本文将探讨习题 7.2.2.1-31 中提到的经典应用：五格骨牌平铺问题。
什么是五格骨牌？
五格骨牌（Pentominoes）是由 5 个单位正方形连接而成的多格骨牌。不考虑旋转和翻转，共有 12 种 不同的五格骨牌，通常用字母 F, I, L, P, N, T, U, V, W, X, Y, Z 来命名：
问题定义
经典问题：用全部 12 种五格骨牌各一片，能否精确平铺一个 6×10 的矩形区域？
这个问题可以推广到：
- 5×12 矩形
- 4×15 矩形
- 3×20 矩形
谁养斑马？——用算法终结逻辑推理题
我花了一个小时没解出来，然后写了 30 行代码，算法用不到 1 毫秒解完了。
这道题就是著名的”斑马谜题”（又叫爱因斯坦谜题）：五个人住一排房子，每人国籍不同、职业不同、宠物不同、饮料不同、房子颜色不同，给你一堆线索，问——谁养斑马？
1962 年发表在 Life International 杂志上，据说只有 2% 的人能解出来。
这篇文章介绍一种完全不同的做法：把谜题翻译成 XCC 问题，让舞蹈链算法自动求解。不用画表格，不用推理，只需要把”什么是合法答案”描述清楚。
然后我们反过来——让算法自动出一道新的逻辑推理题。
博客搬家：从 GitHub Pages 到自定义域名
最近做了一件拖了很久的事情——给博客换了个域名。新地址是 blog.morefreeze.top，旧的 morefreeze.github.io 会自动跳转过来，不影响之前收藏的链接。
