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 |
|
