創作內容

3 GP

【作品】8-puzzle solver web版

作者:♙♲⚙\~O_O~/⚙♲♙│2018-02-18 04:54:05│巴幣:6│人氣:3483
這是一個 8-puzzle 的最少移動解製造機。已於2021-05-24 01:04更新成BFS的部分使用wasm(web assembly)的版本,若瀏覽器不支援wasm,則仍會使用純js(javascript)版本(較慢)。
全前端計算,可將html存起來,在沒網路的環境下使用。
(若要使用wasm版則還需另存puz8.wasm並至於同一個資料夾中,並另外簡單地開個網頁伺服器。)
使用bfs全搜尋後的結果全部記在記憶體裡,只有第一次找解答會覺得慢。
網址:https://aaaaagold.github.io/miscellanea/html/mn-puzzle.html
截圖[圖1]:

    圖1. 網頁截圖 : cache 所有空格解後的記憶體使用量 (使用純js)

使用說明:
把初始狀態填到左邊的initial state的格子中,然後按下"solve it"。
底下的 u/r/d/l 分別代表 上/右/下/左,表示將空格處 上/右/下/左 的格子移動到空格處。
以圖1為例:第一步為l, 即移動"6",使狀態變成

  1    2    3
  5  (空)  6
  4    7    8
或是直接想成空格要怎麼跑。

演算法:
直接用BFS(Breadth-First Search)暴力法。

資源消耗:
計算全前端,會cache最佳解答案(們),以goal state的空格在哪裡分類(計算時會將數字重新mapping),自己實測所有空格位置都cache(4個類別,以水平、鉛直鏡射方式減少種類)約需72.4MB[圖1]。
使用wasm的情形請見下圖[圖2]:

    圖2. 網頁截圖2 : cache 所有空格解後的記憶體使用量 (BFS的部分使用wasm)
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=3892562
Some rights reserved. 姓名標示-非商業性 2.5 台灣

相關創作

同標籤作品搜尋:solver|8-puzzle|wasm

留言共 5 篇留言

有月月
謝謝 這真是太好用了

05-24 10:54

♙♲⚙\~O_O~/⚙♲♙
耶[e12]
雖然我很好奇到底是用在哪裡05-24 12:55
有月月
最近未定事件簿有個拼圖活動 每天都要解 苦惱死一堆姊妹 發現有人轉貼這篇驚覺神物

05-24 13:03

♙♲⚙\~O_O~/⚙♲♙
原來如此05-24 13:06

未定的玩家過來朝聖(?)
但是我看不懂 [e3]

05-25 02:39

♙♲⚙\~O_O~/⚙♲♙
沒關係,我也不懂怎麼會有人有辦法找到這個並轉貼(?)05-25 03:03
jpxft
未定玩家朝聖!
謝謝大神
解救了我!!!

05-25 18:10

♙♲⚙\~O_O~/⚙♲♙
不客氣[e12]05-26 02:57
Ren
想問一下此程式是用java寫的麼
版主有沒有源碼呢

06-15 21:45

♙♲⚙\~O_O~/⚙♲♙
主體是用javascript(+html,+css)寫的
web assembly的部分是用C++寫,再自行編譯的

所以原始碼的部分按鍵盤F12就對了,寫完就長那樣,沒有做模糊化
C++的部分,雖然沒有辦法從F12中看出來,但多少猜的到網址
https://aaaaagold.github.io/miscellanea/html/puz8.cpp
就算猜不到網址,看到github.io大概也知道去哪裡找
https://duckduckgo.com/?q=github.io&ia=web

其實我不寫java06-15 23:38
我要留言提醒:您尚未登入,請先登入再留言

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

前一篇:【作品】file to ... 後一篇:【未完成】【筆記】3種殺...

追蹤私訊切換新版閱覽

作品資料夾

tfapp大家
小屋內容新增,歡迎大家到我的小屋,免費以及輕鬆愉快學日文看更多我要大聲說昨天22:11


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

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