الگوریتمستان

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
بازی Lights Out و ریاضیات دوست داشتنی - الگوریتمستان
الگوریتمستان
  »  

بازی Lights Out و ریاضیات دوست داشتنی

        حل بازی Lights Out با ریاضیات دوست داشتنی

فرض کنید صفحه‌ی ۵ در ۵ از کلید شاسی‌های چراغ‌دار داریم و این کلیدها به نحوی به هم متصل هستن که وقتی کلیدی رو فشار می‌دیم، نه تنها وضعیت چراغ همون کلید که وضعیت چراغ چهار کلید بالا، پایین، راست و چپ هم (در صورت وجود) عوض می‌شه؛ یعنی اگر چراغ روشن باشه، خاموش می‌شه و بالعکس. بازی Lights Out (یا Lights Off) روی چنین صفحه‌ای انجام می‌شه و به این ترتیب هست که اگر یک سری از چراغ‌ها در ابتدای کار روشن باشن، چطور می‌تونیم با فشار دادن کلیدها همه‌ی چراغ‌ها رو خاموش کنیم.

پیوند نوشت ۱: شما می‌تونید Lights Out رو اینجا به صورت آنلاین بازی کنید.

من خیلی سال قبل با این بازی آشنا بودم و بازی می‌کردم. اما برام سوال بود که چطور وقتی وسط بازی کم می‌یارم و از برنامه کمک می‌خوام، خودش اتوماتیک بقیه‌ی بازی رو انجام می‌ده و همه‌ی چراغ‌ها در نهایت خاموش می‌شن. بعدا کشف کردم که چطور. اخیرا هم به بازی‌های ساده فکر می‌کردم که بشه راحت پیاده‌سازی کرد. یاد این بازی افتادم و گفتم بد نیست شما هم بدونید چطور ریاضیات دوست داشتنی به کمک حل این مسئله می‌یاد.

پیوند نوشت ۲: اینجا حل بازی رو با JavaScript پیاده کردم.

قبل از اینکه وارد جزئیات ریاضی حل بازی بشیم، باید به این نکات توجه داشت:

۱- بر اساس اینکه هر بار فشار دادن یک کلید، وضعیت اون و اطرافیانش رو عوض می‌کنه و فشار دوم، همه رو به وضعیت اولیه بر می‌گردونه، پس فشار دادن بیشتر از یک بار یک کلید ارزش خاصی نداره و صرفا باید روی این موضوع تمرکز کنیم که آیا نیاز هست کلیدی فشار داده شه یا نه؟

۲- بر اساس نکته‌ی قبلی، اگر همه‌ی کلیدهای مورد نیاز برای خاموش شدن کل چراغ‌ها رو مجددا فشار بدیم، به وضعیت اولیه‌ی صفحه می‌رسیم. پس در حل مسئله می‌تونیم فرض کنیم چراغ‌ها در ابتدا همه خاموش هستن و هدفمون رسیدن به الگوی مشخص هست.

۳- ترتیب فشار دادن کلید‌ها برای رسیدن به نتیجه‌ی مطلوب مهم نیست (چرا؟).

۴- این بازی در سایر ابعاد هم قابل بازی کردن هست و لزومی نداره حتما ۵ در ۵ باشه. بنابراین برای رسیدن به حل مسئله می‌تونیم ابعاد کوچکتر رو بررسی کنیم.

۵- اگر ابعاد صفحه رو $n$ در $n$‌ در نظر بگیریم، تعداد $2^{n^2}$ حالت مختلف برای انتخاب از بین کلیدها برای فشار دادن وجود داره (چرا؟). با این حساب جستجوی کل فضای مسئله از مرتبه‌ی نمایی هست و اگر ابعاد صفحه بزرگ باشه، در عمل امکان‌پذیر نیست.

بر اساس این توضیحات می‌ریم سراغ مثالی که ابعاد صفحه ۲ در ۲ باشه و هدف ما رسیدن از صفحه‌ی کاملا خاموش به الگوی مورد نظرمون هست. فشار دادن کلیدها رو با شمارش از گوشه‌ی چپ بالا به صورت سطری با $b_{11}$، $b_{12}$، $b_{21}$ و $b_{22}$ و روشن یا خاموش بودن چراغ این چهار کلید رو با $r_{11}$، $r_{12}$، $r_{21}$ و $r_{22}$ مشخص می‌کنیم. کلید اول تحت تاثیر دو کلید ردیف بالا و کلید چپ ردیف پایین هست. یعنی فشار دادن هر کدوم از این کلیدها باعث تغییر وضعیت چراغ این کلید می‌شه. اگر فقط یکی یا هر سه فشار داده شن، چراغ روشن می‌شه و اگر هیچ‌کدوم یا فقط دو تا فشار داده شن، خاموش باقی می‌مونه. به بیان ریاضی‌تر، باقیمانده تقسیم بر دو اگر یک باشه، چراغ روشن می‌شه و اگر صفر باشه، خاموش باقی می‌مونه. یعنی:

$ (b_{11} + b_{12} + b_{21}) \; mod \; 2 = r_{11} $

