题目网址: http://www.puzzleup.com/2016/
http://www.puzzleup.com/2016/puzzle/?18
答题时限: 11月24日７ＰＭ－比赛结束（约12月14日）
加分时限: 11月24日７ＰＭ－11月30日６：５９ＰＭ
答对可得基本分１００分。答案可上传５次，每改１次答案从基本分扣２０分。　
比赛期间内可随时上传答案，加分时限内答对第ｎ天加（６－ｎ）分　 　　 　　
另依题目的难易有额外加分（如有８０％的人这题答错，答对者加８０分）　　
◆CHESS CODES
Sixty four chess notation codes from a1 to h8 are placed randomly on each
square of a standard 8x8 chessboard. Your task is to put the codes in the
correct order as given in the diagram. In each step you can take one code
from a white square and one code from a black square and exchange them.
What is the minimum number of steps that is sufficient to obtain the correct
order from all possible initial positions?
六十四个西洋棋代数记号由 a1 至 h8 随机放置在一个标准 8x8 的西洋棋盘上。
你的任务是将所有记号回归到正确的位置上。
每一步你能做的是将一个处在黑格的记号和一个处在白格的记号对调。
试问对所有盘面，多少步足以将所有记号回归？
(译注: 关于代数记号, 请参阅本版 #1A1TgpvR )

好难，2x2的话是四步，4x4的话……

难+1

如果去掉交换时的限制:格子颜色不同才能交换好像最多是64?应该是63因为任意排列皆可表示为cycle notation每交换一次cycle上相邻的两点, cycle就会少一条边直到cycle长度剩下2时, 交换后cycle就消失了

嘛...每种状态当成一个点 能换到的表示两点有连那就剩ProgramUp了吧

https://en.wikipedia.org/wiki/God's_algorithmNP-hardhttp://www.cube20.org/Google花了35 CPU-years才算出魔术方块的God's Number把状态当点...这题的点与degree的数量级都超过魔术方块把8x8的棋盘格子放成1x64不会影响答案那从1x2, 1x4, 1x6,...算起，也许可以找到规律

有种陷于五里雾中的fu把原本在a1等黑格的记号A1想成黑球，最糟糕的状况是所有黑球位在黑格，所有白球位在白格，但全是错排所以格子的空间排列不重要，可以从黑格与黑球的错排和白格与白球的错排开始想，变成研究移动次数与一开始置换群长怎样之间的关系...寻找手筋中...

以下提供一种方法,但我无发证明是最快的方法因为任意排列皆可表示为cycle notation,所以把64颗不同的球,从球拉出箭头,指向它原本的位置这些箭头必定形成一个环或多个环.若环上存在相邻的格子异色,则可以交换格子上的球使得环的长度变短,直到环消失例如: b1->b2->w3->b4->b5->b1 (b:黑格, w:白格)须交换b2与w3格子上的球, 新环就变成:b1->w3->b4->b5->b1若整个环都是同色的格子,要使环消失须先与一个异色的格子交换球,让环变成非同色环才能开始消去环.但这会多一步骤并且使环的长度增加所以我猜最坏的状况是:所有的环都是同色环,越多越好环的数量越多越好,不是环的长度例子错了，应改成交换w3与b4格子上的球, 新环就变成:b1->b2->w3->b5->b1

哈，任意n元黑环和m元白环都可以在n+m次内归位，证完感谢提示，你的记号直觉好用

好强的两位！

http://i.imgur.com/xYrlhGp.jpg他的记号在哪里@@ 格子上的a1什么的位置不都正确吗看不懂要移动什么@@噢我少看随机了 当我没问 抱歉><"