誰是內奸？ - 拼圖

總之頁首防雷























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

--