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次置换，所以无解。
让这个游 | l*****8
发帖数: 16949 | | g**********y
发帖数: 14569 | 3 hehe, 看来陷阱还是有用的啊。这是儿子带回来的Valentine Day gift. 我想，小孩的
，能难到哪儿去。几分钟，就搞成这个你现在看到的状态。但是下面无论怎么试，我都解
不开。我觉得有点不对。
去google了一下，才发现，我陷进死胡同了。这个是无解的状态。或者说，我有一个错
误的假设，以为那个蓝心形是在左上角的，其实蓝心形应该跟右下角的心形交换。否则
无解，这个是可以数学证明的。
【在 l*****8 的大作中提到】
: 太难了。现在已经过了废寝忘食解难题的阶段了。
| a****e
发帖数: 5562 | 4 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 | b********n
发帖数: 4256 | 5 不知道，帮顶
-puzzle, 通常小孩玩的是3x3的，所以叫8-puzzle.
1874年就发明了这个玩意。当然Sam Loyd也还算有点贡献，他悬赏$1000解一个特殊的
15-puzzle, 吸引了无数眼球。他的问题跟我贴的那个大同小异，当然我这个是有解的
，要是你想到把蓝心换到右下角的话。他的确实是无解。1879年，Johnson & Story证
明了大概一半的puzzle是无解的。有解的充要条件是：如果通过偶数次置换可以解的话
。比如你把编号14和15的直接交换，那就是Sam Loyd悬赏的，那个需要1次置换，所以
无解。
一层一层地解，一定可以解开所有可解的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次置换，所以无解。
: 让这个游
|
|
