g**********y 发帖数: 14569 | 1 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, 吸引了无数眼球。他的问题跟我贴的那个大同小异,当然我这个是有解的,要是你想到把蓝心换到右下角的话。他的问题确实是无解。1879年,Johnson & Story证明了大概一半的puzzle是无解的。有解的充要条件是:如果通过偶数次置换可以解的话。比如你把编号14和15的直接交换,那就是Sam Loyd悬赏的,这个需要1次置换完成,因为是奇数,所以无解。
让这个游戏失去吸引力的,我想有两个重要因素,一是有很 | a****e 发帖数: 5562 | | g**********y 发帖数: 14569 | 3 solution呢?
【在 a****e 的大作中提到】 : 43?
| a****e 发帖数: 5562 | 4 位置编号
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,塌搭
【在 g**********y 的大作中提到】 : solution呢?
| g**********y 发帖数: 14569 | 5 anniee你是不是把问题理解错了,我照着你说的没有移出完整的图。问题是要把整个图
拼出来象这样: | a****e 发帖数: 5562 | 6 一开始你也没说要把那个移到那里啊。。。。
【在 g**********y 的大作中提到】 : anniee你是不是把问题理解错了,我照着你说的没有移出完整的图。问题是要把整个图 : 拼出来象这样:
| b*****g 发帖数: 919 | 7 我弄了80多下
【在 g**********y 的大作中提到】 : anniee你是不是把问题理解错了,我照着你说的没有移出完整的图。问题是要把整个图 : 拼出来象这样:
| a****e 发帖数: 5562 | 8 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 | a****e 发帖数: 5562 | 9 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 | g**********y 发帖数: 14569 | 10 这个解不错,请收包子。你是自己想出来的,还是算出来的?高手啊。
9,
15,
【在 a****e 的大作中提到】 : 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
| | | g**********y 发帖数: 14569 | 11 80多下比我好多了,我是按标准解法一层一层的搬,搬了100多下才解开的。
【在 b*****g 的大作中提到】 : 我弄了80多下
| a****e 发帖数: 5562 | 12 汗一个,我不会算,太高深了。。。。。
其实就相当于我之前的解了2/3
剩下的是对称的,
根据一开始的稍微再多走几步就行了
谢谢包子
【在 g**********y 的大作中提到】 : 这个解不错,请收包子。你是自己想出来的,还是算出来的?高手啊。 : : 9, : 15,
| a****e 发帖数: 5562 | 13 啥是标准解法?
【在 g**********y 的大作中提到】 : 80多下比我好多了,我是按标准解法一层一层的搬,搬了100多下才解开的。
| g**********y 发帖数: 14569 | 14 象我前面描述的,先拼最下面一层,再拼倒数第二层,然后拼右上角4个,最后剩左上
角3个就一定是对的了,否则无解。
用这种办法可以解所有的MxN的sliding puzzle.
【在 a****e 的大作中提到】 : 啥是标准解法?
| g**********y 发帖数: 14569 | 15 天才啊,佩服一下,看来我们思维方式完全不一样,我解题从来都是按部就班地解,一般不会想出你那种办法。
【在 a****e 的大作中提到】 : 汗一个,我不会算,太高深了。。。。。 : 其实就相当于我之前的解了2/3 : 剩下的是对称的, : 根据一开始的稍微再多走几步就行了 : 谢谢包子
| b*****g 发帖数: 919 | 16 明显左下四分之一是不用动的。。。
【在 g**********y 的大作中提到】 : 象我前面描述的,先拼最下面一层,再拼倒数第二层,然后拼右上角4个,最后剩左上 : 角3个就一定是对的了,否则无解。 : 用这种办法可以解所有的MxN的sliding puzzle.
| g**********y 发帖数: 14569 | 17 左下不用动就可解,那是对这个特定的问题而言。对这个问题最快的解法,我直觉是需
要动左下角的。象anniee解的59步,就是动了左下角的。
【在 b*****g 的大作中提到】 : 明显左下四分之一是不用动的。。。
| b*****g 发帖数: 919 | 18 o...
有道理啊
【在 g**********y 的大作中提到】 : 左下不用动就可解,那是对这个特定的问题而言。对这个问题最快的解法,我直觉是需 : 要动左下角的。象anniee解的59步,就是动了左下角的。
| a****e 发帖数: 5562 | 19 过奖啦过奖啦
我角得一般通用解法都会是比较慢的解法吧
比如你走迷宫,一直沿着一侧墙壁走总能走出去
而且这个题其实只要动3块其他的都不用动,放的地方有那么特殊
所以还是会有特殊路径地
一般不会想出你那种办法。
【在 g**********y 的大作中提到】 : 天才啊,佩服一下,看来我们思维方式完全不一样,我解题从来都是按部就班地解,一般不会想出你那种办法。
| W******0 发帖数: 65 | 20 let me try
-puzzle, 通常小孩玩的是3x3的,所以叫8-puzzle.
1874年就发明了这个玩意。当然Sam Loyd也还算有点贡献,他悬赏$1000解一个特殊的
15-puzzle, 吸引了无数眼球。他的问题跟我贴的那个大同小异,当然我这个是有解的
,要是你想到把蓝心换到右下
一层一层地解,一定可以解开所有可解的sliding puzzle. 另外,找到最短解法,是个
NP hard problem, 意味着除了穷举,没什么必杀技。于是有人研究一些启发式算法,
也还有效。但是这个游戏
可解的。
证。
【在 g**********y 的大作中提到】 : 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, 吸引了无数眼球。他的问题跟我贴的那个大同小异,当然我这个是有解的,要是你想到把蓝心换到右下角的话。他的问题确实是无解。1879年,Johnson & Story证明了大概一半的puzzle是无解的。有解的充要条件是:如果通过偶数次置换可以解的话。比如你把编号14和15的直接交换,那就是Sam Loyd悬赏的,这个需要1次置换完成,因为是奇数,所以无解。 : 让这个游戏失去吸引力的,我想有两个重要因素,一是有很
| | | o*t 发帖数: 655 | | o*t 发帖数: 655 | | o*t 发帖数: 655 | | o*t 发帖数: 655 | | g**********y 发帖数: 14569 | 25 以前的网站过期了,重新注册了一个,
http://www.7penguin.com/Puzzle/Butterfly/
【在 o*t 的大作中提到】 : 打不开啊
| h******7 发帖数: 980 | 26 61steps
6, 5, 4, 0, 1, 5, 4, 8, 9, 5, 6, 10, 9, 13, 14, 10, 6, 7, 11, 15, 14, 10, 11
, 7, 6, 10, 14, 13, 9, 5, 4, 0, 1, 5, 6, 10, 9, 5, 4, 8, 9, 10, 6, 5, 9, 8,
4, 0, 1, 5, 4, 0, 1, 5, 9, 8, 4, 0, 1, 5, 4, 0 |
|