توصیه هایی در راستای چگونگی بازی سوکوبان

نوشتار

عبارات زیر در حین این راهنمایی استفاده می شوند:

• حرکت: یک قدم کارگر چه جعبه ای را حرکت بدهد چه ندهد.
• مسیر: دنباله ای از حرکات.
• موقعیت: کل این مساله با در نظر گرقتن کارگر و همه ی جعبه ها در یک موقعیت خاص.
• پاسخ: موقعیتی که در آن هر جعبه ای روی یک نقطه قرار دارد.
• مسیر پاسخ: دنباله ای از حرکات از موقعیت اصلی به پاسخ.
• موقعیت مرده: موقعیتی که از آن پاسخ نمی تواند به دست آید.

استراتژی کلی

کوتاهترین پاسخ ممکن است شامل ۱۰۰، ۳۰۰ یا حتی ۱۰۰۰ حرکت. ساده ترین بازی ۱ ما ۷۳ حرکت لازم دارد، بازی ۸، ۱۲۶ حرکت لازم دارد. اگر به طور متوسط، فرض کنید، ۲ احتمال برای هر حرکت و پاسخ ۱۰۰ حرکت می خواهد، آنگاه یک جستجوی جامع ممکن است نیازمند جستجوی ۲^۱۰۰ مسیر برای پیدا کردن پاسخ باشد. حتی برای رایانه ها این ممکن نیست. در نتیجه ما لازم است که:

1. زود تشخیص دهیم اگر موقعیتی مرده است،
2. هدف نهایی را به چند کار زیرمجموعه ای تقسیم کنید.اگر یک مسیر پاسخ ۱۰۰ حرکتی بتواند به مثلا، ۱۰ زیر شاخه تقسیم شود، آنگاه پیچیدگی مساله به شدت کاهش پیدا می کند.. به علاوه، ممکن است که بتوان ترتیبی که در آن زیرشاخه باید انحام شود را کاهش داد و آنگاه کل مساله برای حل شدن ساده می شود،
3. اولین محدودیت برای مسیر پاسخ،
4. به ابتکارهای دیگر فکر کنید.

درباره ی ۱: تشخیص زودهنگام موقعیت های مرده

۱. ۱: گاهی آسان است که تصمیم بگیریم آیا موقعیتی مرده است، فقط کافی است به همسایگی یک جعبه ی تنها نگاه کرد. تنها چیزی که لازم است یک بازرسی موضعی است. اگر جعبه ای روی یک نقطه قرار نگرفته است و نمی تواند به صورت افقی و عمودی حرکت کند، آنگاه آن موقعیت مرده است. جعبه ممکن است با دیوار و یا جعبه های دیگر بلوکه شده باشد که باز هم نمی تواند حرکت کند.

۱.۲: این اندکی سخت تر است که ببینیم که موقعیتی مرده است اگر که جعبه در کنار دیوار قرار دارد و می تواند هل داده شود اما فقط در راستای دیوار و در جهت یکسان، و هیچ یک از موقعیت هایی که این جعبه می تواند به آن برسد نقطه نمی باشد.

۱.۳: در این تعمیم جعبه در کنار دیوار قرار دارد و می تواند به موقعیتی که دیوار در کنارش قرار نداشته باشد، حرکت داده شود, نقشه ی A در زیر، اما آن موقعیت همسایه ی خالی الف نمی تواند توسط کارگر بعد از هل دادن جعبه به کنار A به دست آید.

این سه مورد می توانند به صورت موضعی و بدون حرکت کردن کارگر تصمیم گیری شوند. بنابراین می توانند در موقعیت ابتدایی بررسی شوند و می توان مکان ها را به عنوان ممنوع مشخص کرد، مثلا با ! ، به گونه ای که یک جعبه هرگز نمی تواند به آن مکان ها هل داده شود.

۱.۴: در تعمیم بعدی، مکان A می تواند توسط کارگر به دست آید اما به قیمت اینکه قرار دادن یک جعبه ی دیگر در یک مکان ممنوع.

این توضیحات بازگشتی می باشد ^[1], یعنی، یک مکان مرده را با استفاده از کلمه های موقعیت مرده مشخص می کند. چنین موقعیت های مرده ای سخت تر قابل تشخیص هستند زیرا که نمی توانند با بازرسی موضعی پیدا شوند و ممکن است تست حرکت ها لازم باشد.

در مورد ۲: فرمول بندی کردن کارهای زیرمجموعه ای

