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