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

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

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

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

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

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

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

۵- اگر ابعاد صفحه را $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}$ مشخص می‌کند باید کدام کلیدها فشار داده شوند.

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

◄  پیوندها برای مطالعه‌ی بیشتر
مسعود اقدسی فام

مسعود اقدسی فام هستم.

دانش‌آموخته‌ی علوم کامپیوتر و فعال حوزه‌های علم داده و یادگیری ماشین؛ علاقه‌مند به یاد دادن و یاد گرفتن :)

algs.ir/sp7696r     اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram
نوشته‌ها از این دست
       ✦   مسئله آسانسورها
       ✦   مسئله انتخابات
آخرین نوشته‌ها
       ✦   الگوریتم آنلاین
نوشته‌های پرمخاطب
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک (محرمانه):

متن پیام: *  

01 02 06 07 08 09 10 11 12 13 14

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

060606