2012年02月11日 星期六 10:50
哲思的高手们,这个问题困扰了我很久,
第一次接触到这个问题是在09年的一篇文章里,作者画了这样一个图(见1楼)
注意到相同颜色构成的一个子块,它们都是8联骨牌的一种。随后我查了多联骨牌(polyominoes)的资料,http://www.matrix67.com/blog/archives/tag/%E5%A4%9A%E8%81%94%E9%AA%A8%E7%89%8C在这篇博文给出的例子中“用相同形状的多联骨牌拼接完全对称图形 ”跟我将要想做的事情比较相似,但是解是直接给出的,没有必要的分析,我想编程实现苦于找不到门路。
现在我想解决这样的问题:
问题:给定一组均匀分布的栅格点的坐标集合,其在平面上分布成一中心对称区域(例如圆,正n边形)。现在我将用多联骨牌这块区域进行分割(或称为填充);
要求:1.只能使用一种类型的骨牌及其经过对称变换后得到的骨牌;
2.每一个栅格点都属于且只属于某一个骨牌(称其为完全填充);若不存在完全填充解,则要求出未被骨牌填充的栅格点数目最小的解(称其为次完全填充);
2012年02月11日 星期六 10:57
这是文献中的图:
这是已确定的栅格区域:
2012年02月11日 星期六 11:09
我想:从中心开始,向四周不断地添加骨牌,添加过程中保持1.对称原则;2.不留空原则;3.不超越区域边界原则,这样就跟俄罗斯方块游戏很像了。
不知道有没有更方便的方法?
RY大哥,这有没有现有的模块啊?要是有就更好了
2012年02月11日 星期六 11:47
2012年02月14日 星期二 00:05
感谢RY大哥提供的链接!
我大概明白了,可这是一个精确覆盖“Exact cover”问题。
Zeuux © 2024
京ICP备05028076号