هيكل / خوارزمية لحل اللعبة مع بطاقات متداخلة

Question

ضع في اعتبارك لعبة بطاقة على طول خطوط Tower Solitaire أو Tripeaks أو Fairway Solitaire: يتكون الجدول من عدد من البطاقات المتوفرة على الفور، كل منها قد يغطي بطاقات أخرى تحتها (حظرها من لعبها). لديك بطاقة "مؤسسة" واحدة، ويمكنك إزالة بطاقة من الجدول إذا كانت برتبة واحدة بالضبط أو أسفل بطاقة الأساس الخاصة بك، في هذه النقطة تصبح بطاقة الأساس الجديدة. لديك عدد محدود من البطاقات البديلة للرسم عند عدم تشغيل بطاقة من الجدول، لذلك تريد عموما أن تلعب أطول سلسلة من البطاقات ممكنة.

أولا، كيف يمكنك تمثيل اللوحة لتسهيل العثور على حل؟ ثانيا، ما الخوارزمية التي تستخدمها للعثور على أطول تسلسل قابل للعب؟

مثال:

 -4A- -5-3- -2-4B-

بطاقات على بطاقات الكتلة السفلية أعلى من إزالتها: لا يمكنك إزالة 4A حتى الآن 3 و 2 قد ولت. على افتراض أن بطاقة البدء الخاصة بك هي ACE، فإن اللعب المثلى هنا سيكون 2، 3، 4B، 5، 4A. (يمكنك اللعب 2، 3، 4A بدلا من ذلك، ولكن هذا ليس جيدا.)

أفترض أن هذا يجب أن يمثل كأنواع من الرسم البياني الموجه. لديك حواف من 3 و 2 إلى 4A ومن 2 و 4B إلى 5، ولكن هل لديك أيضا حواف بين 3 و 2 وبين 4A و 5، لأن المرء قابل للعب بعد الآخر؟ إذا كان الأمر كذلك، فهل من شأنها أن تكون حقيقة أنه يمكن لعبها في أي من النظام (3 ثم 2 أو 2 ثم 3) تكوين دورة في الرسم البياني يمنعك من استخدام خوارزميات "أطول مسار" فعالة؟ (أعتقد أن العثور على أطول مسار في الرسم البياني هو np-complete إذا كان الرسم البياني يحتوي على دورات.)

Answer 1

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

Answer 2

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

أقترح ترميز بناء على شكل هيكل البطاقات المتبقية على الطاولة.

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