3coSoKu

3coSoKu

MiniZinc dan Pemrograman Kumpulan Jawaban untuk IcoSoKu dan generalisasi NP-lengkapnya yang kuat 3coSoKu (lihat makalah tentangnya di sini dan di sini), dilengkapi dengan alat visualisasi/solver 3D untuk IcoSoKu yang dibangun dengan Three.js dan clingo-wasm, yang Anda bisa coba online sekarang. Repositori ini juga berisi beberapa skrip yang membandingkan pemecah dan memverifikasi bahwa setiap contoh IcoSoKu memang dapat diselesaikan (lihat Hasil eksperimen ).

Masalahnya

IcoSoKu adalah teka-teki mekanis yang dibuat pada tahun 2009 oleh Andrea Mainini dan cara kerjanya sebagai berikut:

1. permainan diatur dengan menempatkan 12 pasak kuning (angka dari 1 hingga 12) secara acak di simpul;
2. Permainan ini dimainkan dengan mencari susunan 20 ubin segitiga yang dikirimkan dengan permainan pada muka ikosahedron, sehingga jumlah titik hitam yang mengelilingi setiap titik sama dengan jumlah pasak kuningnya.

20 ubin ditunjukkan di bawah ini.

3coSoKu adalah generalisasi dari IcoSoKu di mana setiap instance didefinisikan oleh:

• lapangan bermain , polihedron dengan permukaan segitiga (icosahedron, untuk IcoSoKu);
• kapasitas setiap simpul, bilangan bulat non-negatif (disposisi pasak kuning);
• ubin , terbuat dari tiga bobot bilangan bulat non-negatif (ubin dengan titik-titiknya).

Agar tetap setia pada IcoSoKu, kami memaksakan jumlah ubin sama dengan jumlah wajah. 3coSoKu sangat NP-lengkap, Anda dapat membaca semua detailnya di makalah yang saya dan Agostino Dovier, profesor saya di Universitas Udine, tulis.

Memulai

Untuk melihat instance IcoSoKu dan menyelesaikannya menggunakan pemecah ASP, Anda dapat mencoba dan bermain-main dengan aplikasi web: tidak diperlukan instalasi, berkat Three.js dan clingo yang dikompilasi ke WebAssembly.

Jika tidak, jika Anda ingin menguji solvernya, instal MiniZinc dan/atau clingo, lalu unduh repositori ini.

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

Solver, yang ditemukan di solvers/MiniZinc dan solvers/ASP , sudah dikonfigurasi untuk menyelesaikan instance IcoSoKu. Pada sistem Linux/Unix Anda dapat menggunakan skrip icosolve.sh , yang terdapat di kedua folder: skrip menerima dua belas kapasitas sebagai masukan yang menentukan pasak kuning, mengikuti konvensi gambar di sebelah kanan (urutan abjad).

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

Sebagai alternatif, Anda dapat memodifikasi array cap di file input-ico.dzn dan fakta cap(V,C) di input-ico.lp , masing-masing, juga mengikuti konvensi gambar di sebelah kanan, dan secara manual menjalankan pemecah masalah:

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

untuk MiniZinc (Anda juga dapat menggunakan IDE), dan

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

untuk ASP.

Hasil percobaan

Folder tests berisi skrip Bash untuk melakukan beberapa tes menarik, juga dijelaskan di makalah. Detail dan hasilnya dijelaskan di sini. Khususnya: pemecah memungkinkan untuk menyelesaikan setiap contoh IcoSoKu, berkat simetri permainan; ada miliaran solusi berbeda untuk setiap instance IcoSoKu, jadi strategi nyata yang baik untuk game ini adalah sering-sering memulai ulang dan mencoba "beruntung".

Alat visualisasi 3D

Kami mengembangkan aplikasi 3D yang memvisualisasikan instance IcoSoKu dan solusinya menggunakan three.js , Tweakpane , dan stats.js . Selain itu, aplikasi ini menggunakan clingo-wasm untuk benar-benar menyelesaikan (dalam browser!) instance IcoSoKu yang ditentukan oleh pengguna, berkat clingo yang dikompilasi ke WebAssembly dan pengkodean ASP kami.

Anda dapat mencoba aplikasi web di sini menggunakan browser modern apa pun, atau Anda dapat meluncurkannya secara lokal dengan dua cara:

• Anda dapat menghosting folder webapp/http di jaringan lokal Anda dengan server HTTP apa pun;

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

• Anda dapat menjalankan aplikasi versi offline yang terdapat di webapp/offline tanpa melakukan hosting apa pun dengan membuka file html utama.

    $ firefox webapp/offline/index.html
  

Versi offline di webapp/offline tidak memicu aturan CORS browser dan diperoleh dengan beberapa trik, di antaranya mengkompilasi clingo ke JavaScript alih-alih WebAssembly menggunakan opsi empscripten -s WASM=0 --memory-init-file 0 ( mengakibatkan kinerja clingo lebih buruk).

Lisensi

Semua kode saya (pemecah, skrip, dan aplikasi web) dilisensikan berdasarkan ketentuan lisensi GNU GPL v3, sedangkan perangkat lunak dan aset yang saya gunakan (terletak di webapp/{http,offline}/vendor dan di webapp/{http,offline}/assets ), yaitu Clingo WebAssembly, three.js, Tweakpane, dan stats.js, tetap mempertahankan lisensi aslinya. Gambar saya (di folder images ) dilisensikan di bawah CC BY.

Ucapan Terima Kasih

Terima kasih banyak kepada profesor saya Agostino Dovier atas usulan masalah ini dan untuk menulis makalah bersama saya, kepada Marzio De Biasi atas kata-kata baiknya, kepada penyelenggara CILC 2020, kepada para reviewer mereka dan kepada para pesertanya.