مثال هایی از کارهای زیرمجموعه ای:

1. کارگر را از A به B حرکت دهید،
2. یک جعبه ی مشخص را از A به B حرکت دهید

که هر یک از این کارها قرار است که بدون به وجود آوردن موقعیت مرده به دست آید.

مثالی از: اینکه چگونه کارگر می تواند از یک جعبه برای رسیدن به A بگذرد:

از آنجایی که کارگر باید اطراف جعبه قدم بردارد، همه ی فضای خالی لازم می باشد. اگر فضای خالی کمتری وجود داشته باشد، آنگاه کارگر نمی تواند از جعبه بدون تولید موقعیت مرده بگذرد.

اگر کسی تعداد زیادی ازاین کارهای زیرمجموعه ای را عمیقا با شکل های آنها می داند، آنگاه می تواند زمان زیادی را با صرف نکردن برای فکر کردن درباره ی آن ذخیره کند، در اینجا این مسیر ۹ حرکتی. با اهمیت تر از آن، فکر مردن به اینکه یک کاز غیر ممکن است باعث تسلیم شدن نخواهد شد.

یک سوال مرتبط با کار زیرمجموعه ای این است که چگونه آنها را پیدا کنیم. به عنوان مثال، کارهای زیرمجموعه ای در زمان حل کردن مساله به صورت برعکس پدیدار می شوند. فرض کنید یک نقطه ی مشخص فقط می تواند از یک طرف فقط یک جعبه در دسترسی قرار بگیرد. در نتیجه این جعبه لازم است که در یک جهت خاص حرکت داده شود. برای انجام این کار، ازم است که کارگر به طرف دیگر آن برسد. یک کار می تواند آوردن جعبه و کارگر به موقعیت درست باشد.

یک مثال متداول دیگر از پیدا کردن کارهای زیر مجموعه ای مثال این است: می توان با خیال راحت فرض کرد که همه ی فضای داخل یک موقعیت برای پاسخ لازم است. این به ین معنی است که اگر موقعیت ابتدایی فضای داخلی حجیمی دارد، مثلا ۲ ضربدر ۳ مساحت خالی در مثال بالا، آنگاه می توان پرسید که هدف این فضا چیست. می تواند این باشد که این فضا لازم است برای کارگر که از جعبه ها عبور کند و یا اینکه استفاده می شود برای پارک موقت یک جعبه به فضای خالی در جای دیگر به صورت فوری. بنابراین اگر فضای وسیع قابلیت این را دارد که جعبه را به صورت موقت نگه داری کند آنگاه آن جعبه کدام می تواند باشد؟ چگونه می توان این جعبه را به نقطه پارکیگ میانی رساند؟

درباره ی ۳: فرمولسازی کردن محدودیت ها روی مسیر پاسخ

محدودیت های زیادی روی مسیر پاسخ قرار دارند که با نگاه کردن به موقعیت و بدون امتحان کردن هیچ حرکتی ممکن هستند. به عنوان مثال:

۳.۱: یک راهرو وجود دارد که می توان با یک جعبه وارد آن شد، اما جعبه هیچوقت نمی تواند در طول کل راهرو حرکت کند و در نتیجه فضای انتهایی راهرو هرگز از طرفی که آن به پایان می رسد مورد دسترسی قرار نمی گیرد.

۳.۲: یک نقطه ی خاص فقط می تواند از یک طرف مورد دسترسی قرار گیرد حتی اگر فضای خالی در طرف های دیگر وجود داشته باشد.

۳.۳: یک جعبه ی خاص هرگز نمی تواند در یک جهت خاص خرکت داده شود و در نتیجه فقط می تواند به یک نقطه ی خاص دست یابد.

۳.۴: از آنجایی که نقطه ها می توانند توسط جعبه ها فقط از بعضی طرف ها مورد دسترسی قرار گیرند، این ترتیبی که در آن نقطه ها باید اشغال شوند را تعیین می کند.

۳.۵: این ممکن است که واضح باشد که کدام نقطه لازم است در آخر پوشانده شود، زیرا که فضا برای کارگر لازم است که بتواند جعبه را در یک مسیر خاص هل دهد.

درباره ی ۴: ابتکارهای دیگر

۴.۱: هر دنباله ای از هل دادن ها که بتواند معکوس شودمی تواند و باید امتحان شود، حتی اگر به این معنی باشد که کارگر مجبور است راه طولانی برود تا بتواند از طرف دیگر این هل دادن ها را معکوس کند. حتی اگر همچین تمرینی بی ثمر به نظر آید، موقعیت جدید ممکن است که احتمالات جدیدی را برای چگونگی ادامه دادن باز کند.

