می‌توان نشان داد، اولین کسی که دو ‎X کنار هم می سازد، بازنده است. بنابراین هرکس در نوبت خودش باید خانه‌ای را پر کند که با هیچ ‎X‎ دیگری مجاور نباشد‎. ‎ فرض کنید در ابتدای بازی ‎$n$‎ خانه داریم و نفر اول خانه‌ی ‎$k$‎ام را پر می‌کند. ‎ ‎ خانه‌های ‎$k-1$‎ ام و ‎$k+1$‎ ام نیز دیگر قابل استفاده نیستند و درواقع بعد از این حرکت دو بازی با اندازه‌های ‎$k – 2$‎ و ‎$n – k – 1$‎ باقی می‌ماند که نفر دوم باید در دقیقا یکی از این بازی‌ها، حرکت خود را انجام دهد‎.‎

درواقع در هر مرحله تعدادی بازی داریم که هرکس در نوبت خودش یکی از این بازی‌ها را به دو بازی با اندازه‌های کوچک‌تر تبدیل می‌کند. توجه کنید که ممکن است بازی‌های جدید دارای صفر خانه باشند و دیگر قابل تقسیم نباشند. بنابراین کسی بازنده است که در نوبت او هیچ بازی ای قابل تقسیم نباشد و این یعنی در همه‌ی بازی‌ها یک ردیف صفرتایی داشته باشیم‎.‎

اگر بخواهیم با روش داینامیک این مسئله را حل کنیم، تعداد حالات می‌تواند بسیار زیاد باشد. درواقع برای حل بازی‌هایی که خود از چند بازی دیگر تشکیل شده‌اند، این بازی را به بازی نیم تبدیل می‌کنند و با کمک آن بازی اصلی را حل می‌کنند‎. ‎ تعریف: برای هر وضعیت از یک بازی مثل ‎$G$‎ که دور ندارد، عددی به اسم عدد نیم تعریف می‌شود که با استفاده از الگوریتم زیر محاسبه می‌شود: ‎

1. مجموعه ی ‎$A$‎ را برابر با وضعیت‌هایی که هنوز عدد نیم‌شان مشخص نشده است، قرار بده.
2. ‎‎از بین وضعیت‌های مجموعه‌ی ‎$A$‎ وضعیتی پیدا کن که به ازای همه‌ی حرکت‌های ممکن از آن وضعیت، به وضعیتی برسیم که در مجموعه‌ی ‎$A$‎ نباشد. (چون گراف دور ندارد، چنین وضعیتی وجود دارد‎.‎) اسم این وضعیت را ‎$u$‎ می‌گذاریم.
3. ‎ مجموعه‌ی ‎$B$‎ را برابر با مجموعه‌ی اعداد نیم همه‌ی وضعیت‌هایی که از وضعیت ‎$u$‎ می توان به آنها رفت، قرار بده.
4. ‎ عدد نیم وضعیت ‎$u$‎ برابر با کوچک‌ترین عدد صحیح نامنفی‌ای است که در مجمومه‌ی ‎$B$‎ وجود ندارد.
5. ‎ درصورتی که عدد نیم همه‌ی وضعیت‌ها مشخص نشده است، به مرحله‌ی ‎1‎ برگرد.

پس از اجرای این الگوریتم روی بازی ‎$G$‎ با فرض اینکه گراف این بازی دور ندارد، برای هر وضعیت عدد نیم‌اش حساب می‌شود. حال در قضیه‌ی زیر به کاربرد این عدد پی می‌بریم‎:

‎ قضیه ‎1‎: فرض کنید دو نفر همزمان روی بازی‌های ‎$G_1$‎، ‎$G_2$‎ ، ‎$\cdots$‎ .، ‎$G_n$‎ به این طریق بازی می‌کنند. هر کس در نوبت خودش در دقیقا یکی از این ‎$n$‎ بازی یک حرکت انجام می دهد. اگر اعداد ‎$a_1$‎، ‎$a_2$‎، ‎$\cdots$‎ ، ‎$a_n$‎ برابر با اعداد نیم در هر کدام از ‎$n$‎ بازی بالا باشد، نفر اول استراتژی برد دارد، اگر و فقط اگر ‎xor‎ این ‎$n$‎ عدد بزرگ‌تر از صفر باشد‎.

