PTT遊戲區 / puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)

[中譯] Puzzleup 2016 (18) Chess Codes

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者 (アルターエゴ)時間8年前 (2016/11/23 21:26), 編輯推噓12(12推 0噓 37→)
留言49則, 6人參與, 最新討論串1/1
題目網址: 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
→
11/24 09:01, , 1F
好難，2x2的話是四步，4x4的話……
11/24 09:01, 1F
推
11/24 12:43, , 2F
難+1
11/24 12:43, 2F
推
11/24 18:52, , 3F
如果去掉交換時的限制:格子顏色不同才能交換
11/24 18:52, 3F
→
11/24 18:58, , 4F
好像最多是64?
11/24 18:58, 4F
→
11/24 19:22, , 5F
應該是63
11/24 19:22, 5F
→
11/24 19:39, , 6F
因為任意排列皆可表示為cycle notation
11/24 19:39, 6F
→
11/24 19:42, , 7F
每交換一次cycle上相鄰的兩點, cycle就會少一條邊
11/24 19:42, 7F
→
11/24 19:43, , 8F
直到cycle長度剩下2時, 交換後cycle就消失了
11/24 19:43, 8F
推
11/24 22:52, , 9F
嘛...每種狀態當成一個點 能換到的表示兩點有連
11/24 22:52, 9F
→
11/24 22:52, , 10F
那就剩ProgramUp了吧
11/24 22:52, 10F
推
11/24 23:52, , 11F
11/24 23:52, 11F
→
11/24 23:52, , 12F
NP-hard
11/24 23:52, 12F
→
11/24 23:54, , 13F
11/24 23:54, 13F
→
11/24 23:54, , 14F
Google花了35 CPU-years才算出魔術方塊的God's Number
11/24 23:54, 14F
推
11/25 00:11, , 15F
把狀態當點...這題的點與degree的數量級都超過魔術方塊
11/25 00:11, 15F
→
11/25 00:14, , 16F
把8x8的棋盤格子放成1x64不會影響答案
11/25 00:14, 16F
→
11/25 00:14, , 17F
那從1x2, 1x4, 1x6,...算起，也許可以找到規律
11/25 00:14, 17F
推
11/25 11:39, , 18F
有種陷於五里霧中的fu
11/25 11:39, 18F
→
11/25 11:41, , 19F
把原本在a1等黑格的記號A1想成黑球，最糟糕的狀況是
11/25 11:41, 19F
→
11/25 11:42, , 20F
所有黑球位在黑格，所有白球位在白格，但全是錯排
11/25 11:42, 20F
→
11/25 11:43, , 21F
所以格子的空間排列不重要，可以從黑格與黑球的錯排和
11/25 11:43, 21F
→
11/25 11:44, , 22F
白格與白球的錯排開始想，變成研究移動次數與一開始
11/25 11:44, 22F
→
11/25 11:45, , 23F
置換群長怎樣之間的關係...尋找手筋中...
11/25 11:45, 23F
推
11/25 12:51, , 24F
以下提供一種方法,但我無發證明是最快的方法
11/25 12:51, 24F
→
11/25 12:51, , 25F
因為任意排列皆可表示為cycle notation,所以
11/25 12:51, 25F
→
11/25 12:51, , 26F
把64顆不同的球,從球拉出箭頭,指向它原本的位置
11/25 12:51, 26F
→
11/25 12:52, , 27F
這些箭頭必定形成一個環或多個環.
11/25 12:52, 27F
→
11/25 12:52, , 28F
若環上存在相鄰的格子異色,則可以交換格子上的球
11/25 12:52, 28F
→
11/25 12:52, , 29F
使得環的長度變短,直到環消失
11/25 12:52, 29F
→
11/25 12:52, , 30F
例如: b1->b2->w3->b4->b5->b1 (b:黑格, w:白格)
11/25 12:52, 30F
→
11/25 12:53, , 31F
須交換b2與w3格子上的球, 新環就變成:
11/25 12:53, 31F
→
11/25 12:53, , 32F
b1->w3->b4->b5->b1
11/25 12:53, 32F
推
11/25 12:57, , 33F
若整個環都是同色的格子,要使環消失
11/25 12:57, 33F
→
11/25 12:57, , 34F
須先與一個異色的格子交換球,讓環變成非同色環
11/25 12:57, 34F
→
11/25 12:57, , 35F
才能開始消去環.
11/25 12:57, 35F
→
11/25 12:57, , 36F
但這會多一步驟並且使環的長度增加
11/25 12:57, 36F
→
11/25 12:57, , 37F
所以我猜最壞的狀況是:
11/25 12:57, 37F
→
11/25 12:57, , 38F
所有的環都是同色環,越多越好
11/25 12:57, 38F
→
11/25 12:58, , 39F
環的數量越多越好,不是環的長度
11/25 12:58, 39F
推
11/25 13:23, , 40F
例子錯了，應改成
11/25 13:23, 40F
→
11/25 13:23, , 41F
交換w3與b4格子上的球, 新環就變成:
11/25 13:23, 41F
→
11/25 13:23, , 42F
b1->b2->w3->b5->b1
11/25 13:23, 42F
推
11/25 15:09, , 43F
哈，任意n元黑環和m元白環都可以在n+m次內歸位，證完
11/25 15:09, 43F
→
11/25 15:10, , 44F
感謝提示，你的記號直覺好用
11/25 15:10, 44F
推
11/25 15:49, , 45F
好強的兩位！
11/25 15:49, 45F
推
11/26 04:21, , 46F
11/26 04:21, 46F
→
11/26 04:22, , 47F
他的記號在哪裡@@ 格子上的a1什麼的位置不都正確嗎
11/26 04:22, 47F
→
11/26 04:22, , 48F
看不懂要移動什麼@@
11/26 04:22, 48F
→
11/26 04:23, , 49F
噢我少看隨機了 當我沒問 抱歉><"
11/26 04:23, 49F
‣ 更多 LPH66 的文章
文章代碼(AID): #1ODPZe1v (puzzle)
puzzle 近期熱門文章
更多 近期熱門文章 >>
PTT遊戲區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 LPH66 的文章
文章代碼(AID): #1ODPZe1v (puzzle)