لعبة حل خوارزمية (Buttonia, أضواء خارج البديل)

Question

أنا في محاولة لخلق ملاءته وظيفة لعبة الخوارزمية.أساسا الدالة التي ترجع true أو false معين اللعبة لو قابلة للحل أم لا.

اللعبة Buttonia.com (الذي لا تنفيذ الخوارزمية حتى الآن) ، وهو نوع من أضواء خارج اللعبة.أساسا لديك شبكة من الأزرار ، كل منها عند الضغط عليه سيتم تغيير الدولة من بعض الجيران.أنا حاليا توليد لعبة عشوائية التكوين ومن ثم تطبيق الاستدلال بقدر الإمكان.والباقي هو قرر من قبل القوة الغاشمة البحث.

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

button_A = 1 - (button_1 + button_2 + ...+ button_X) % 2

حيث button_1 خلال button_X هي الدول الأزرار مع تأثير على button_A.بعض الأزرار يمكن حلها فورا ، إذا فهي لا تعتمد على الآخرين.لبقية أحاول تكوين واحد حتى أحصل على الصراع ومن ثم العودة تتبع.

حاليا هذه الخوارزمية هو عملي أصغر تكوينات من الألعاب.لقد اختبرت ذلك من 3x3 الألعاب تصل إلى أحجام 10x10.حيث 6x6 بالقرب من الحد الأعلى للحصول على عملية اللعب.

المعادلات بشكل كبير في خفض مساحة البحث من القوة الغاشمة ، مما يجعل العملية.قد يكون هناك رياضي بحت طريقة حل نظام من المعادلات.

---

عينة 3x3 اللعبة في ascii (من buttonia.com/?game=2964):

||#
-o-
+#|

Legend:
o = affect only self
- = affect left and right neighbors
| = affect above and below neighbors
+ = affect left, right, above and below neighbors
# = affect all 8 surrounding neighbors

الحل اضغط على هذه:(0,0), (2,0), (1, 2), (0, 1), (1, 1), (2,1)

المعادلات لهذه اللعبة:

Button_0_0 = 1 - (0) % 2
Button_1_0 = 1 - (Button_2_0) % 2
Button_2_0 = 1 - (0) % 2
Button_0_1 = 1 - (Button_0_0 + Button_0_2 + Button_1_2) % 2
Button_1_1 = 1 - (Button_1_0 + Button_2_0 + Button_0_1 + Button_2_1 + Button_1_2) % 2
Button_2_1 = 1 - (Button_2_0 + Button_1_2 + Button_2_2) % 2
Button_0_2 = 1 - (Button_1_2) % 2
Button_1_2 = 1 - (Button_0_2) % 2
Button_2_2 = 1 - (Button_1_2) % 2

الحلول المحتملة:

تغيير الدوال الرياضية لتجنب الحاجة إلى معامل يتيح لنا التحرك شروط على الجانب الأيسر إلى اليمين ، وخلق أنيق مصفوفة الإعداد نحتاج من أجل التمويه الأسلوب.لذا فإن أول اثنين من المعادلات سوف التوالي تحويل إلى:

-1 = -1*B00 +  0*B10 +  0*B20 +  0*B01 +  0*B11 +  0*B21 +  0*B02 +  0*B12 +  0*B22
-1 =  0*B00 + -1*B10 + -1*B20 +  0*B01 +  0*B11 +  0*B21 +  0*B02 +  0*B12 +  0*B22

مناقشة الحل هنا: القضاء جاوس مع المشغلين مخصصة

الحصول على أوثق.جاهزة تقريبا إلى ما بعد الحل الكامل: عكس الثنائية الشبكات

Answer 1

هذا هو نظام من المعادلات الخطية على F₂, الحقل يحتوي على اثنين من العناصر 0 و 1.

يمكنك حلها تماما مثل العادية المعادلات الخطية ، ولكن عليك أن تفعل الحساب مودولو 2.

تحرير: الجبر الخطي لهذه الحالة يعمل بالضبط مثل أرقام حقيقية, إلا أنه لا يجب أن تحل محل عمليات:

• الجمع والطرح تصبح حصرية أو أي0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0.

• الضرب يصبح:0 * 0 = 0, 0 * 1 = 0, 1 * 1 = 1

• شعبة غير ممكن إلا عن طريق واحد:0 / 1 = 0, 1 / 1 = 1.

جميع المعاملات في معادلات القيم الممكنة من المجاهيل إما 0 أو 1.

حتى نمطية ليست صفع خارج المعادلات مثل كتبت ضمنا في العمليات.

إذا كان النظام الخاص بك من المعادلات غير قابلة للحل سوف تحصل على المعادلة 0 = 1 ، التي من الواضح أنها غير قابلة للحل.

Answer 2

وبدلا من البدء مع دولة عشوائية، لماذا لا تولد نقطة الانطلاق عن طريق التقليب مفاتيح عشوائية، أي العمل الى الوراء من دولة حلها إلى حالة البدء. وبهذه الطريقة يمكنك توليد فقط الألغاز قابلة للحل.

Answer 3

وهذا يبدو تقريبا مثل نظام المعادلات الخطية (باستثناء وزارة الدفاع 2)، لذلك قد تكون قادرة على التكيف واحدة من التقنيات العادية من أجل حل تلك - على سبيل المثال تخفيض صف النظام في شكل مصفوفة (ويكيبيديا) .