‎ روش اثبات این قضیه، کاملا مشابه یافتن حالات برد و باخت در بازی نیم است. با این تفاوت که در بازی نیم به جای این ‎$n$‎ بازی، ‎$n$‎ کیسه سنگ، وجود دارد‎.

حال به سراغ حل مسئله‌ی اصلی می‌رویم. در این مسئله در هر مرحله تعدادی بازی داریم. هر کس در نوبت خودش یکی از این بازی‌ها را به دو بازی با اندازه‌های کوچک‌تر تبدیل می کند. در حل این مسئله، قضیه ی ‎1‎ به تنهایی، کارساز نیست. زیرا این قضیه در حالتی بود که از ابتدا ‎$n$‎ بازی داشته باشیم و در هر مرحله تعداد بازی‌ها افزایش پیدا نکند. اما در این مسئله، در یک حرکت ممکن است تعداد بازی‌ها افرایش پیدا کند‎.‎

قضیه ‎2‎: فرض کنید بازی ‎$H$‎ از جمع دو بازی ‎$G_1$‎ و ‎$G_2$‎ ساخته شده باشد به این شکل که هرکس در نوبت خودش دقیقا در یکی از دو بازی ‎$G_1$‎ و ‎$G_2$‎ حرکت بکند. در این صورت عدد نیم بازی ‎$H$‎ از ‎xor‎ کردن عدد نیم بازی‌های ‎$G_1$‎ و ‎$G_2$‎ به‌دست می آید‎.

‎ حال بااستفاده از این قضیه می‌توان عدد نیم را برای وضعیت‌های مختلف بازی ‎3X‎ محاسبه کرد. برای محاسبه‌ی عدد نیم در حالی که یک جدول ‎$1 n$‎ وجود دار د، تمامی حرکت‌های ممکن را بررسی می‌کنیم. اگر در طی حرکتی دو بازی با اندازه‌های ‎$a$‎ و ‎$b$‎ باقی بماند، ‎xor‎ عدد نیم این دو بازی را حساب می‌کنیم و در مجموعه‌ی ‎$A$‎ می‌ریزیم. بعد از بررسی تمام حرکات، کوچک‌ترین عدد صحیح نامنفی که در مجموعه‌ی ‎$A$‎ وجود ندارد، عدد نیم بازی درحالت ‎$n$‎ می‌باشد‎.‎

به طور دقیق‌تر اگر ‎$F_n$‎ را برابر عدد نیم بازی 3X‎ در حالتی که ‎$n$‎ تا خانه داریم، تعریف کنیم، رابطه‌ی بازگشتی زیر برای ‎$F_n$‎ ها برقرار است: ‎‎ ‎‎

• $F_0=0$‎
• $A_n= \{F_a \bigoplus F_b | a=Max(0,k-2),b=Max(0,n-k-1),1 \leq k \leq n\}$‎
• $F_n=Min\{x | x \geq 0,x \in Z,x \notin A_n \}$‎

حال کافی است ما ‎$F_n$‎ را حساب کینم و درصورتی که مقدار آن صفر باشد، ‎$F_n$‎ حالت باخت است و در غیر این صورت حالت برد است‎.‎

‎‎ با توجه به رابطه‌ی بازگشتی‌ای که در بالا برای ‎$F_n$‎ حساب کردیم، کافی است که مقادیر ‎$F_i$‎ را با استفاده از روش پویا حساب کنیم. برای این کار در هر مرحله برای محاسبه‌ی ‎$A_n$‎ از ‎$O(n)$‎ زمان صرف می‌کنیم. همچنین برای یافتن کوچک‌ترین ‎$x$‎ صحیح و نامنفی که در ‎$A_n$‎ نیامده است، نیاز به ‎sort‎ کردن مجموعه‌ی ‎$A_n$‎ داریم که از ‎$O(n \log n)$‎ زمان صرف می‌کند. و چون کلا ‎$n$‎ بار این مراحل تکرار می‌شود، کل الگوریتم را می‌توان از ‎$O(n^2 log n)$‎ پیاده‌سازی کرد ‎

پيچيدگي

درصورتی که مایل هستید اطلاعات بیش‌تری راجع به حل بازی‌های موازی پیدا کنید، این لینک منبع خوبی است.