3coSoKu

3coSoKu

Решатели MiniZinc и программирования набора ответов для IcoSoKu и его строго NP-полная обобщенная версия 3coSoKu (см. статьи об этом здесь и здесь), дополненные инструментом 3D-визуализации/решателя для IcoSoKu, созданным с помощью Three.js и clingo-wasm, который вы можете попробуйте онлайн сейчас. Этот репозиторий также содержит несколько сценариев, проверяющих работу решателей и проверяющих, что каждый экземпляр IcoSoKu действительно может быть решен (см. Результаты экспериментов ).

Проблема

IcoSoKu — это механическая головоломка, созданная в 2009 году Андреа Майнини и работающая следующим образом:

1. игра настроена путем произвольного размещения 12 желтых колышков (цифры от 1 до 12) на вершинах;
2. В игре нужно найти расположение 20 треугольных плиток, поставляемых вместе с игрой, на гранях икосаэдра так, чтобы количество черных точек, окружающих каждую вершину, равнялось количеству желтого колышка.

20 плиток показаны ниже.

3coSoKu — это обобщение IcoSoKu, где каждый экземпляр определяется:

• игровое поле — многогранник с треугольными гранями (икосаэдр, для IcoSoKu);
• емкость каждой вершины, неотрицательное целое число (расположение желтых колышков);
• плитки , состоящие из трех неотрицательных целочисленных весов (плитки с точками).

Чтобы оставаться верными IcoSoKu, мы устанавливаем количество плиток равным количеству граней. 3coSoKu строго NP-полна, все подробности вы можете прочитать в статьях, которые мы с Агостино Довье, моим профессором из Университета Удине, написали.

Начиная

Чтобы увидеть экземпляры IcoSoKu и решить их с помощью решателя ASP, вы можете попробовать поэкспериментировать с веб-приложением: установка не требуется благодаря Three.js и clingo, скомпилированному в WebAssembly.

В противном случае, если вы хотите протестировать решатели, установите 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

В качестве альтернативы вы можете изменить cap массива в файле input-ico.dzn и факты cap(V,C) в input-ico.lp соответственно, также следуя соглашению, показанному на рисунке справа, и вручную выполнить решатели:

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

для MiniZinc (вы также можете использовать IDE) и

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

для АСП.

Результаты экспериментов

tests содержит сценарии Bash для выполнения некоторых интересных тестов, также описанных в статьях. Подробности и результаты описаны здесь. В частности: решатели позволяют решить каждый экземпляр IcoSoKu благодаря симметрии игры; для каждого экземпляра IcoSoKu существуют миллиарды различных решений, поэтому хорошая реальная стратегия для игры — частые перезапуски и попытка «повезти».

Инструмент 3D-визуализации

Мы разработали 3D-приложение, визуализирующее экземпляры IcoSoKu и его решения, используя three.js , Tweakpane и stats.js . Более того, приложение использует clingo-wasm для фактического решения (в браузере!) экземпляра IcoSoKu, указанного пользователем, благодаря clingo, скомпилированному в WebAssembly и нашей кодировке ASP.

Вы можете попробовать здесь веб-приложение, используя любой современный браузер, или запустить его локально двумя способами:

• вы можете разместить папку webapp/http в своей локальной сети с помощью любого HTTP-сервера;

    $ cd webapp/http
    $ python3 -m http.server &
    $ firefox localhost:8000
  

• вы можете запустить автономную версию приложения, найденную в webapp/offline без какого-либо хостинга, открыв основной html-файл.

    $ firefox webapp/offline/index.html
  

Автономная версия в webapp/offline не запускает правила CORS браузера, и она была получена с помощью некоторых уловок, среди которых компиляция clingo в JavaScript вместо WebAssembly с использованием параметров empscripten -s WASM=0 --memory-init-file 0 ( что приводит к ухудшению производительности клинго).

Лицензия

Весь мой код (решатель, скрипты и веб-приложение) лицензируется в соответствии с условиями лицензии GNU GPL v3, тогда как программное обеспечение и ресурсы, которые я использую (расположены в webapp/{http,offline}/vendor и в webapp/{http,offline}/assets ), то есть Clingo WebAssembly, Three.js, Tweakpane и stats.js, сохраняют свою первоначальную лицензию. Вместо этого мои изображения (в папке images ) лицензируются по лицензии CC BY.

Благодарности

Большое спасибо моему профессору Агостино Довье за ​​предложение этой задачи и за написание статьи вместе со мной, Марцио Де Бьязи за его добрые слова, организаторам CILC 2020, их рецензентам и его участникам.