2018年6月7日 星期四

4rdp 四格益智拼圖的排列記錄

http://4rdp.blogspot.com/2018/06/4rdp.html


4rdp 是一款可以任意拼圖的遊戲,因為花樣極多,它是圖論與組合數學的綜合難題,所以目前為止還沒有人可以清楚點出到底有多少種排列組合方式?這猶如面對一座礦山,知道裡面有豐富的寶藏,大家開始挖掘礦產 (排列花樣),因此成立一個 FB 社團 ─ 4rdp 益智拼圖,只要排出花樣就拍照上傳到 FB 記錄下來,就可以證明某某人找到某個花式圖案。

不過問題來了,雖然拍照上傳不困難,可是要比對圖案將會是一件越來越艱難的事,因為未來圖案會越來越多的,所以在此提出一個解決方案,就是需要建置一個系統資料庫,這件事是我的小朋友提醒我的,參考 OEIS 作法,要有系統記錄誰在何時發現甚麼花樣,這樣一來大家都有機會留下各種記錄。

首先需要編碼系統,能夠一眼立即辨識這是排列什麼圖案,以上圖為例,
一維編碼方法
它的編碼為 (12x12), J2S0Z1L1S0S0, Z1J0, O0Z1S0S0, J1, T0Z1T0T1, L2T0T3, L0I0Z0I0T2, J2, L0O0I0O0I0, L0J1, O0O0, I1,(12x12) 為 12 直行 (Columns) x 12 橫列 (Rows),從第一列開始,由左而右依序寫下圖塊形狀以及旋轉的情形,形狀有七種 IJLOSTZ,旋轉一律順時針方向轉,0 表示不旋轉,1 為右轉 90°,2 右轉 180°,3 右轉 270°,每排一列完成就以逗號分隔,這樣別人可以依照記錄的編碼正確複製你的圖案,以及核對圖案是否重複。

二維編碼方法
雖然一維編碼方便比對花樣是否重複,可是對 AI 不利於思考拼圖擺置,另外,在對奕時,用一維編碼也看不出圖塊擺置的先後次序,這時需要二維編碼的輔助,它的編碼為 (12x12), a1J2, b1S0, d1Z1, f1L1, h1S0, j1S0, f2Z1, k2J0, b3O0, d3Z1, g3S0, i3S0, a4J1, e5T0, g5Z1, i5T0, k5T1, a6L2, c6T0, i6T3, a7L0, c7I0, e7Z0, h7I0, j7T2, d8J2, e9L0, f9O0, i9I0, j9O0, l9I0, a10L0, b10J1, g11O0, j11O0, c12I1,假設圖塊放置也依序由左而右,由上而下,拼盤原點座標取左上方,橫坐標從左到右為 a 到 l ,縱座標從上而下為 1 到 12,圖塊表示方式同一維編碼,取圖塊左上角位置(即使是虛位也一樣,參考下圖圖例藍點) 與拼盤座標相對應。(2018 6/10 更正,這樣更符合程式設計習慣)

這兩個編碼可以互相轉換,但是由二維轉換成一維,排放次序將會喪失。


未來不排除群眾募資成立 4rdp 四格拼圖基金會之類組織舉辦比賽,並像 Wiki 或 OEIS 之類網站建立圖案資料庫,成為國際性組織,可以提供資料給各方研究者進一步研究,這件事可以由台灣成為領先者。

延伸閱讀,
想知道什麼是 OEIS ,請看 OEIS A274119 數列的故事 (2003倍數)

2 則留言:

  1. 遲遲沒收到,看大家拼我心裏癢癢~~
    哈哈
    另想確認一下地址。

    回覆刪除
    回覆
    1. 老師您應該收到了,希望有空時,填一下問卷 4rdp 四格益智拼圖意見回饋,謝謝。

      刪除