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

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

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
بازی 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 و استفاده از خروجی آن
»  سینوس و کسینوس را قورت بده
        محاسبه‌ی جدولی سینوس و کسینوس زوایای مشهور
»  نکته‌ای در استفاده از map
        نکته‌ای در مورد استفاده از ساختمان داده‌ی map با مثالی به زبان برنامه‌نویسی ++C
»  بازی مین‌روب
        بازنشر یک یادداشت قدیمی
»  محاسبه‌ی فاکتوریل اعداد بزرگ
        چطور شاخ غول فاکتوریل را بشکنیم