به همین ترتیب می‌تونیم برای بقیه‌ی کلیدها چنین رابطه‌ی بنویسم و به یک دستگاه چهار معادله‌ی چهار مجهولی برسیم. نگران محاسبه‌ی باقیمانده هم نباید بود. چون می‌دونیم که هر کلید حداکثر یک بار فشار داده می‌شه و چراغ هم فقط دو وضعیت روشن و خاموش داره. پس همه چیز به صورت باینری هست و می‌تونیم محاسبه‌ی باقیمانده رو با عملکر XOR جایگزین کنیم:

\[ \left\{ \begin{matrix} b_{11} \oplus b_{12} \oplus b_{21} = r_{11} \\ b_{11} \oplus b_{12} \oplus b_{22} = r_{12} \\ b_{11} \oplus b_{21} \oplus b_{22} = r_{21} \\ b_{12} \oplus b_{21} \oplus b_{22} = r_{22} \\ \end{matrix} \right. \]

با مشخص بودن مقادیر $r_{11} $ تا $r_{22} $ این دستگاه رو حل می‌کنیم و مقادیر به دست اومده برای $b_{11} $ تا $b_{22}$ مشخص می‌کنه باید کدوم کلیدها فشار داده شه.

چنین دستگاه معادله‌ای رو می‌شه برای هر ابعادی از صفحه ساخت و با حل دستگاه به نتیجه‌ی مطلوب رسید. این دستگاه در ابعاد ۲ در ۲ حتما به جواب منحصر بفرد می‌رسه. اما مثلا در ابعاد ۵ در ۵ نه تنها خیلی اوقات هیچ جوابی وجود نداره (یعنی الگوهایی در این ابعاد وجود دارن که نمی‌شه با فشار دادن کلیدها ساختشون یا خاموششون کرد)، بلکه الگوهای جواب‌دار حتما چهار راه مختلف برای خاموش شدن دارن!

پیوند نوشت ۳: اگر علاقه‌مند به موضوع شدید، ویکی‌پدیای انگلیسی معرفی بازی رو مطالعه کنید.

به اشتراک‌گذاری نوشته
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
برچسب‌ها
       
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

01 02 03 04 05 06 07 08 09 10 11 12 13 14

 


• سید رضا
سه‌شنبه، ۱۸ اردیبهشت ماه ۱۳۹۷، ساعت ۲۰:۴۳

060606


الگوریتمستان در تلگرام

   

   

پیوند کوتاه: عمر نوشته:  ۴۳۲ روز
تعداد بازدید:  ۷۰۳ بازدید
تعداد امتیاز:  ۴ امتیاز
میانگین امتیاز:  ۳.۷۵  از  ۵.۰۰
»  نکته‌ای در مورد کلاس‌ها و مجموعه‌ها در ++C
        بررسی روش تعریف کلاس برای قابلیت استفاده از ظرف‌های مجموعه (set و unordered_set) در زبان برنامه‌نویسی ++C
»  سوال Free Ticket
        راهنمای حل سوال Free ticket، از سوالات المپیاد ملی کامپیوتر هندوستان
»  sync_with_stdio در زبان ++C
        نکته‌ای در مورد کارایی عملیات ورودی و خروجی در زبان برنامه‌نویسی ++C و عملکرد تابع sync_with_stdio
»  نکته‌ای در محاسبه‌ی زمان اجرای کد
        در مورد تفاوت توابع clock و time در زبان برنامه‌نویسی ++C برای محاسبه‌ی زمان اجرای برنامه
»  ابزار VJudge
        معرفی وب‌سایت Virtual Judge برای برگزاری مجازی مسابقه‌ی برنامه‌نویسی به سبک مسابقات ACM-ICPC
»  هدر فایل bits/stdc++.h
        معرفی هدرفایل bits/stdc++.h برای کاهش زمان آماده شدن کد مسابقات برنامه‌نویسی
»  نکته‌ای از مسأله‌ی Graphical Editor
        استفاده از stringstream در حل سوالات مسابفات برنامه‌نویسی با زبان برنامه‌نویسی ++C
»  ابزار UVA Toolkit
        معرفی وب‌سایت UVA Toolkit برای کمک به حل سوالات برنامه‌نویسی UVA Online Judge
»  نکته‌ای از مسأله‌ی LC-Display
        نکته‌ای در باب روش ذخیره کردن ورودی یک مسأله
»  تابع popen
        روش اجرای برنامه‌ای دیگر داخل کد ++C و استفاده از خروجی آن
»  بازی TicTacToe
        پروژه‌ی بازی TicTacToe با زبان برنامه‌نویسی ++C و Qt
»  سینوس و کسینوس را قورت بده
        محاسبه‌ی جدولی سینوس و کسینوس زوایای مشهور
»  نکته‌ای در استفاده از map
        نکته‌ای در مورد استفاده از ساختمان داده‌ی map با مثالی به زبان برنامه‌نویسی ++C
»  بازی مین‌روب
        بازنشر یک یادداشت قدیمی