发一篇我的关于滑块游戏的学术论文

sokoban

这篇文章《Sliding puzzles and rotating puzzles on graphs》写于2009年，2011年才发表在学术期刊《Discrete Math》。
刚才看到 poe 兄的帖子和博客 http://bbs.mf8-china.com/viewthread.php?tid=83295 提到关于一般滑块游戏的 Wilson定理，
想起了我的这篇拙作。我的文章就是讨论关于一般滑块游戏的 Wilson定理的。
另外还涉及到著名的魔方爱好者Jaap Scherphuis在他的网页上证明的关于Rotational Puzzle的一个定理，我称之为Scherphuis定理。
Jaap 的网页文章：http://www.jaapsch.net/puzzles/graphpuzz.htm
我的文章主要是讨论了这两个定理 ( Wilson定理和Scherphuis定理 ) 的关系，用Scherphuis定理证明Wilson定理。
文章只涉及到较为基本的图论和置换群的知识，论坛里有不少朋友数学功底都颇高，应该都看得明白，欢迎批评指正。

DM2011.pdf (231.29 KB, 下载次数: 56)

2011-10-11 23:28:22 上传

下载次数: 56

xwfh2000

专业研究，赞一个

qiaoyisi

poe兄的帖子侧重于理论，乌木和大烟头兼有，邱志宏也有原创，我感觉工程师出身的如台湾的邱海华好像更侧重于实践经验的总结。

qiaoyisi

诸如魔板、魔方、魔尺相关理论我几乎不去碰它，一是国内外学者研究都很深入了，二是这方面的mod实在太多（相对于孔明锁来说）、每天更新太快！但是我仍在关注和收藏实物魔方（已有近400多个山寨和品牌的）和相关大量文献，等以后有精力和充裕资金再研究不迟。

[ 本帖最后由 qiaoyisi 于 2011-10-13 16:03 编辑 ]

sokoban

原帖由 qiaoyisi 于 2011-10-13 08:50 发表
另外楼主对于本群中＂另类华容道＂的帖子里所列举的例子能否做一个类型 ...

我对另类“华容道“的分类没有什么心得，这方面 poe 兄比较有研究，他的博客对各种谜题的涉及面很广泛。

我比较有兴趣的是对“魔板”的分类研究，如8块板有多少个不等价的可能？好像只有2种，一种是常见的2x4矩形。另外一种
我制作过，见 http://bbs.mf8-china.com/viewthread.php?tid=26005
10块板呢？12块呢？。。。。
这个研究不是特别难，但是需要大量动手试验的时间，没有时间去做。希望能看到彻底的总结。

qiaoyisi

关于更一般的旋转谜题，很早以前记得在国外哪个大学的论坛看到过，也是用群论写的一篇文章，后来的稳操胜券第二版应该增加了不少这方面的论证。另外楼主对于本群中＂另类华容道＂的帖子里所列举的例子能否做一个类型归类和一般定义？

sokoban

我主要搞图论。可空多个点的滑块问题相对来说应该更容易一些，刚把你提到的论文下载了，很有趣，要仔细看看。你说的更一般的旋转谜题很值得思考，我也没有看过这方面的结果。

[ 本帖最后由 sokoban 于 2011-10-12 18:36 编辑 ]

poe

把业余爱好转化成论文，赞一个。不知你什么专业的？我是搞Percolation理论的，属于概率的一个分支。任意连通图上推广的滑块谜题(可空多个点)已基本解决，见Daniel Kornhauser, GaryMiller, and Paul Spirakis.   Coordinating pebble motion    on graphs, the diameter of permutation groups, and applications。然而Scherphuis定理的条件稍微窄了点，因为有很多旋转谜题不存在两个旋转圈使其交恰为一条路，不知道这方面有进展否？

[ 本帖最后由 poe 于 2011-10-12 00:53 编辑 ]

Cielo

来学习一下！