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 获得许可的。