[其他] 拼圖遊戲

看板Math作者 (小泉花陽の配偶)時間11年前 (2014/04/13 10:27), 11年前編輯推噓2(205)
留言7則, 1人參與, 最新討論串1/1
有一種拼圖遊戲是這樣 不知道正確名稱是甚麼 比如 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

04/13 10:43, , 1F
就叫作N-puzzle 9格的就叫8-puzzle
04/13 10:43, 1F

04/13 10:46, , 2F
考慮盤面的逆序值,就是目前盤面上有多少pair (i,j)
04/13 10:46, 2F

04/13 10:46, , 3F
是j比i小,但是j卻在i後面的
04/13 10:46, 3F

04/13 10:47, , 4F
你可以發現,盤面可以分成逆序值是奇數的奇盤面
04/13 10:47, 4F

04/13 10:47, , 5F
跟逆序值是偶數的偶盤面,兩個是無法互相轉變的
04/13 10:47, 5F

04/13 10:48, , 6F
稍微思考一下就會發現移動不改變奇偶性
04/13 10:48, 6F

04/13 10:58, , 7F
啊="=抱歉 還要把逆序值加上空格在第幾row的值才對
04/13 10:58, 7F
文章代碼(AID): #1JIVOOz2 (Math)