Скачать или смотреть 小時候拼不完的拼圖，長大後寫程式暴力破解！【玩俄羅斯拼圖】

==== 補充一些影片中沒說到的資訊 ====

「俄羅斯拼圖」應該不是這類拼圖的正式中文名稱，
在英文裡有一個正式的名稱是 polyomino tiling puzzle（可譯為：多連方平鋪謎題），
或者就簡稱為 polyomino puzzle。
https://en.wikipedia.org/wiki/Polyomi...

如同有些留言提到的，
解這類 puzzle 有一個非常高效的演算法：dancing links algorithm（又稱 algorithm X, DLX），
https://en.wikipedia.org/wiki/Dancing...
可惜在做這支影片時我還不知道有這個演算法，
當然也就沒能實作出來。

後來我理解了 DLX 並且用 Python 實作出來，
可以用單核 CPU 在 15 分鐘內找出全部 69415 個解，
已經比我影片中寫的版本還要快 5 倍以上（影片中的是單核 80 分鐘）。

後來在 Github 上找到別人用 C++ 實作的 DLX 程式碼，
https://github.com/jlaire/dlx-cpp
解這個拼圖可以用單核在 9.5 秒內找出全部 69415 個解，
等於比我影片中的版本快 500 倍，
實在是喪心病狂😂

另外也有人提到可以用 BurrTools 這個開源軟體來解，
我去找來用了（花了不少時間才終於學會），
它可以用單核在 1.2 分鐘內找出 69415 個答案，
也已經非常快了。
根據官方說明，它內部也是用 DLX 演算法。

以上實驗都是在 M1 MacBook 上測試的。

總之非常感謝各路大神留言告訴我這些我本來不知道的知識！

==== 以下是做這支影片的感想 ====

這支影片絕對是我目前為止花最多時間製作的影片，
從去年八月就開始製作，
程式就寫了好幾個版本，
也花了超多時間思考如何拍攝、如何呈現程式和演算法、哪些內容大眾會感興趣、哪些內容大眾可能不感興趣或看不懂，
也常常懷疑：「我花這麼多時間製作一支影片真的值得嗎？會不會做完沒人看？」
（結果影片發布後的前 10 個月真的沒什麼人看，觀看數不到 2000，後來才突然飆升到接近 10 萬）

總之在各種憂慮和拖延下，
我終於還是把這支影片做出來了，
這是我目前能力範圍內能做到的最好的版本了。

喜歡這支影片的話歡迎透過按讚、留言、超級感謝支持我！
也歡迎給我任何合理的批評、建議！

---

如果有人想要自己寫程式解解看的話，
可以在以下連結下載拼圖片的 JSON 格式資料。
https://gist.github.com/Roger-Wu/af47...

---

Video Chapters:
0:00 簡介
0:14 開箱
1:13 動手拼
3:30 開始寫程式暴力破解
4:18 第一個演算法
6:12 改良後的演算法
7:38 其他加速技巧
9:17 總共有多少種答案？
9:52 找出最好看的答案
10:45 感想

#puzzle #programming #algorithm #tetris #education #dfs #backtracking