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

Re: [問題] 重排時鐘

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者 (水牛比爾)時間4年前 (2020/09/23 11:13), 編輯推噓3(3推 0噓 4→)
留言7則, 3人參與, 4年前最新討論串2/2 (看更多)
推
09/23 00:51,
大概是 Hamiltonian path
09/23 00:51
→
09/23 00:52,
不對 要 cycle XD
09/23 00:52
推
09/23 10:43,
意外地只有一組解 https://imgur.com/JJtsqqK.png
09/23 10:43
→
09/23 10:44,
先砍掉 12 和 6，目標變成從 {5, 7} 到 {1, 11} 找
09/23 10:44
→
09/23 10:44,
兩條 disjoint 的 paths
09/23 10:44
→
09/23 10:46,
再砍 1, 5, 7, 11 發現就只剩兩條可能的
09/23 10:46
→
09/23 10:46,
[2, 9, 4] 和 [8, 3, 10]
09/23 10:46
推
09/23 10:48,
咦，是四組XD
09/23 10:48
→
09/23 10:50,
2, 4, 8, 10 都能各自接 1, 5, 7, 11
09/23 10:50
→
09/23 10:54,
除了四個 [i, i+1] 的以外
09/23 10:54
→
09/23 11:00,
還有 [5, 10]
09/23 11:00
答案就是4，令人意外的少 https://i.imgur.com/tXiFzjQ.png
也許有人一看到12個數字排列 就以為要計算12!種情形，然後打開了IDE準備寫程式... nononono這題其實稍微推理一下就可以將數字大幅刪減： ．因互質故所有偶數不得相鄰，六奇六偶一定會排成奇偶奇偶.... ．12旁邊只能放7跟5，同理6旁邊只能放1跟11 ．承上可推理出3旁邊只能放8跟10，9旁邊只能放2跟4 整個時鐘就變成(7,12,5)(8,3,10)(1,6,11)(2,9,4)四個區塊 每個區塊只有兩種變化，只需計算16種情形 附帶一提，如果時鐘沒有12，只有1~11的話 那答案數量會爆增，有35個： https://i.imgur.com/L75ZAmR.png
然後1~10的話會無解 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.251.148.94 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1600830826.A.7D0.html
推
09/23 11:17, 4年前 , 1F
奇偶性有想到，可是沒細究下去XD
09/23 11:17, 1F
→
09/23 11:18, 4年前 , 2F
翻轉對稱可以讓可能性先再減半
09/23 11:18, 2F
→
09/23 11:19, 4年前 , 3F
翻轉可以固定(7,12,5)或是固定不讓3區塊與9區堆互換
09/23 11:19, 3F
→
09/23 11:20, 4年前 , 4F
我的算法是固定區塊，12->3->6->9這樣排除翻轉的
09/23 11:20, 4F
推
09/23 11:23, 4年前 , 5F
哦哦，16 種就排除過翻轉對稱了
09/23 11:23, 5F
推
09/23 21:27, 4年前 , 6F
真有趣的題目 幾乎是Puzzleup等級了
09/23 21:27, 6F
→
09/24 11:58, 4年前 , 7F
感謝樓上的鼓勵，不過我又沒梗了qq
09/24 11:58, 7F
‣ 更多 buffalobill 的文章
文章代碼(AID): #1VQhrgVG (puzzle)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共2篇)
puzzle 近期熱門文章
更多 近期熱門文章 >>
PTT遊戲區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 buffalobill 的文章
文章代碼(AID): #1VQhrgVG (puzzle)