3coSoKu

3coSoKu

Solucionadores de programação MiniZinc e Answer Set para IcoSoKu e sua generalização fortemente NP-completa 3coSoKu (veja os artigos sobre isso aqui e aqui), completados por uma ferramenta de visualização/solução 3D para IcoSoKu construída com Three.js e clingo-wasm, que você pode experimente on-line agora. Este repositório também contém alguns scripts de benchmarking dos solucionadores e verificando se cada instância do IcoSoKu pode de fato ser resolvida (veja Resultados experimentais ).

O problema

IcoSoKu é um quebra-cabeça mecânico criado em 2009 por Andrea Mainini e funciona da seguinte forma:

1. o jogo é configurado colocando 12 pinos amarelos (os números de 1 a 12) arbitrariamente nos vértices;
2. o jogo é jogado encontrando um arranjo das 20 peças triangulares enviadas com o jogo nas faces do icosaedro, de modo que o número de pontos pretos ao redor de cada vértice seja igual ao número do pino amarelo.

As 20 peças são mostradas abaixo.

3coSoKu é a generalização do IcoSoKu onde cada instância é definida por:

• o campo de jogo , um poliedro com faces triangulares (o icosaedro, para IcoSoKu);
• a capacidade de cada vértice, um número inteiro não negativo (a disposição dos pinos amarelos);
• as peças , compostas por três pesos inteiros não negativos (as peças com seus pontos).

Para permanecermos fiéis ao IcoSoKu, impomos que o número de peças seja igual ao número de faces. 3coSoKu é fortemente NP-completo, você pode ler todos os detalhes nos artigos que Agostino Dovier, meu professor na Universidade de Udine, e eu escrevemos.

Começando

Para ver as instâncias do IcoSoKu e resolvê-las usando o solucionador ASP, você pode experimentar e brincar com o aplicativo da web: nenhuma instalação é necessária, graças ao Three.js e ao clingo compilado no WebAssembly.

Caso contrário, se você quiser testar os solucionadores, instale o MiniZinc e/ou clingo e baixe este repositório.

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

Os solucionadores, encontrados em solvers/MiniZinc e solvers/ASP , já estão configurados para resolver instâncias do IcoSoKu. Em sistemas Linux/Unix pode-se utilizar o script icosolve.sh , encontrado em ambas as pastas: o script aceita como entrada as doze capacidades especificando os pinos amarelos, seguindo a convenção da figura à direita (ordem alfabética).

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

Alternativamente, você pode modificar o array cap no arquivo input-ico.dzn e fact cap(V,C) em input-ico.lp , respectivamente, seguindo também a convenção da figura à direita, e executar manualmente os solucionadores:

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

para MiniZinc (você também pode usar o IDE) e

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

para ASP.

Resultados experimentais

A pasta tests contém os scripts Bash para realizar alguns testes interessantes, também descritos nos artigos. Detalhes e resultados são descritos aqui. Em particular: os solucionadores permitem resolver todas as instâncias do IcoSoKu, graças às simetrias do jogo; existem bilhões de soluções diferentes para cada instância do IcoSoKu, então uma boa estratégia na vida real para o jogo é reiniciar frequentemente e tentar “ter sorte”.

A ferramenta de visualização 3D

Desenvolvemos um aplicativo 3D visualizando instâncias IcoSoKu e suas soluções usando three.js , Tweakpane e stats.js . Além disso, o aplicativo usa clingo-wasm para realmente resolver (no navegador!) a instância IcoSoKu especificada pelo usuário, graças ao clingo compilado para WebAssembly e nossa codificação ASP.

Você pode experimentar aqui o aplicativo da web usando qualquer navegador moderno ou iniciá-lo localmente de duas maneiras:

• você pode hospedar a pasta webapp/http em sua rede local com qualquer servidor HTTP;

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

• você pode executar a versão offline do aplicativo encontrada em webapp/offline sem fazer nenhuma hospedagem, abrindo o arquivo html principal.

    $ firefox webapp/offline/index.html
  

A versão offline em webapp/offline não aciona as regras CORS do navegador e foi obtida com alguns truques, entre os quais compilar clingo para JavaScript em vez de WebAssembly usando as opções do empscripten -s WASM=0 --memory-init-file 0 ( resultando em pior desempenho do clingo).

Licença

Todo o meu código (o solucionador, os scripts e o webapp) é licenciado sob os termos da licença GNU GPL v3, enquanto o software e os ativos que estou usando (localizados em webapp/{http,offline}/vendor e em webapp/{http,offline}/assets ), isto é, Clingo WebAssembly, three.js, Tweakpane e stats.js, mantêm sua licença original. Minhas imagens (na pasta images ) são licenciadas sob CC BY.

Agradecimentos

Muito obrigado ao meu professor Agostino Dovier pela proposta deste problema e por escrever o artigo comigo, a Marzio De Biasi pelas suas amáveis ​​palavras, aos organizadores do CILC 2020, aos seus revisores e aos seus participantes.