[ 1000000$ لحـل خوارزمية الـMinesweeper..! ]^_^

[غرور فتاه]

اذا كنتـ/ي من لاعبي هذه اللعبة الشهيرة فستعرف عما أتحدث...
لقد توصل الباحث Richard Kaye في عام 2000 إلى نتيجة مفادها أن تعقيد حل مسألة كانسة الألغام هوNP-complete
لمن لا يعرف اللعبة فهي تعتمد على اكتشاف أماكن الألغام بين مجموعة من المربعات و ذلك بالاستفادة من المعلومات التي تقدمها الأرقام خلف كل مربع,و هي من الألعاب التي تأتي مع نظام تشغيل ويندوز.

الحالة الموضحة في الشكل تعطي فكرة عن الصعوبة الكامنة في حل هذه اللعبة , فلكي نكتشف أماكن الألغام علينا أن نسبر كل المربعات و نجمع كل المعلومات المتوفرة و نتخذ أقل عدد ممكن من المجازفات , و في هذه الحالة المبينة في الشكل ليس علينا أن نقوم بأي مجازفة بل يكفي أن نمعن التفكير و نفكر في كل الاحتمالات حتى نتوصل للحل الوحيد, طبعاً هناك حالات خاصة يكون لزاماً علينا أن نقوم بالتخمين و لكن في مثل هذه الحالات يجب أن نتدرس كافة الاحتمالات و نحاول أن نجعل المجازفة أقل ما يمكن.
عندما تلعب في كانسة الألغام عليك أن تأخذ بعين الاعتبار كل منطقة اللعب بحيث يكون لكل خطوة تأثير كبير على باقي المربعات و يصبح لزاماً علينا سبرها من جديد بعد كل خطوة, و هذا ما يجعل اللعبة صعبة الحل و يجعلنا نعتقد بأنها NP-complete
لقد تمكن Richard Kaye من برهان أن مسألة كانسة الألغام مكافئة في التعقيد لمسائل NP-complete و هي مسائل تأخذ شكل مسائل عامة تتطلب أجوبة من النمط نعم\لا
إن هذه المسائل مهمة للغاية و اكتشاف خوارزمية فعالة لحلها مفيد جداً و أعني هنا بكلمة فعالة أنها تستغرق زمن كثير حدود لتنفيذها, و لكن للأسف فحتى يومنا هذا لم يتمكن أحداً من ايجاد مثل هذه الخوارزمية, و هناك كثير من الناس يعتقدون أنه لا وجود لمثل هذه الخوارزمية و لكن حتى برهان استحالة ايجاد خوارزمية فعالة قد يكون مستحيلاً...
و هكذا من خلال مسألة كانسة الألغام نجد نفسنا نعود للمسألة الشهيرة هل NP=P ؟
و التي تعتبر من أهم و أكبر المسائل المفتوحة في الرياضيات إلى يومنا هذا , لمزيد من المعلومات عن هذه المسألة

www.csc-sy.com/html/modules.php?name=Forums&file=viewtopic&t=340

إذا تمكن أي شخص في العالم من ايجاد خوارزمية فعالة لحل مسألة كانسة الألغام حتى عندما تكون عبارة عن شبكة عملاقة من المربعات بحيث تستغرق زمن كثير حدود , في حين أن كل الدلائل تقول بأنه لا وجود لمثل هذه الخوارزمية فسيكون مبلغ الجائزة و قدرها 1000000$ من نصيبه, و في الحقيقة حتى برهان استحالة وجود هذه الخوارزمية سيجعل هذه الجائزة من نصيبه.
من يعلم قد يكون أول من يحل هذه المسألة طالب من عندنا ^_*

و من الجدير بالذكر أن لعبة Tetris الشهيرة تعد من مسائل NP-complete أيضاً.
المصادر:
http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm
http://en.wikipedia.org/wiki/NP-complete
http://www.claymath.org/Popular_Lectures/Minesweeper/

[قائد بلا جنود]

ما شاء الله تبارك الله



أحييكي على هذا الموضوع المفيد والحماسي




من الرائع وجود ناس تحب تفكر وتبحث وتشغل مخها ما شاء الله تبارك الله




في الحقيقه انا وقعت في حيره بالنسبه لهذا الموضوع... ما عندي خلفيه كبيره عنه لكن إن شاء الله في وقت الفضاوه ابي احاول ابحث عنها شوي..



شكراً جزيلاً على هذا الموضوع...