Answer 4

وبما أن هذه ليست مشكلة محدودة بفترة زمنية محددة (وأيضا، على افتراض أنه يمكن القيام به في أقل من يوم واحد)، وربما يذهب لبحث اتساع الأول محدودة العمق، مع كل خطوة ممكنة على مستوى وثم كل خطوة الذي يلي يوم من كل خطوة.

وسوف تكون بطيئة، ومع ذلك فمن يضمن تقريبا أن تجد جوابا، إذا كان هناك واحد!

Answer 5

لنفترض انك ببناء نظام من المعادلات وحلها لهم أفضل ما يمكن، ولكن انتهى بعض الصفوف مع جميع على الجانب الأيسر من المعادلة 0 (أنا تمثل المعادلات باعتبارها مصفوفة ممتدة) افترض أنك حاولت حل النظام في حلقة Z2 (وهو من الناحية العملية لهذا المثال بالذات يعني أن التغيير الوحيد هو أن 1 + 1 = 0، آخر كل شيء لا يزال هو نفسه ... ولهذا المشغل الوحيد الذي نحتاجه هو XOR) وانتهت مع المصفوفة التالية:

1001 1
0100 1
0011 0
0000 0

وكما ترون في هذا المثال، الصف 4TH هو كل 0، وهذا يعني أننا لم نحصل على إجابة لذلك. ومع ذلك أعتقد أنه من هذا الطريق: صف من كل 0 يعني أن هذا المتغير لا يؤثر على الحل. وهذا في الواقع سوء اختيار للكلمات ... وهذا يعني فقط أنها يمكن أن يكون لها أي قيمة (ونحن في الحظ هنا، حيث أن جميع القيم تعني 1 أو 0، خلافا لما حدث في الأعداد الحقيقية ... ولذلك فإن هذا يعني أن لدينا 2 حلول لهذا النظام).

وهنا لماذا: ما تحتاج إلى معرفته في هذه المرحلة هو أن العمود أقصى اليمين لا يزال يحتوي على الحل صالحة لعبتك. دعونا نلقي السطر الأول على سبيل المثال. وتقول أن

button_0 + button_3 = 1

ولكن نحن نعلم أن زر 3 يمكن أن يكون أي شيء (منذ السطر 3 هو كل 0S). عند هذه النقطة زر 3 0 (العمود أقصى اليمين في الصف 3 هو 0 عند هذه النقطة) وحتى الآن نحن نعرف أنه يعني

button_0 + 0 = 1

وحتى نعرف لحقيقة أنه لا button_0 1. لذلك في هذا النظام على الرغم من أننا لا يمكن أن تجد مباشرة من button_3، لا يزال لدينا حل صالح.

والمصفوفة الناتجة أعلاه كافية للتحقق من ملاءته. إذا صف يحتوي على كافة 0S ثم هو في الأساس قائلا ان

nothing = nothing

و، أو لتصور أفضل لماذا هذا يعمل،

0x = 0

والذي يجعل المعنى، فإن النظام لا يزال ساري المفعول. ولكن إذا واجهنا على التوالي هذا هو كل 0S <م> إلا أقصى اليمين قليلا، أي بمعنى.

0000 1

والتي من شأنها ان تقول

0x = 1

وهو أمر مستحيل وبالتالي فإننا نعرف الآن أن النظام لا يمكن حلها، لأننا لا يمكن أن تحل وضعا مستحيلا من هذا القبيل.

وذلك في وباختصار يمكن القول، ومحاولة حل المعادلة على أفضل يمكنك، لا تقلق إذا لم تتمكن من العثور بالضبط ما بعض المتغيرات هي، طالما أنك لا تواجه، في أي لحظة، المستحيل الصف الأول فقط ذكر ثم اللعبة قابلة للحل.

ولكن ماذا إذا كنا نريد <م> أقصر حل للنظام؟ هنا علينا أن دراسة جميع الحلول الممكنة. لدينا button_3 التي يمكن أن تكون أي قيمة، وهذا يعني أن أي 1 في العمود 3 يعني أن الصف الذي يتم العثور عليه، يتأثر button_3. لذلك لنفترض أننا نريد معرفة ما اذا كان الحل باستخدام button_3 سيكون أقصر. ونحن إنشاء مصفوفة آخر، ولكن مجموعة button_3 إلى 1 الآن (منذ أنشأنا في وقت سابق أنه يمكن أن يكون أي شيء، وكان لدينا بالفعل 0 في هناك، وحتى الآن نحن تحقق ل1). نحن الآن في نهاية المطاف مع المصفوفة التالية:

1001 1
0100 1
0011 0
0001 1

ونحن لحد أنه بقدر ما نستطيع وتنتهي الآن مع هذه المصفوفة:

1000 0
0100 1
0010 1
0001 1

وهذا لا يزال هناك حل صحيح، ولكن يمكننا أن نرى أن الحل هو أطول (تتطلب 3 بدلا من 2 تضغط على زر) وبالتالي فإننا تخلص منه. علينا أن نفعل هذا لكل التقليب من تحديد الصفوف وجدنا وجميع 0S إلى 1. لذلك إذا كان لدينا صفوف السينية التي كانت كلها 0S، ثم النظام لديه س ^ 2 الحلول، وعلينا أن تحقق كل منهم.