五格骨牌的三染色问题:2339 种铺法里有多少种能上色?
引言
用 12 块五格骨牌平铺 6×10 矩形共有 2339 种方法——但如果我要求相邻骨牌颜色不同,连角都不能碰,还剩几种?
这是《The Art of Computer Programming》Volume 4B 中的习题 7.2.2.1-277,难度评级 [25](TAOCP 的评级范围 0–50,数字越大越难)。答案是:94 种,仅占约 4%。
用 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 矩形