3coSoKu

3coSoKu

حلول برمجة MiniZinc ومجموعة الإجابة لـ IcoSoKu وتعميمها القوي الكامل NP 3coSoKu (راجع الأوراق البحثية حول هذا الموضوع هنا وهنا)، والتي تم إكمالها بواسطة أداة التصور/الحل ثلاثي الأبعاد لـ IcoSoKu المبنية باستخدام Three.js وclingo-wasm، والتي يمكنك حاول على الانترنت الآن. يحتوي هذا المستودع أيضًا على بعض البرامج النصية التي تقيس أداء الحلول وتتحقق من إمكانية حل كل مثيل لـ IcoSoKu (انظر النتائج التجريبية ).

المشكلة

IcoSoKu هو لغز ميكانيكي تم إنشاؤه في عام 2009 بواسطة Andrea Mainini ويعمل على النحو التالي:

1. يتم إعداد اللعبة عن طريق وضع 12 أوتادًا صفراء (الأرقام من 1 إلى 12) بشكل عشوائي على القمم؛
2. يتم لعب اللعبة من خلال إيجاد ترتيب للبلاطات المثلثة العشرين المشحونة مع اللعبة على وجوه المجسم العشروني، بحيث يكون عدد النقاط السوداء المحيطة بكل قمة مساويًا لعدد الوتد الأصفر.

يتم عرض البلاط العشرين أدناه.

3coSoKu هو تعميم IcoSoKu حيث يتم تعريف كل مثيل بواسطة:

• الملعب ، متعدد السطوح ذو وجوه مثلثة (المجسم العشروني، لـ IcoSoKu)؛
• سعة كل قمة، عدد صحيح غير سلبي (التصرف في الأوتاد الصفراء)؛
• البلاطات ، مصنوعة من ثلاثة أوزان صحيحة غير سالبة (البلاطات بنقاطها).

لكي نبقى صادقين مع IcoSoKu، نفرض أن يكون عدد المربعات مساويًا لعدد الوجوه. 3coSoKu هو NP-Complete بقوة، يمكنك قراءة جميع التفاصيل في الأوراق التي كتبتها أنا وأجوستينو دوفيير، أستاذي في جامعة أوديني.

ابدء

لرؤية مثيلات IcoSoKu وحلها باستخدام حل ASP، يمكنك تجربة تطبيق الويب والتلاعب به: لا يلزم التثبيت، وذلك بفضل Three.js والتشبث المترجم إلى 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 وfacts 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، لذا فإن الإستراتيجية الواقعية الجيدة للعبة هي القيام بإعادة التشغيل بشكل متكرر ومحاولة "الحصول على الحظ".

أداة التصور ثلاثي الأبعاد

قمنا بتطوير تطبيق ثلاثي الأبعاد لتصور مثيلات IcoSoKu وحلولها باستخدام three.js و Tweakpane و stats.js . علاوة على ذلك، يستخدم التطبيق clingo-wasm لحل فعليًا (داخل المتصفح!) مثيل IcoSoKu الذي حدده المستخدم، وذلك بفضل lingo الذي تم تجميعه إلى 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 -s WASM=0 --memory-init-file 0 ( مما يؤدي إلى ضعف أداء lingo).

رخصة

تم ترخيص كل التعليمات البرمجية الخاصة بي (المحلل والبرامج النصية وتطبيق الويب) بموجب شروط ترخيص GNU GPL v3، في حين أن البرامج والأصول التي أستخدمها (موجود في webapp/{http,offline}/vendor وفي webapp/{http,offline}/assets )، أي Clingo WebAssembly، وthree.js، وTweakpane، وstats.js، يحتفظون بترخيصهم الأصلي. بدلاً من ذلك، يتم ترخيص صوري (الموجودة في مجلد images ) بموجب CC BY.

شكر وتقدير

جزيل الشكر لأستاذي أغوستينو دوفييه على اقتراح هذه المشكلة وعلى كتابة الورقة معي، وإلى مارزيو دي بياسي على كلماته الرقيقة، وإلى منظمي CILC 2020، وإلى مراجعيهم والحاضرين.