[求助]35子棋怎么排？

乌木

36个位置，35个子，初态是混乱的，只能一次走一子，走入空格，相当于空格在移动，即空格的四面的任一子可以移入空格。头33个子还好排，最后34和35要求对换，玩不转啦，求助！有无解的可能吗？

[此贴子已经被作者于2006-12-31 11:43:02编辑过]

robester

<P>楼主的是六阶的，所以我不知道34和35是不是可以互换，不过三五等奇数阶只换最后面两个是无解的。</P>
<P>下面介绍一个证明奇数阶无解的简单方法</P>
<P>&nbsp;</P>
<P>需要知道的基础知识是：高中时学过的奇排列，偶排列的定义，以及其性质：相邻两个数的交换改变了序列奇偶性</P>
<P>&nbsp;</P>
<P>证明过程是：</P>
<P>&nbsp;</P>
<P>我们把所有数字按先行后列的顺序全部排成长长的一行，称之为整个序列</P>
<P>&nbsp;</P>
<P>游戏中的空格的动作有两种，左右移动和上下移动，左右移动明显不改变整个序列的奇偶性，上下移动相当于进行了偶数次相邻数交换（比如五阶空格的上下移动相当于进行了四次相邻数交换），所以整个序列的奇偶性进行了偶数次改变，相当于没变，即在正确游戏的过程中整个序列的奇偶性是不变的</P>
<P>&nbsp;</P>
<P>而只交换最后面两个数改变了整个序列的奇偶性，所以只交换最后面两个是无解的</P>

[ 本帖最后由 robester 于 2008-5-4 01:42 编辑 ]

乌木

<P>15楼的状态可以另行排序，排法不是最好的，只求排好交差。移动路线不管闭合不闭合，必须含有一个空格，否则动不起来，和魔方的块的循环不一样。</P>
<P>&nbsp;</P>
<P> </P>
<P>&nbsp;</P>

[ 本帖最后由 乌木 于 2008-5-4 09:55 编辑 ]

乌木

<P>

原帖由 <I>kexin_xiao</I> 于 2008-5-1 18:12 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=124146&amp;ptid=3206" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 排列组合问题,纯数学问题了

</P>
<P>&nbsp;</P>
<P>是数学问题，但好像不是排列组合问题。大概和19世纪风靡世界的“15子棋”一样的吧？</P>
<P>&nbsp;</P>
<P>数学家证明，下面的排列要把14、15的位置更正过来是不可能的：（有一个空格，只能移动棋子。）</P>
<P>&nbsp;</P>
<P>1&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;2&nbsp; &nbsp; 3&nbsp;&nbsp; &nbsp;4</P>
<P>5&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;6&nbsp;&nbsp;&nbsp; 7&nbsp;&nbsp; &nbsp;8</P>
<P>9&nbsp;&nbsp;&nbsp; 10&nbsp; 11&nbsp; 12</P>
<P>13&nbsp; 15&nbsp; 14</P>

[ 本帖最后由 乌木 于 2008-5-2 00:19 编辑 ]

kexin_xiao

排列组合问题,纯数学问题了

乌木

那说明书中6道题有三道属于一种“常规态”可以排出的，另三道题属于另一种“常规态”可排出的。对于11楼给出的常规态，下面的排不出，要改为再下面的花样才可得：
1  7  13 19 25 31
2  8  14 20 26 32
3  9  15 21 27 33
4 10  16 22 28 34
5 11  17 23 29 35
6 12  18 24 30  X  排不出

下面的行：
X  6  12 18 24 30
1  7  13 19 25 31
2  8  14 20 26 32
3  9  15 21 27 33
4 10  16 22 28 34
5 11  17 23 29 35

乌木

类似地，说明书中的
1   2  4  7 11 16
3   5  8 12 17 22
6   9 13 18 23 27
10 14 19 24 28 31
15 20 25 29 32 34
21 26 30 33 35  X    排不出，

但能排出下面的：
1   3  6 10 15 21
2   5  9 14 20 26
4   8 13 19 25 30
7  12 18 24 29 33
11 17 23 28 32 35
16 22 27 31 34  X

乌木

那说明书好像有误。

它的常规态是：
1…………6
7…………12
……………
……………
25………30
31……35 X

