[其他] 拼圖遊戲

[HanayoK (小泉花陽の配偶)]

有一種拼圖遊戲是這樣
不知道正確名稱是甚麼
比如
123
56
478

要拼到完整的結果 6右移 5右移 4上移 7左移 8左移
就到了結果
123
456
78

那如果亂移 一共會出現幾種畫面
比如 123 是一種畫面    那 123 也是一種畫面
     456                  56
     78                   478
直覺是9!=1*2*3*...*9這麼多種可能性。


但是實際上 是不是要除以2
因為移動格子的時後會發現  某些畫面是無法到結果的
比如
123
456
78   作為結尾的話
就不可能出現 123
             456
             87 這個畫面  因為這個畫面無法到那個結尾

先用4個想
12
3

4!=24
實際上只出現
12 1   1 31 31 3   3 23 23 2   2 12
3  32 32  2 2  21 21  1 1  13 13  3
12種畫面

自問自答好像真的是除以2  不過道理在哪裡啊..還有這個應該叫甚麼遊戲@@

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.25.30.212
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1397356056.A.F42.html
※ 編輯: HanayoK (114.25.30.212), 04/13/2014 10:28:31
推 knowbee     :就叫作N-puzzle 9格的就叫8-puzzle
→ knowbee     :考慮盤面的逆序值，就是目前盤面上有多少pair (i,j)
→ knowbee     :是j比i小，但是j卻在i後面的
→ knowbee     :你可以發現，盤面可以分成逆序值是奇數的奇盤面
→ knowbee     :跟逆序值是偶數的偶盤面，兩個是無法互相轉變的
→ knowbee     :稍微思考一下就會發現移動不改變奇偶性
推 knowbee     :啊="=抱歉 還要把逆序值加上空格在第幾row的值才對