這個真的太猛了==
發個文記一下網址 順便分享
雖然平常自己拚戰地拼圖也是沒什問題
不過竟然有人能寫出 解拼圖這種NP hard的問題
只能跪著看了
作者還把他寫程式的心路歷程寫出來
滿有趣的 稍微翻一下
一開始作者先試著用暴力法跑自己的戰地
結果意外發現解得很快
所以就花了一些時間把整個UI模板都做出來
寫完後發現當初的暴力法只是自己比較賽
套用到某些人的戰地上會花到好幾分鐘甚至更久
所以作者在原本的暴力法上加一些限制
從周圍有最多拼圖的區域開始找起
ie. constrained variable algorithm
但是做到這邊還是有一些小問題
因為大部分人的拼圖都是中間有一條橫線
會導致中間的拼圖放完之後
兩邊的數量可能拼不起來但程式還是繼續去解
最後作者意外的發現
有些要找很久的問題上
只要把整個拼圖板做旋轉
程式就會突然很迅速地找到解
所以可以利用這個方法
旋轉找到解後再unrotate
最後的最終版就出來了
一開始會將原本的拼圖板轉成三種樣子
分別去跑brute force algorithm +constrained variable algorithm
就可以很快速地找到解
超神的程式背後的小小故事