3co搜庫

IcoSoKu 的MiniZinc 和答案集編程求解器及其強NP 完全泛化3coSoKu（請參閱此處和此處有關它的論文），由使用Three.js 和clingo-wasm 構建的IcoSoKu 3D 可視化/求解器工具完成，您可以現在在線嘗試。該儲存庫還包含一些對求解器進行基準測試並驗證 IcoSoKu 的每個實例確實可以求解的腳本（請參閱實驗結果）。

IcoSoKu圖片

問題

IcoSoKu 是 Andrea Mainini 於 2009 年創建的機械拼圖，其工作原理如下：

遊戲的設定是將 12 個黃色釘子（數字 1 到 12）任意放置在頂點上；
遊戲的玩法是找到遊戲中附帶的 20 個三角形方塊在二十面體表面上的排列方式，使得每個頂點周圍的黑點數量等於其黃色釘子的數量。

20 個圖塊如下圖所示。

IcoSoKu 的圖塊配置。

3coSoKu是 IcoSoKu 的泛化，其中每個實例定義如下：

比賽場地，一個帶有三角形面的多面體（二十面體，對於 IcoSoKu）；
每個頂點的容量，一個非負整數（黃色釘子的配置）；
tiles ，由三個非負整數權重組成（帶有有點的tiles）。

為了忠於 IcoSoKu，我們強製磁磚數量等於面數。 3coSoKu 是強 NP 完全的，你可以閱讀我和烏迪內大學教授 Agostino Dovier 撰寫的論文中的所有細節。

入門

要查看 IcoSoKu 實例並使用 ASP 求解器求解它們，您可以嘗試使用 Web 應用程式：無需安裝，這要歸功於 Three.js 和編譯為 WebAssembly 的 clingo。

否則，如果您想測試求解器，請安裝 MiniZinc 和/或 clingo，然後下載此儲存庫。

$ git clone https://github.com/nrizzo/3coSoKu.git
$ cd 3coSoKu

命名二十面體的頂點

在solvers/MiniZinc和solvers/ASP中找到的求解器已配置為求解IcoSoKu 的實例。在 Linux/Unix 系統上，您可以使用兩個資料夾中的腳本icosolve.sh ：該腳本接受指定黃色釘子的十二個容量作為輸入，遵循右圖的約定（按字母順序排列）。

$ cd solvers/MiniZinc
$ ./icosolve.sh 1 2 3 4 5 6 7 8 9 10 11 12

或者，您可以分別修改檔案input-ico.dzn中的陣列cap和input-ico.lp中的事實cap(V,C) ，也遵循右圖的約定，並手動執行求解器：

$ minizinc --solver chuffed 3coSoKu.mzn input-ico.dzn

對於 MiniZinc（您也可以使用 IDE），以及

$ clingo 3coSoKu.lp variants/ico.lp input-ico.lp

對於 ASP。

實驗結果

資料夾tests包含用於執行一些有趣測試的 Bash 腳本，這些測試也在論文中進行了描述。詳細資訊和結果在此描述。特別是：由於遊戲的對稱性，解算器可以求解每個 IcoSoKu 實例；每個 IcoSoKu 實例都有數十億種不同的解決方案，因此遊戲的一個良好的現實策略是頻繁地重新啟動並嘗試「幸運」。

3D視覺化工具

我們使用three.js 、 Tweakpane和stats.js開發了一個可視化 IcoSoKu 實例及其解決方案的 3D 應用程式。此外，由於 clingo 編譯為 WebAssembly 和我們的 ASP 編碼，應用程式使用clingo-wasm來實際解決（在瀏覽器中！）使用者指定的 IcoSoKu 實例。

您可以在此處使用任何現代瀏覽器嘗試該 Web 應用程序，也可以透過兩種方式在本地啟動它：

您可以使用任何 HTTP 伺服器在本機網路上託管webapp/http資料夾；
```
  $ cd webapp/http
  $ python3 -m http.server &
  $ firefox localhost:8000
```
您可以透過開啟主 html 檔案來執行webapp/offline中找到的應用程式的離線版本，而無需進行任何託管。
```
  $ firefox webapp/offline/index.html
```

webapp/offline中的離線版本不會觸發瀏覽器的 CORS 規則，它是透過一些技巧獲得的，其中使用empscripten的 options -s WASM=0 --memory-init-file 0將clingo 編譯為JavaScript 而不是WebAssembly (導致 cligo 性能較差）。

執照

我的所有程式碼（求解器、腳本和 webapp）均根據 GNU GPL v3 許可證條款獲得許可，而我正在使用的軟體和資產（位於webapp/{http,offline}/vendor和webapp/{http,offline}/assets ），即 Clingo WebAssembly、 Three.js、Tweakpane 和 stats.js，保留其原始許可證。我的圖像（在images資料夾中）是根據 CC BY 獲得許可的。