3coSoKu

Three.js 및 clingo-wasm으로 구축된 IcoSoKu용 3D 시각화/솔버 도구로 완성된 IcoSoKu 및 강력한 NP 완전 일반화 3coSoKu용 MiniZinc 및 응답 세트 프로그래밍 솔버(여기 및 여기에서 관련 문서 참조) 지금 온라인으로 시도해 보세요. 이 저장소에는 솔버를 벤치마킹하고 IcoSoKu의 모든 인스턴스가 실제로 해결될 수 있는지 확인하는 일부 스크립트도 포함되어 있습니다( 실험 결과 참조).

IcoSoKu의 사진

문제

IcoSoKu는 Andrea Mainini가 2009년에 만든 기계식 퍼즐이며 다음과 같이 작동합니다.

게임은 12개의 노란색 말뚝(1부터 12까지의 숫자)을 정점에 임의로 배치하여 설정됩니다.
게임은 게임과 함께 제공되는 20개의 삼각형 타일을 정이십면체 면에 배치하여 각 꼭지점을 둘러싸는 검은 점의 수가 노란색 말뚝의 수와 동일하도록 하는 방식으로 진행됩니다.

20개의 타일이 아래에 표시됩니다.

IcoSoKu의 타일 구성.

3coSoKu 는 각 인스턴스가 다음과 같이 정의되는 IcoSoKu의 일반화입니다.

경기장 , 삼각형 면을 가진 다면체(IcoSoKu의 경우 정이십면체);
각 정점의 용량 , 음수가 아닌 정수(노란색 말뚝의 배치)
음이 아닌 정수 가중치 3개(점이 있는 타일)로 구성된 타일 .

IcoSoKu에 충실하기 위해 타일 수를 면 수와 동일하게 적용합니다. 3coSoKu는 강력하게 NP 완전하므로 Udine 대학교 교수인 Agostino Dovier와 제가 쓴 논문에서 모든 세부 정보를 읽을 수 있습니다.

시작하기

IcoSoKu 인스턴스를 확인하고 ASP 솔버를 사용하여 문제를 해결하려면 웹 애플리케이션을 사용해 볼 수 있습니다. 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 애플리케이션을 개발했습니다. 또한 응용 프로그램은 WebAssembly로 컴파일된 clingo와 ASP 인코딩 덕분에 clingo-wasm 사용하여 사용자가 지정한 IcoSoKu 인스턴스를 실제로 (브라우저 내에서!) 해결합니다.

여기에서 최신 브라우저를 사용하여 웹 애플리케이션을 사용해 보거나 다음 두 가지 방법으로 로컬에서 실행할 수 있습니다.

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에 따라 라이센스가 부여됩니다.