当前在线人数16258
首页 - 分类讨论区 - 娱乐休闲 - 大脑工作室版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
包子题:蝴蝶拼图
[版面:大脑工作室][首篇作者:gloomyturkey] , 2010年02月18日10:26:09 ,1128次阅读,28次回复
来APP回复,赚取更多伪币 关注本站公众号:
[首页] [上页][下页][末页] [分页:1 2 ]
gloomyturkey
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: gloomyturkey (一只郁闷的火鸡), 信区: BrainTeaser
标  题: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Thu Feb 18 10:26:09 2010, 美东)

http://www.7penguin.com/Puzzle/Butterfly/

点击绿色方块的相邻方块就可以移动绿色方块, 反悔一步点Regret ,重新开始点
Reset。如果成功解出,你的solution会自动显示。

喜欢puzzle的同学,应该一眼就认出这是曾经著名的sliding puzzle, 正式名称:15-puzzle, 通常小孩玩的是3x3的,所以叫8-puzzle.

一个叫Sam Loyd的家伙,1891年自称发明了这个游戏。但事实是,一个纽约的邮递员1874年就发明了这个玩意。当然Sam Loyd也还算有点贡献,他悬赏$1000解一个特殊的15-puzzle, 吸引了无数眼球。他的问题跟我贴的那个大同小异,当然我这个是有解的,要是你想到把蓝心换到右下角的话。他的问题确实是无解。1879年,Johnson & Story证明了大概一半的puzzle是无解的。有解的充要条件是:如果通过偶数次置换可以解的话。比如你把编号14和15的直接交换,那就是Sam Loyd悬赏的,这个需要1次置换完成,因为是奇数,所以无解。

让这个游戏失去吸引力的,我想有两个重要因素,一是有很简单的标准解法,你只要一层一层地解,一定可以解开所有可解的sliding puzzle. 另外,找到最短解法,是个NP hard problem, 意味着除了穷举,没什么必杀技。于是有人研究一些启发式算法,也还有效。但是这个游戏不管从理论,还是实际角度,好象都不那么吸引人了。也就沦为纯小孩玩具。

从游戏的角度,所有的15-puzzle, 据说都是80步以内可解的。

谁能80步以内解出这个puzzle, 双黄包就是他/她的了。请把答案贴在这儿,我好验证。




--

※ 修改:·gloomyturkey 於 Nov 23 21:52:03 2010 修改本文·[FROM: 173.54.]
※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 64.9.]

 
anniee
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: anniee (danding.....), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Thu Feb 18 13:12:07 2010, 美东)

43?

--

※ 修改:·anniee 於 Feb 18 15:04:26 2010 修改本文·[FROM: 146.151.]
※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 146.151.]

 
gloomyturkey
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: gloomyturkey (一只郁闷的火鸡), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Thu Feb 18 17:41:46 2010, 美东)


solution呢?

【 在 anniee (danding.....) 的大作中提到: 】
: 43?



--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 173.54.]

 
anniee
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: anniee (danding.....), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Fri Feb 19 00:17:46 2010, 美东)

位置编号
01-02-03-04
05-06-07-08
09-10-11-12
13-14-15-16

空格初始位置07
位置11/15/16/12/08/04/03/02/01/05/09/13/14的方块顺时针移动一格,
空格到位置14处
位置15/11/07/03/02/01/05的方块顺时针移动,空格移动到05
位置06/10/14/13/09的方块逆时针移动,空格移动到10
位置09/05/01/02/06的方块逆时针移动,空格移动到02
位置03/04/08/12/16的方块逆时针移动,空格移动到16,塌搭


【 在 gloomyturkey (一只郁闷的火鸡) 的大作中提到: 】
: solution呢?




--

※ 修改:·anniee 於 Feb 19 00:22:34 2010 修改本文·[FROM: 146.151.]
※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 146.151.]

 
gloomyturkey
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: gloomyturkey (一只郁闷的火鸡), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Fri Feb 19 09:09:02 2010, 美东)


anniee你是不是把问题理解错了,我照着你说的没有移出完整的图。问题是要把整个图
拼出来象这样:




--

※ 修改:·gloomyturkey 於 Feb 19 09:14:42 2010 修改本文·[FROM: 64.9.]
※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 64.9.]

此主题相关图片如下:

[删除]

 
anniee
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: anniee (danding.....), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Fri Feb 19 10:30:50 2010, 美东)


一开始你也没说要把那个移到那里啊。。。。

【 在 gloomyturkey (一只郁闷的火鸡) 的大作中提到: 】
: anniee你是不是把问题理解错了,我照着你说的没有移出完整的图。问题是要把整个图
: 拼出来象这样:



