娃问数字华容道

[（ヅ）]

2x8的棋盘上有7个棋子

1 2 3 4
6 7 5

最后一个位置是空的，每一步可以把空位与相邻的一个棋子交换位置，比如

1 2 3
6 7 5 4

问题是，怎么可以排序得到
1 2 3 4
5 6 7

[verdelite]

2x8的棋盘上有7个棋子

1 2 3 4
6 7 5

最后一个位置是空的，每一步可以把空位与相邻的一个棋子交换位置，比如

1 2 3
6 7 5 4

问题是，怎么可以排序得到
1 2 3 4
5 6 7

2x4？我觉得可以写程序来穷举。

[(ッ)]

2x4？我觉得可以写程序来穷举。

新年别人都在打牌我花了半天时间才想明白这个问题

关键在于这种pattern

a b
c d e

的时候，可以把(a,c,d)看成一个tupple做旋转，即可以得到

c b
d a e

直觉应该用群论来建立模型(参考 D6)，我太菜了想不明白

[randomatrices]

总结几个规律以后还是比较简单的：
1）空格在大多数时间应该在中间俩列。

2）zone和等价棋形的概念
zone指一个2X2的区域， 这个区域必需有一个空格才能移动棋子（显然的）
但仅仅在zone内移动棋子， 得到的都是等价棋形，如

3）从endgame出发倒推，如 需得到
1 2 3 4
5 6 7
只要得到
5 13
6724
即可， refer 1)可以得到zone
5
6 7 的所有等价棋形， 这些都可以得到endgame。
而得到
7 13
5624 还是很显然的。

这些还只是ad-hoc, 还没有形成完整的algorithmic 。是不是一个初始构型可以定义一个顺序量？ 有没有不能到达的构型？

2x8的棋盘上有7个棋子

1 2 3 4
6 7 5

最后一个位置是空的，每一步可以把空位与相邻的一个棋子交换位置，比如

1 2 3
6 7 5 4

问题是，怎么可以排序得到
1 2 3 4
5 6 7

[(ッ)]

总结几个规律以后还是比较简单的：
1）空格在大多数时间应该在中间俩列。

2）zone和等价棋形的概念
zone指一个2X2的区域， 这个区域必需有一个空格才能移动棋子（显然的）
但仅仅在zone内移动棋子， 得到的都是等价棋形，如

3）从endgame出发倒推，如 需得到
1 2 3 4
5 6 7
只要得到
5 13
6724
即可， refer 1)可以得到zone
5
6 7 的所有等价棋形， 这些都可以得到endgame。
而得到
7 13
5624 还是很显然的。

这些还只是ad-hoc, 还没有形成完整的algorithmic 。是不是一个初始构型可以定义一个顺序量？ 有没有不能到达的构型？

我想了大半天还是有点收获的。这个问题实际上是3个问题

1. 可解的必要条件是什么。举个例子, 2x2的棋盘

1
2 3

就不可解. 这个不算很难

2. 可解的充分条件是什么，op问的实际上是这个，也就是要找到可解的算法.

3. 可解的时候，如何找到最优解,使用最小步数.这个我也不知道

[YWY]

把空格记作8， 那么一开始就是
1234
7658
可直接记作12347658。这是个奇排列。

每做一次邻位交换，就是把那两个数（其中一个必定是8）换位，每换一次就改变一次排列奇偶性。另一方面，要想让8回到右下角（起始位置），8这个数字自始至终必须只能走偶数步，也就是说整个数列只能经历偶数次奇偶交替。由于一开始是奇排列，所以当8回到右下角时，排列必须依然是奇排列。

所以，按规则，无论怎么走，也走不出
1234
5678
这个结局。能走出这个结局的必要条件是初始状态是偶排列，

是不是充分我还需再想想。

[YWY]

是不是充分我还需再想想。

应该也是充分的。就是说，能走回
1234
5678
的充要条件是初始排列（右下角是空格8）为偶排列。

至于为啥是充分的，涉及到具体操作策略：大概就是可以先针对1操作，通过（战略性）移动空格8，最终把1移到左上角；然后针对5，把它移到1的下面；然后就是归纳法（因为剩下的是个小的2 x 3矩形）。

[(ッ)]

应该也是充分的。就是说，能走回
1234
5678
的充要条件是初始排列（右下角是空格8）为偶排列。

至于为啥是充分的，涉及到具体操作策略：大概就是可以先针对1操作，通过（战略性）移动空格8，最终把1移到左上角；然后针对5，把它移到1的下面；然后就是归纳法（因为剩下的是个小的2 x 3矩形）。

这是正确思路，只要能保证8在1的右边，就能使得1往左和往上移动，参考3楼的办法。同理可以放置2,3,4,....

细节上有一些需要考虑的地方