3coSoKu

3coSoKu

MiniZinc y solucionadores de programación Answer Set para IcoSoKu y su generalización fuertemente NP-completa 3coSoKu (consulte los artículos al respecto aquí y aquí), completados por una herramienta de resolución/visualización 3D para IcoSoKu construida con Three.js y clingo-wasm, que puede Pruébelo en línea ahora. Este repositorio también contiene algunos scripts que comparan los solucionadores y verifican que cada instancia de IcoSoKu pueda resolverse (consulte Resultados experimentales ).

el problema

IcoSoKu es un rompecabezas mecánico creado en 2009 por Andrea Mainini y funciona de la siguiente manera:

1. el juego se configura colocando las 12 clavijas amarillas (los números del 1 al 12) de forma arbitraria en los vértices;
2. El juego se juega encontrando una disposición de las 20 fichas triangulares que se envían con el juego en las caras del icosaedro, de modo que el número de puntos negros que rodean cada vértice sea igual al número de la clavija amarilla.

Las 20 fichas se muestran a continuación.

3coSoKu es la generalización de IcoSoKu donde cada instancia está definida por:

• el campo de juego , un poliedro de caras triangulares (el icosaedro, por IcoSoKu);
• la capacidad de cada vértice, un número entero no negativo (la disposición de las clavijas amarillas);
• los mosaicos , formados por tres pesos enteros no negativos (los mosaicos con sus puntos).

Para mantenernos fieles a IcoSoKu, imponemos que el número de mosaicos sea igual al número de caras. 3coSoKu es fuertemente NP-completo; puedes leer todos los detalles en los artículos que escribimos Agostino Dovier, mi profesor en la Universidad de Udine, y yo.

Empezando

Para ver instancias de IcoSoKu y resolverlas usando el solucionador ASP, puedes probar y jugar con la aplicación web: no se requiere instalación, gracias a Three.js y clingo compilado en WebAssembly.

De lo contrario, si desea probar los solucionadores, instale MiniZinc y/o clingo, luego descargue este repositorio.

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

Los solucionadores, que se encuentran en solvers/MiniZinc y solvers/ASP , ya están configurados para resolver instancias de IcoSoKu. En sistemas Linux/Unix se puede utilizar el script icosolve.sh , que se encuentra en ambas carpetas: el script acepta como entrada las doce capacidades especificando las clavijas amarillas, siguiendo la convención de la figura de la derecha (orden alfabético).

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

Alternativamente, puede modificar el cap de la matriz en el archivo input-ico.dzn y los hechos cap(V,C) en input-ico.lp , respectivamente, siguiendo también la convención de la figura de la derecha, y ejecutar manualmente los solucionadores:

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

para MiniZinc (también puedes usar el IDE), y

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

para ASP.

Resultados experimentales

La carpeta tests contiene los scripts Bash para realizar algunas pruebas interesantes, también descritas en los artículos. Los detalles y resultados se describen aquí. En particular: los solucionadores permiten resolver cada instancia de IcoSoKu, gracias a las simetrías del juego; Hay miles de millones de soluciones diferentes para cada instancia de IcoSoKu, por lo que una buena estrategia en la vida real para el juego es reiniciar con frecuencia e intentar "tener suerte".

La herramienta de visualización 3D

Desarrollamos una aplicación 3D que visualiza instancias de IcoSoKu y sus soluciones usando three.js , Tweakpane y stats.js . Además, la aplicación utiliza clingo-wasm para resolver (¡en el navegador!) la instancia de IcoSoKu especificada por el usuario, gracias a clingo compilado en WebAssembly y nuestra codificación ASP.

Puede probar aquí la aplicación web utilizando cualquier navegador moderno, o puede iniciarla localmente de dos maneras:

• puedes alojar la carpeta webapp/http en tu red local con cualquier servidor HTTP;

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

• Puede ejecutar la versión sin conexión de la aplicación que se encuentra en webapp/offline sin realizar ningún alojamiento abriendo el archivo html principal.

    $ firefox webapp/offline/index.html
  

La versión fuera de línea en webapp/offline no activa las reglas CORS del navegador y se obtuvo con algunos trucos, entre los cuales compilar clingo a JavaScript en lugar de WebAssembly usando las opciones de empscripten -s WASM=0 --memory-init-file 0 ( lo que resulta en un peor rendimiento de clingo).

Licencia

Todo mi código (el solucionador, los scripts y la aplicación web) tiene licencia según los términos de la licencia GNU GPL v3, mientras que el software y los activos que estoy usando (ubicados en webapp/{http,offline}/vendor y en webapp/{http,offline}/assets ), es decir, Clingo WebAssembly, three.js, Tweakpane y stats.js, conservan su licencia original. En cambio, mis imágenes (en la carpeta de images ) tienen licencia CC BY.

Expresiones de gratitud

Muchas gracias a mi profesor Agostino Dovier por la propuesta de este problema y por escribir el artículo conmigo, a Marzio De Biasi por sus amables palabras, a los organizadores de CILC 2020, a sus revisores y a sus asistentes.