趣题:在指定形状的棋盘内放置n个相同的图形
icon2 Brain Storm | icon4 2008-5-15 14:48| icon33 Comments | 本文内容遵从CC版权协议 转载请注明出自matrix67.com

上个月Erich Friedman的Math Magic提出了这样的问题:
给定一个指定形状的棋盘,给定一个大于2的整数n,找出一个面积最大的图形S使得n个S能够不重叠地装进这个棋盘里。
问题提出之后得到了不少有趣的构造,这些构造是否为最优解还有待进一步证明。

 
由三个格子组成的棋盘共有两种本质不同的形状。“长条形”已经不用多考虑,“拐角形”中n=2, 3, 6时的最优解也是非常显然的。拐角形棋盘是可以分成四等分的。但是,在这个棋盘中放置5个相同的图形就没那么容易了。已知的最优方案占据了整个棋盘约0.959的面积。放置7个相同的图形研究起来更困难一些。已知最优解为0.956。

      

 
由四个格子组成的棋盘中,L形和T字形在n=2时各有一个15/16的解;

   

Károly Hajba找到了n=5的L形棋盘目前已知的最优解,它占据棋盘约0.972的面积。

 
五个格子组成的棋盘变化更多,构造也更有趣。
n=2时有一些非常巧妙的构造,它们都是由Dick Hess发现的,面积分别为棋盘的0.928、9/10、9/10、0.871和0.864:

   

   

 
Károly Hajba找到了拐角形在n=3时目前已知的最优解0.917。

 
大家可以到这里查看一些更复杂的情况。

3 条回复

  • 楼层: 沙发 | | 沙渺 说:

    沙发抢到。

  • 楼层: 板凳 | | dahe_1984 说:

    我也先占个座位。
    谁对推箱子游戏感兴趣啊?我还差2关没过去。
    不知道有什么技巧!!

  • 楼层: 地毯 | | hetong_007 说:

    唔唔~忍不住要打广告了~
    http://hetong007.googlepages.com/well%2Cpushing%21
    这里有我自己写的一个刚好够用的解推箱子的程序
    用的深度搜索算法加上死形判断剪枝

    但愿能够有点帮助~

您也随便说几句吧:

请注意:如果您是第一次在本站发表评论,您的评论需要通过管理员的审核。

您可以在Gravatar设置您的头像。