توصیه‌هایی در مورد روش انجام بازی سوکوبان

علامت‌گذاری

در این دستورالعمل از اصطلاحات زیر استفاده می‌شود :

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

استراتژی کلی

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

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

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

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

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

۱.۳ : در یک حالت پیچیده‌تر، جعبه در کنار دیوار قرار دارد و می‌تواند به وضعیتی که دیوار در کنارش نباشد، حرکت داده شود, (مکان A در شکل زیر)، اما بعد از هل دادن جعبه به مکان A کارگر نمی‌تواند به فضای خالی مجاور A برود.

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

۱.۴: در وضعیت پیچیده تر بعد، کارگر می‌تواند به مکان A برود اما برای این کار باید یک جعبه دیگر را در یک مکان ممنوع قرار دهد.

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

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

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

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

که هر یک از این کارها نباید باعث به وجود آمدن وضعیت مرده بشوند.

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

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

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

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

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

درباره ۳ : فرمول‌بندی محدودیت‌ها روی مسیر جواب

محدودیت‌های زیادی برای مسیر جواب وجود دارند که با نگاه کردن به وضعیت و بدون امتحان کردن هیچ حرکتی ممکن هستند. به عنوان مثال :

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

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

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

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

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

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

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

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

مثالی از یک جواب کامل (بازی ۸)

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

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

تنها هل دادن هایی که می‌تواند انجام شود : الف) جعبه B3 تا جعبه B4 (نه تا B5 که یک وضعیت مرده است) و یا ب ) جعبه C2 به سمت راست.

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

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

ما همچنین تشخیص می‌دهیم که جعبه B3 فقط می‌تواند روی خط 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 برسانیم، هل دهیم و همچنین جعبه C4 را تا F4 هل دهیم و کارگر را به G4 برسانیم تا اینکه G4 را به سمت G3 هل دهد :

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

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

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

انجام شد.