Re: [問題] 誰是內奸？

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者LPH66 (-6.2598534e+18f)時間10年前 (2015/11/06 22:45)推噓3(3推 0噓 1→)

留言4則, 2人參與討論串2/2 (看更多)

總之頁首防雷 3x3 的魔方陣眾所周知就只有那個可以旋轉翻轉的那一解不過這題是 0~8 的關係所以全部都要減 1 全部八種目標表列如下: ＡＢＣＤＥＦＧＨ３８１１６５５７７２３１８３３２７７５５６１２４６８４６４２４８６４２８４２４６４８７５３２７１８３５６１５７１６５３８１７２３跟原盤面一比可知只有 B D E F 四種目標存在至少一個數字留在原位易知 F 這個固定 2 的無解, 3 和 7 離不開他所在的位置同理 D 也不能固定 2 剩下的部份有兩個方法, 一個是拿盤子出來滑, 另一個是直接套奇偶性證明直接滑的話為方便思考可以倒過來從目標出發滑回一開始的配置注意不要動到固定數字即可直接滑盤面的結果可以發現 B 跟 D 都有解而 E 會得到一個奇偶性相反的狀況所以無解如果要直接用奇偶性證明的話先各移一格使空格在中間, 然後列出排列及其逆序數: B: 16584327 逆序數: 65 64 63 62 54 53 52 84 83 82 87 43 42 32 計 14 個 D: 72348561 逆序數: 72 73 74 75 76 71 21 31 41 85 86 81 51 61 計 14 個 E: 18362547 逆序數: 83 86 82 85 84 87 32 62 65 64 54 計 11 個原始盤面 12345678 的逆序數是 0 是偶數, 所以 B 和 D 都有解, E 無解 (其實個人覺得兩個方法相輔相成, 無解用奇偶性證明, 有解就直接滑出一個走法就是解了) 因此最後的盤面就是 B 或 D 兩種狀況, 其內奸分別為 1 或 3 最後，以下是程式跑出來的 B / D 盤面的最短步數之其中一解: B: 內奸 1, 手順: 7647 5325 683256 748327 48327 計 25 步１２３１２３１５２１６５１６５１６５４５→７５→７３→７２→４７→８４６７８４６８４６８４８３８３２３２７ D: 內奸 3, 手順: 4124 1671 5815 6 756427 計 19 步１２３２４３２４３２４３２４３７２３４５→１５→６５→６８→ ６８→ ４８６７８６７８７１８７５１７５１５６１有巨人的肩膀可以站真是方便的頁末防雷頁 -- 'You've sort of made up for it tonight,' said Harry. 'Getting the sword. Finishing the Horcrux. Saving my life.' 'That makes me sound a lot cooler then I was,' Ron mumbled. 'Stuff like that always sounds cooler then it really was,' said Harry. 'I've been trying to tell you that for years.' -- Harry Potter and the Deathly Hollows, P.308 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.39.85 ※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1446821103.A.74C.html