--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 146.151.]

 
braving
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: braving (water_mirror), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Fri Feb 19 10:43:57 2010, 美东)

我弄了80多下

【 在 gloomyturkey (一只郁闷的火鸡) 的大作中提到: 】
: anniee你是不是把问题理解错了,我照着你说的没有移出完整的图。问题是要把整个图
: 拼出来象这样:



--

※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 129.105.]

 
anniee
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 8 ]

发信人: anniee (danding.....), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Fri Feb 19 10:51:50 2010, 美东)

Your solution (63 steps):

6, 10, 14, 15, 11, 7, 3, 2, 1, 0, 4, 8, 12, 13, 14, 10, 6, 2, 1, 0, 4, 5, 9,
13, 12, 8, 4, 5, 9, 8, 4, 0, 1, 5, 9, 8, 12, 13, 14, 15, 11, 10, 6, 2, 3, 7
, 11, 10, 6, 7, 11, 15, 14, 10, 6, 7, 11, 15, 14, 13, 12, 8, 4, 0
--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 146.151.]

 
anniee
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 9 ]

发信人: anniee (danding.....), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Fri Feb 19 10:59:40 2010, 美东)

Steps:  59  Regret  Reset

Your solution (59 steps):

6, 10, 14, 15, 11, 7, 3, 2, 1, 0, 4, 8, 12, 13, 14, 10, 6, 2, 1, 0, 4, 5, 9,
13, 14, 15, 11, 10, 6, 2, 3, 7, 11, 10, 6, 7, 11, 15, 14, 10, 6, 7, 11, 15,
14, 13, 12, 8, 4, 5, 9, 8, 4, 0, 1, 5, 9, 8, 4, 0
--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 146.151.]

 
gloomyturkey
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 10 ]

发信人: gloomyturkey (一只郁闷的火鸡), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Fri Feb 19 11:37:01 2010, 美东)


这个解不错,请收包子。你是自己想出来的,还是算出来的?高手啊。

【 在 anniee (danding.....) 的大作中提到: 】
:  Steps:  59  Regret  Reset
: Your solution (59 steps):
: 6, 10, 14, 15, 11, 7, 3, 2, 1, 0, 4, 8, 12, 13, 14, 10, 6, 2, 1, 0, 4, 5,
9,
:  13, 14, 15, 11, 10, 6, 2, 3, 7, 11, 10, 6, 7, 11, 15, 14, 10, 6, 7, 11,
15,
:  14, 13, 12, 8, 4, 5, 9, 8, 4, 0, 1, 5, 9, 8, 4, 0




--

※ 修改:·gloomyturkey 於 Feb 19 11:39:27 2010 修改本文·[FROM: 64.9.]
※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 64.9.]

 
gloomyturkey
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 11 ]

发信人: gloomyturkey (一只郁闷的火鸡), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Fri Feb 19 11:42:27 2010, 美东)

80多下比我好多了,我是按标准解法一层一层的搬,搬了100多下才解开的。


【 在 braving (water_mirror) 的大作中提到: 】
: 我弄了80多下



--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 64.9.]

 
anniee
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 12 ]

发信人: anniee (danding.....), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Fri Feb 19 11:46:09 2010, 美东)

汗一个,我不会算,太高深了。。。。。
其实就相当于我之前的解了2/3
剩下的是对称的,
根据一开始的稍微再多走几步就行了
谢谢包子

【 在 gloomyturkey (一只郁闷的火鸡) 的大作中提到: 】
: 这个解不错,请收包子。你是自己想出来的,还是算出来的?高手啊。
: 9,
: 15,



--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 146.151.]

 
anniee
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 13 ]

发信人: anniee (danding.....), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Fri Feb 19 11:46:47 2010, 美东)

啥是标准解法?
【 在 gloomyturkey (一只郁闷的火鸡) 的大作中提到: 】
: 80多下比我好多了,我是按标准解法一层一层的搬,搬了100多下才解开的。



--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 146.151.]

 
gloomyturkey
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 14 ]

发信人: gloomyturkey (一只郁闷的火鸡), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Fri Feb 19 11:50:31 2010, 美东)


象我前面描述的,先拼最下面一层,再拼倒数第二层,然后拼右上角4个,最后剩左上
角3个就一定是对的了,否则无解。

用这种办法可以解所有的MxN的sliding puzzle.

【 在 anniee (danding.....) 的大作中提到: 】
: 啥是标准解法?



--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 64.9.]

 
gloomyturkey
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 15 ]

