3coSoKu

MiniZinc และ Answer Set Programming Solvers สำหรับ IcoSoKu และ 3coSoKu ที่เป็นลักษณะทั่วไปของ NP ที่สมบูรณ์อย่างมาก (ดูเอกสารเกี่ยวกับมัน ที่นี่ และ ที่นี่ ) เสร็จสมบูรณ์โดยเครื่องมือสร้างภาพสามมิติ / เครื่องมือแก้ปัญหาสำหรับ IcoSoKu ที่สร้างด้วย Three.js และ clingo-wasm ซึ่งคุณสามารถทำได้ ลองออนไลน์ตอนนี้ พื้นที่เก็บข้อมูลนี้ยังมีสคริปต์บางตัวที่ทำการเปรียบเทียบตัวแก้ปัญหาและตรวจสอบว่าทุกอินสแตนซ์ของ IcoSoKu สามารถแก้ไขได้อย่างแน่นอน (ดู ผลการทดลอง )

รูปภาพของ IcoSoKu

ปัญหา

IcoSoKu เป็นปริศนากลไกที่สร้างขึ้นในปี 2009 โดย Andrea Mainini และมีลักษณะดังนี้:

เกมดังกล่าวได้รับการตั้งค่าโดยการวางหมุดสีเหลือง 12 อัน (ตัวเลขตั้งแต่ 1 ถึง 12) ไว้บนจุดยอดโดยพลการ
เกมนี้เล่นโดยการค้นหาการจัดเรียงแผ่นกระเบื้องสามเหลี่ยม 20 แผ่นที่จัดส่งมาพร้อมกับเกมบนใบหน้าของไอโคซาฮีดรอน โดยที่จำนวนจุดสีดำที่อยู่รอบจุดยอดแต่ละจุดจะเท่ากับจำนวนหมุดสีเหลือง

จำนวน 20 แผ่นมีดังต่อไปนี้

การกำหนดค่าไทล์ของ IcoSoKu

3coSoKu เป็นลักษณะทั่วไปของ IcoSoKu โดยที่แต่ละอินสแตนซ์ถูกกำหนดโดย:

สนามเด็กเล่น รูปทรงหลายเหลี่ยมที่มีใบหน้า เป็นรูปสามเหลี่ยม (icosahedron สำหรับ IcoSoKu);
ความจุ ของแต่ละจุดยอด ซึ่งเป็นจำนวนเต็มที่ไม่เป็นลบ (ลักษณะของหมุดสีเหลือง)
แผ่นกระเบื้อง ทำจากน้ำหนักจำนวนเต็มที่ไม่เป็นลบสามแผ่น (แผ่นกระเบื้องที่มีจุด)

เพื่อให้ IcoSoKu เป็นจริง เรากำหนดจำนวนไทล์ให้เท่ากับจำนวนใบหน้า 3coSoKu สมบูรณ์ NP อย่างยิ่ง คุณสามารถอ่านรายละเอียดทั้งหมดในเอกสารที่ Agostino Dovier ศาสตราจารย์ของฉันที่ University of Udine และฉันเขียน

เริ่มต้นใช้งาน

หากต้องการดูอินสแตนซ์ IcoSoKu และแก้ไขโดยใช้ ASP Solver คุณสามารถลองใช้เว็บแอปพลิเคชันได้ โดยไม่จำเป็นต้องติดตั้ง ต้องขอบคุณ 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 และ fact 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 ดังนั้นกลยุทธ์ในชีวิตจริงที่ดีสำหรับเกมคือการรีสตาร์ทบ่อยครั้งและพยายาม "โชคดี"

เครื่องมือสร้างภาพสามมิติ

เราได้พัฒนาแอปพลิเคชัน 3 มิติที่แสดงภาพอินสแตนซ์ 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 options -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 แทน

รับทราบ

ขอขอบคุณศาสตราจารย์ Agostino Dovier ของฉันสำหรับข้อเสนอของปัญหานี้และสำหรับการเขียนบทความร่วมกับฉันถึง Marzio De Biasi สำหรับคำพูดของเขาถึงผู้จัดงาน CILC 2020 ถึงผู้ตรวจสอบและผู้เข้าร่วม

ขยาย

ข้อมูลเพิ่มเติม