緣起
學生時期，家中一直有一個智慧拼盤(似圖1, 參1)，不清楚來源，可能是買奶粉送的吧？偶爾會拿來玩玩。大學時，有一次老師剛好出了一題”求解智慧盤”(圖2)的作業，於是就花了時間研究它的解法；當年的電子檔已不存在，只剩列印的文件。2000年左右，小孩在玩立體拼盤(3D Pentominos)(如圖3)， 但卻沒人能拼回(太難了吧，只能當積木玩)，於是利用離職前兩個星期，重新改寫此一程式並支援三維，才把借來的立體拼盤給拼回去！
|
|
| 智慧拼盤 (圖1) |
求解智慧盤-列印封面 (圖2) |
|
3D Pentominos (圖3)
|
拼盤的玩法
拼盤中不同形狀的塊體稱為多方塊(Polyomino)，是由多個方塊組成，不同個數的組合，又有不同名稱如俄羅斯方塊是由4個方塊組成稱
Tetromino，而5個方塊組成稱為Pentomino(參2)。拼盤的玩法非常簡單，就是將多方塊完全放入拼盤中即完成；通常只要多點耐心，多試幾次就可以完成，與智慧無關吧，智慧二字應該只是商人的噱頭。
拼盤與程式
拼盤的程式解法，是使用回溯法(Backtracking)即試錯(Trial and error)的方式來解出答案的，關於回溯法請參考另一篇文章：回溯法；這裡主要說明多方塊如何擺放的過程。
(1) 經由旋轉(rotate)及反轉(flip)產生所有可擺放的多方塊形狀。
一個多方塊最多有八種可擺放的形狀，例：
多方塊經 6次順時針90度及 1次左右反轉，最多產生 8種不同形狀。
(2) 試著將多方塊先左而右，再由上而下的放入拼盤內，如下圖：
因左而右再上而下，所以將多方塊的最左上(先取最上再取最左)坐標設為(0,0)，並經由順時90度及左右反轉找出所有的形狀：
(2.1) 多方塊順時90度：
(2.1.1) 坐標順時90度： (X, Y) ==> (-Y, X)
(2.1.2) 排序：依先比Ｙ再比Ｘ的方式排序。
(2.1.3) 將排序後最小值轉移至(0,0),即為所求。
範例說明：
(2.2) 多方塊左右反轉：
(2.2.1) 坐標左右反轉: (X, Y) ==> (-X, Y)
(2.2.2) 排序：依先比Ｙ再比Ｘ的方式排序。
(2.2.3) 將排序後最小值轉移至(0,0),即為所求。
範例說明：
|
(3) 擺入一多方塊後，依由左而右由上而下的找下個可擺放的位置，若同一多方塊的所有形狀均無法擺入，就取下一個未擺放的放入，
若全部未擺放的多方塊均無法放入目前的位置，就取出上一個已放入的換成另一塊來放，直到所有多方塊均放完或已擺滿拼盤，
則為一組解，反覆上述動作直到求得所有解或所欲求解的個數。( 參3)
JavaScript:
另外 2000年時，C 語言所寫：matrix.zip (僅供參考, include 3D version, compile using gcc with cygwin)
在學生作業列印文件中，有一段內容記載著當時求解的時間，如下圖：
當時是以Ｃ語言完成，在 286-10@10MHz 的機器要10小時以上，在386-33@56MHz 的機器也要 2小時以上，
這應該有含顯示到螢幕的時間，而目前使用 Intel Core2 Duo P8700 @ 2.53GHz 在 Chrome (版本 25.0.1364.172 m) 上執行
Tetromino
全解(JavaScript)，只要10秒 (Total answers = 99392, Elapsed Time : 10.418s,
不含顯示時間 )。
智慧拼盤遊戲
智慧拼盤的遊戲是用 JavaScript 寫成，動態動作是以 KineticJS javascript framework 完成，遊戲中的每道題目，提示按鈕 及 即時檢查
均是由求解函式所完成，程式可於 Chrome, FireFox , IE9 下執行，但有用到 HTML5 的 localStorage 只有 Chrome 可正常運作。
程式原始碼
GitHub: https://github.com/SimonHung/Polyomino-Puzzle
Simon's GitHub Projects: https://simonhung.github.io
參考資料
(1) 魔術拼盤: http://blog.udn.com/puzzlez/3495793
(2) Polyomino wiki: http://en.wikipedia.org/wiki/Polyomino
(3) Pentominos Puzzle Solver: http://godel.hws.edu/java/pent1.html
|
