3coSoKu

MiniZinc および Answer Set IcoSoKu 用のプログラミングソルバーとその強力な NP 完全一般化 3coSoKu (これに関する論文はこちらとこちらを参照)。Three.js と clingo-wasm で構築された IcoSoKu 用の 3D 視覚化/ソルバーツールによって完成され、次のことが可能です。今すぐオンラインで試してください。このリポジトリには、ソルバーのベンチマークを実行し、IcoSoKu のすべてのインスタンスが実際に解決できることを検証するいくつかのスクリプトも含まれています (実験結果を参照)。

IcoSoKuの写真

問題

IcoSoKu は、2009 年に Andrea Mainini によって作成された機械式パズルで、次のように機能します。

ゲームは、12 個の黄色のペグ (1 から 12 までの数字) を頂点に任意に配置することによってセットアップされます。
ゲームは、ゲームに同梱されている 20 面体の面上にある 20 枚の三角形タイルの配置を見つけて、各頂点を囲む黒い点の数が黄色のペグの数と等しくなるようにプレイします。

20 個のタイルを以下に示します。

IcoSoKuのタイル構成。

3coSoKuは IcoSoKu を一般化したもので、各インスタンスは次のように定義されます。

競技場、三角形の面を持つ多面体 (IcoSoKu の場合は 20 面体)。
各頂点の容量、負ではない整数 (黄色のペグの配置)。
タイル。3 つの非負の整数の重みで構成されます (ドットのあるタイル)。

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使用できます。このスクリプトは、右の図 (アルファベット順) の規則に従って、黄色のペグを指定する 12 個の容量を入力として受け入れます。

$ 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-wasm使用して、WebAssembly にコンパイルされた clingo と ASP エンコーディングのおかげで、ユーザーが指定した IcoSoKu インスタンスを実際に (ブラウザー内で) 解決します。

ここで最新のブラウザを使用して Web アプリケーションを試すことも、次の 2 つの方法でローカルに起動することもできます。

任意の 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のオプション-s WASM=0 --memory-init-file 0 (クリンゴのパフォーマンスが低下します)。

ライセンス

私のすべてのコード (ソルバー、スクリプト、および webapp) は GNU GPL v3 ライセンスの条件に基づいてライセンスされていますが、私が使用しているソフトウェアとアセット ( webapp/{http,offline}/vendorおよびwebapp/{http,offline}/assetsにあります) は、 webapp/{http,offline}/assets )、つまり Clingo WebAssembly、three.js、Tweakpane、および stats.js は、元のライセンスを保持します。私の画像 ( imagesフォルダー内) は、代わりに CC BY に基づいてライセンスされています。