Python和科学计算认证群组  - 讨论区

标题:一个类似于俄罗斯方块游戏的问题,请大家帮忙看看

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

这个想起来就比较复杂,google一下吧。

例如我找到了一个:

http://puzzler.sourceforge.net/

2012年02月14日 星期二 00:05

感谢RY大哥提供的链接!

我大概明白了,可这是一个精确覆盖“Exact cover”问题。

如下红色区域有误,请重新填写。

    你的回复:

    请 登录 后回复。还没有在Zeuux哲思注册吗?现在 注册 !

    Zeuux © 2024

    京ICP备05028076号