[中譯] Puzzleup 2016 (18) Chess Codes

[LPH66 (アルターエゴ)]

題目網址: 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 )

--
 ◢ ˊ_▂▃▄▂_ˋ. ◣　　　　　 　　　　▅▅　▅▅　ι●╮　　 █▄▄▄▄▄   
▍./◤_▂▃▄▂_◥ \'▊ 　　ＨＡＲＵＨＩ █████　＜■┘  　 ▄▄▄▄▄▄▄ 
▎⊿ ◤◤◥█◥◥█Δ   　　ＩＳＭ　 　　By-gamejye　￠|\  　　▌▌▌▌▌▄▌▌
▏ζ(▏●‵◥′●▊)Ψ ▏　　 　　　 　　　　█　　　 ⊿Δ 　　▄▄▄  ▄▄▄▄
█/|▊ 〃  、  〃▋ |\ ▎　　　　　 　 　ハルヒ主義　　　  　　█▄▄▄█▄▄  
◥◥|◣   ‵′  ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団　　　 

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.29.238
※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1479907560.A.079.html
→ buffalobill: 好難，2x2的話是四步，4x4的話……
推 cutekid: 難+1
推 prime2477: 如果去掉交換時的限制:格子顏色不同才能交換
→ prime2477: 好像最多是64?
→ prime2477: 應該是63
→ prime2477: 因為任意排列皆可表示為cycle notation
→ prime2477: 每交換一次cycle上相鄰的兩點, cycle就會少一條邊
→ prime2477: 直到cycle長度剩下2時, 交換後cycle就消失了
推 walkwall: 嘛...每種狀態當成一個點  能換到的表示兩點有連
→ walkwall: 那就剩ProgramUp了吧
推 prime2477: https://en.wikipedia.org/wiki/God's_algorithm
→ prime2477: NP-hard
→ prime2477: http://www.cube20.org/
→ prime2477: Google花了35 CPU-years才算出魔術方塊的God's Number
推 prime2477: 把狀態當點...這題的點與degree的數量級都超過魔術方塊
→ prime2477: 把8x8的棋盤格子放成1x64不會影響答案
→ prime2477: 那從1x2, 1x4, 1x6,...算起，也許可以找到規律
推 jurian0101: 有種陷於五里霧中的fu
→ jurian0101: 把原本在a1等黑格的記號A1想成黑球，最糟糕的狀況是
→ jurian0101: 所有黑球位在黑格，所有白球位在白格，但全是錯排
→ jurian0101: 所以格子的空間排列不重要，可以從黑格與黑球的錯排和
→ jurian0101: 白格與白球的錯排開始想，變成研究移動次數與一開始
→ jurian0101: 置換群長怎樣之間的關係...尋找手筋中...
推 prime2477: 以下提供一種方法,但我無發證明是最快的方法
→ prime2477: 因為任意排列皆可表示為cycle notation,所以
→ prime2477: 把64顆不同的球,從球拉出箭頭,指向它原本的位置
→ prime2477: 這些箭頭必定形成一個環或多個環.
→ prime2477: 若環上存在相鄰的格子異色,則可以交換格子上的球
→ prime2477: 使得環的長度變短,直到環消失
→ prime2477: 例如: b1->b2->w3->b4->b5->b1 (b:黑格, w:白格)
→ prime2477: 須交換b2與w3格子上的球, 新環就變成:
→ prime2477: b1->w3->b4->b5->b1
推 prime2477: 若整個環都是同色的格子,要使環消失
→ prime2477: 須先與一個異色的格子交換球,讓環變成非同色環
→ prime2477: 才能開始消去環.
→ prime2477: 但這會多一步驟並且使環的長度增加
→ prime2477: 所以我猜最壞的狀況是:
→ prime2477: 所有的環都是同色環,越多越好
→ prime2477: 環的數量越多越好,不是環的長度
推 prime2477: 例子錯了，應改成
→ prime2477: 交換w3與b4格子上的球, 新環就變成:
→ prime2477: b1->b2->w3->b5->b1
推 jurian0101: 哈，任意n元黑環和m元白環都可以在n+m次內歸位，證完
→ jurian0101: 感謝提示，你的記號直覺好用
推 cutekid: 好強的兩位！
推 eowynknight:  http://i.imgur.com/xYrlhGp.jpg
→ eowynknight: 他的記號在哪裡@@ 格子上的a1什麼的位置不都正確嗎
→ eowynknight: 看不懂要移動什麼@@
→ eowynknight: 噢我少看隨機了 當我沒問 抱歉><"