但说明书中有一题：
1  2  3  4  5  6
20 21 22 23 24 7
19 32 33 34 25 8
18 31 X  35 26 9
17 20 29 28 27 10
16 15 14 13 12 11   经试做，排不出（应该是另一种常规态能排出）。

只能排出如下的回纹花样：
6  5  4  3  2  1
7  24 23 22 21 20
8  25 34 33 32 19
9  26 35 X  31 18
10 27 28 29 30 17
11 12 13 14 15 16

乌木

果然如阳光兄和沈兄所说。

我为了使1楼中交换35和34，不得不采用重装手段，打乱再排就成功了（第一行1～6，……第六行31～35，右下角空，算是常规态A吧）。看了阳光兄的话，不相信，就实践一下－－不再重装，把A态打乱，排列结果为：左上角空，第一行为X21345，……第六行为30～35。这也是证明阳光兄的说法。

可见，同样一副棋子，排列花样不同，有的成功，有的不成功（如果这仅仅交换两个子是不可能的话）。

即
1  2  3  4  5  6
…………
…………
…………
…………
31 32 33 34 35 X  

可以转变为：
X  2  1  3  4   5
…………
…………
…………
…………
30 31 32 33 34 35   或者任意别的一对邻子错换位置。

也就是说，买到一副这种棋子，其“常规态”或许是左上角应空，或许是右下角应空。两者不相容。

原来是，不能仅仅看结果（什么180°、倒序重新编号等等），而与排列过程有关。具体的我也说不清，只是感到像发现新大陆似的。实在奥妙啊！谢谢两位！

[此贴子已经被作者于2006-12-31 11:50:46编辑过]

阳光

本人在此声明：5楼的言论是错的

              3楼的言论是对的

              5楼的方法适用于奇数阶

              3楼的方法适用于偶数阶

              1楼的情况当属于偶数阶

              楼主不妨试一下3楼的方法，把空格设在原空格的对角线另一边，一定可以使35个数字按顺序排列，34，35也会回到正确位置，34在前，35在后，1到35都是常规的左到右递增。

还有，四楼的疑问可以回答

     四楼问该如何交换 2和1，之所以会出现这个问题，那时因为您仍把空格留在图片的右下角，这么做无论怎么排都会有两个数字是颠倒的，在一楼的图片中，如果空格留在图片的左上方，1和2  自然会更正过来。（当然我说的右下角只是相对一楼的图片而言，棋盘旋转180度的话就是左上角。） 这时你再把1当成35，2当成34等，最后还是3楼的情况。 

 现在回答8楼的疑问

奥妙何在，奥妙就在于

  一楼的空格相对于图片来说是 图片中的右下角

而8楼所描绘的：

180°旋转并依倒序改编号后：
1  2  3  4  5  6
……………
……………
……………
……………
31 32 33 34 35 X      常规排法
这其中的空格相对于图片来说其实是图片中的左上角，只不过被您旋转了180度才会在右下角，但相对于图片来说它仍是图片的左上角。

  把空格留在图片的右下角和把空格留在图片的左上角

这是图片的两种不同情况，会得到两种不同的结果，前者会使34，35颠倒，后者却不会，

不小心把两种情况和结果混为一谈自然会 产生矛盾。

你不能用一个颠倒图片和一个没颠倒的图片比较，把最后那个图 旋转的180度 旋回来，空格 便 变回左上角，这时移动棋子把左上角堵上，右下角空出来，从大到小排列，排列完后，会发现1与2颠倒了，1在前而2在后。然后再依倒序改编 回来，不就是一楼的图片么，34与35颠倒了．

其实着两个图形并不矛盾，因为一个是正的，一个是倒的．

总结一下

（１）棋盘（即一楼图片）不旋转，解的情况是

X  1  2  3  4  5
……………
……………
……………
……………
30 31 32 33 34 35

（２）棋盘（即一楼图片）旋转１８０度，解的情况是

1  2  3  4  5  6
……………
……………
……………
……………
31 32 33 34 35 X  

我们可以发现（１）和（２）中的空格其实是同一个位置，所以只有把空格留在这固定的位置上才会有解，所以严格的说来，解其实只有一个，是唯一的．

呵呵，不知各位是否同意我的总结．