۴.۲: اگر یک خط مستقیمی وجود دارد که همه ی نقطه ها را از حداقل یک جعبه جدا کند، آنگاه این جعبه باید از آن خط بگذرد. اگر این ممکن نیست آنگاه موقعیت مرده است. اگر برای جعبه فقط یک راه وجود دارد که از آن خط بگذرد آنگاه این یک محدودیت قوی برای مسیر پاسخ است.

مثالی از پاسخ کامل: بازی ۸

ما مختصات را برای نشانه گذاری نقطه ها معرفی می کنیم. برای مثال، کارگر در آغاز در نقطه ی G1 می باشد.

در آغاز کارگر فقط دو گزینه دارد: الف: الف: رفتن به حفره ی G3 ، یا ب: رفتن به حفره ی E3. رفتن به G3 فقط به کارگر اجازه می دهد که جعبه را در B3 به B1 هل دهد، نتیجه مرگ است. بنابراین کارگر از حفره ی E3 به B2 می رود:

تنها هل دادن هایی که می توانیم اعمال کنیم الف: جعبه ی B3 تا جعبه ی B4 است یا جعبه ی C2 به راست است.

ما تشخیص می دهیم که جعبه ها نمی توانند به نقاط در مسیر G3 حرکت داده شوند زیرا که آنها بعد از همه ی اینها هرگز نمی توانند به چپ حرکت داده شوند (۱.۲ را ببینید).

اما در راستای حرکت دادن آنها از حفره ی B3,C3 ما فضای این ناحیه را احتیاج داریم، بنابراین لازم است یک یا دو جعبه را به راست حرکت دهیم و مجبوریم بعد از همه ی اینها، آنها را برگردانیم.

ما همچنین تشخیص می دهیم که جعبه ی B3 فقط می تواند روی خط B B حرکت داده شود و در نتیجه در نهایت مجبور است که در نقطه ی B4 خاتمه یابد.

برای حرکت جعبه های بعدی روی C4 و آنگاه هل دادن آنها به سمت راست، کارگر باید قادر باشد که به A4 حرکت کند اما برای رسیدن به آنجا از پایین، جعبه ی B3 باید در B2 باشد و فضاهای B3, C3, C2 باید خالی باشند، بنابراین دو جعبه باید از مسیر خارج شوند و در پایینتر سمت راست پارک شوند.

�

اما پایین هل دادن جعبه هایA3 یاB3 نتبجه نخواهد داشت. تنها گزینه ی دیگر که در موقعیت ۲ که داشتیم این است که در ابتدا جعبه ی B3 را تا B4 هل دهیم و آنگاه حرکت هایی را اعمال کنیم که منجر به موقعیت ۳ می شوند. بدست می آوریم

اکنون می توانیم با هل دادن جعبه ی C3 به پایین تا C2 و حرکت کردن با کارگر به اطراف برای هل دادن جعبه ی F2 بهG2 و G3 :

همانطور که در بالا مطرح شد، ما فضاهای B3,C3,C2 را خالی احتیاج داریم و لازم است جعبه ی B4 را پایین تا B2 برسانیم، بنابراین لازم است که جعبه ی C2 به طور موقت روی G2 . پارک کنیم. بدست می آوریم:

اکنون می توانیم نقشه ی اولیه مان را دنبال کنیم و جعبه ی G2 . را در راستای هل دادنش بعدا به سمت راست به C4 . هل دهیم:

سوال این است که چه مقدار به سمت راست باید آن جعبه ی C4 . را هل دهیم. زیراکه هنوز لازم است که جعبه ی G3 را در طول مسیری که لازم است کارگر را به G4 G4 برسانیم، هل دهیم و همچنین جعبه ی C4 را تا F4 هل دهیم و کارگر را به G4 برسانیم با G4 را به G3 هل دهد:

برای هل دادن جعبه ی G2 به چپ، لازم است کارگر تمام راه را در خلاف حرکت عقربه ی ساعت تا H2 برگردد.

از این پس آسان است: جعبه ی G2 بهC2, C4, D4 هل داده می شود

سپس جعبه ی B2 به B4 هل داده می شود و کارگر به G4 حرکت می کند با سرانجام جعبه ی F4 را روی نقطه ی E4 هل دهد.

تمام شد.