发信人: gloomyturkey (一只郁闷的火鸡), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Fri Feb 19 11:54:31 2010, 美东)


天才啊,佩服一下,看来我们思维方式完全不一样,我解题从来都是按部就班地解,一般不会想出你那种办法。

【 在 anniee (danding.....) 的大作中提到: 】
: 汗一个,我不会算,太高深了。。。。。
: 其实就相当于我之前的解了2/3
: 剩下的是对称的,
: 根据一开始的稍微再多走几步就行了
: 谢谢包子




--

※ 修改:·gloomyturkey 於 Feb 19 11:57:28 2010 修改本文·[FROM: 64.9.]
※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 64.9.]

 
braving
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 16 ]

发信人: braving (water_mirror), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Fri Feb 19 11:57:47 2010, 美东)

明显左下四分之一是不用动的。。。

【 在 gloomyturkey (一只郁闷的火鸡) 的大作中提到: 】
: 象我前面描述的,先拼最下面一层,再拼倒数第二层,然后拼右上角4个,最后剩左上
: 角3个就一定是对的了,否则无解。
: 用这种办法可以解所有的MxN的sliding puzzle.



--

※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 129.105.]

 
gloomyturkey
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 17 ]

发信人: gloomyturkey (一只郁闷的火鸡), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Fri Feb 19 12:09:37 2010, 美东)


左下不用动就可解,那是对这个特定的问题而言。对这个问题最快的解法,我直觉是需
要动左下角的。象anniee解的59步,就是动了左下角的。

【 在 braving (water_mirror) 的大作中提到: 】
: 明显左下四分之一是不用动的。。。



--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 64.9.]

 
braving
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 18 ]

发信人: braving (water_mirror), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Fri Feb 19 12:43:22 2010, 美东)

o...
有道理啊

【 在 gloomyturkey (一只郁闷的火鸡) 的大作中提到: 】
: 左下不用动就可解,那是对这个特定的问题而言。对这个问题最快的解法,我直觉是需
: 要动左下角的。象anniee解的59步,就是动了左下角的。



--

※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 129.105.]

 
anniee
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 19 ]

发信人: anniee (danding.....), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Fri Feb 19 15:06:24 2010, 美东)

过奖啦过奖啦
我角得一般通用解法都会是比较慢的解法吧
比如你走迷宫,一直沿着一侧墙壁走总能走出去
而且这个题其实只要动3块其他的都不用动,放的地方有那么特殊
所以还是会有特殊路径地

【 在 gloomyturkey (一只郁闷的火鸡) 的大作中提到: 】
: 天才啊,佩服一下,看来我们思维方式完全不一样,我解题从来都是按部就班地解,
一般不会想出你那种办法。



--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 146.151.]

 
WHITETO0
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 20 ]

发信人: WHITETO0 (大白兔), 信区: BrainTeaser
标  题: Re: 包子题:蝴蝶拼图
发信站: BBS 未名空间站 (Wed Feb 24 00:37:27 2010, 美东)

let me try

【 在 gloomyturkey (一只郁闷的火鸡) 的大作中提到: 】
: http://www.marmot101.com/Puzzle/Butterfly
: 点击绿色方块的相邻方块就可以移动绿色方块, 反悔一步点Regret ,重新开始点
: Reset。如果成功解出,你的solution会自动显示。
: 喜欢puzzle的同学,应该一眼就认出这是曾经著名的sliding puzzle, 正式名称:15
-puzzle, 通常小孩玩的是3x3的,所以叫8-puzzle.
: 一个叫Sam Loyd的家伙,1891年自称发明了这个游戏。但事实是,一个纽约的邮递员
1874年就发明了这个玩意。当然Sam Loyd也还算有点贡献,他悬赏$1000解一个特殊的
15-puzzle, 吸引了无数眼球。他的问题跟我贴的那个大同小异,当然我这个是有解的
,要是你想到把蓝心换到右下
: 让这个游戏失去吸引力的,我想有两个重要因素,一是有很简单的标准解法,你只要
一层一层地解,一定可以解开所有可解的sliding puzzle. 另外,找到最短解法,是个
NP hard problem, 意味着除了穷举,没什么必杀技。于是有人研究一些启发式算法,
也还有效。但是这个游戏不
: 从游戏的角度,所有的15-puzzle, 据说都是80步以内
可解的。
: 谁能80步以内解出这个puzzle, 双黄包就是他/她的了。请把答案贴在这儿,我好验
证。



--

※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 173.225.]

[首页] [上页][下页][末页] [分页:1 2 ]
[快速返回] [ 进入大脑工作室讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996