فرض کنید صفحه‌ی ۵ در ۵ از کلید شاسی‌های چراغ‌دار داریم و این کلیدها به نحوی به هم متصل هستن که وقتی کلیدی رو فشار می‌دیم، نه تنها وضعیت چراغ همون کلید که وضعیت چراغ چهار کلید بالا، پایین، راست و چپ هم (در صورت وجود) عوض می‌شه؛ یعنی اگر چراغ روشن باشه، خاموش می‌شه و بالعکس. بازی 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}$ مشخص می‌کنه باید کدوم کلیدها فشار داده شه.
چنین دستگاه معادله‌ای رو می‌شه برای هر ابعادی از صفحه ساخت و با حل دستگاه به نتیجه‌ی مطلوب رسید. این دستگاه در ابعاد ۲ در ۲ حتما به جواب منحصر بفرد می‌رسه. اما مثلا در ابعاد ۵ در ۵ نه تنها خیلی اوقات هیچ جوابی وجود نداره (یعنی الگوهایی در این ابعاد وجود دارن که نمی‌شه با فشار دادن کلیدها ساختشون یا خاموششون کرد)، بلکه الگوهای جواب‌دار حتما چهار راه مختلف برای خاموش شدن دارن!
پیوند نوشت ۳: اگر علاقه‌مند به موضوع شدید،
ویکی‌پدیای انگلیسی معرفی بازی رو مطالعه کنید
.