創作內容

5 GP

Legion Board Solver

作者:星星│2020-08-08 12:30:46│巴幣:10│人氣:391


來源 reddit

這個真的太猛了==
發個文記一下網址 順便分享

雖然平常自己拚戰地拼圖也是沒什問題
不過竟然有人能寫出 解拼圖這種NP hard的問題
只能跪著看了




作者還把他寫程式的心路歷程寫出來
滿有趣的 稍微翻一下

一開始作者先試著用暴力法跑自己的戰地
結果意外發現解得很快
所以就花了一些時間把整個UI模板都做出來

寫完後發現當初的暴力法只是自己比較賽
套用到某些人的戰地上會花到好幾分鐘甚至更久

所以作者在原本的暴力法上加一些限制
從周圍有最多拼圖的區域開始找起
ie. constrained variable algorithm

但是做到這邊還是有一些小問題
因為大部分人的拼圖都是中間有一條橫線
會導致中間的拼圖放完之後
兩邊的數量可能拼不起來但程式還是繼續去解

最後作者意外的發現
有些要找很久的問題上
只要把整個拼圖板做旋轉
程式就會突然很迅速地找到解
所以可以利用這個方法
旋轉找到解後再unrotate

最後的最終版就出來了
一開始會將原本的拼圖板轉成三種樣子
分別去跑brute force algorithm +constrained variable algorithm
就可以很快速地找到解


超神的程式背後的小小故事
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4875717
All rights reserved. 版權所有,保留一切權利

相關創作

留言共 3 篇留言

臨川望原
加油好嗎?[e17]

08-08 12:31

星星
[e42]08-08 12:56
小萊修
好想當大佬工程師

08-08 12:51

星星
想當邊看韓劇一邊coding工程師08-08 12:56

不明覺厲

08-15 00:38

我要留言提醒:您尚未登入,請先登入再留言

5喜歡★peggy7992 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:每日單人公會貢獻... 後一篇:19...

追蹤私訊切換新版閱覽

作品資料夾

sdgn大家
吾乃 惠惠教... 爆裂魔法大好看更多我要大聲說昨天19:34


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】