معمای قطار | مانور قطارها را چگونه انجام دهیم؟

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

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

معمای قطار

یک لوکوموتیو (که با B نمایش داده شده) یک واگن را (که با A نمایش داده شده)‌ می‌کشد و از سمت چپ به راست می‌برد. لوکوموتیو دیگری (که با C نمایش داده شده) یک واگن را (که با D نمایش داده شده) می‌کشد و از سمت راست به چپ می‌آید. این دو لوکوموتیو روی یک خط هستند و به هم می‌رسند. یعنی عملا متوقف می‌شوند و نمی‌توانند به مسیرشان ادامه دهند.

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

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

روش رایج برای حل چنین مسائلی – که در ایستگاه‌های راه‌آهن زیاد اتفاق می‌افتد) مانور دادن قطارهاست. ویژگی‌های مانور به صورت زیر است:

• لوکوموتیو‌ها و واگن‌ها را به سادگی می‌توان از هم جدا کرد یا دوباره به هم وصل کرد.
• لوکوموتیوها هم می‌توانند واگن‌ها را بکشند و هم هل دهند (در فواصل محدود ایستگاهی این کار مجاز است).
• اگر لازم بشود لوکوموتیوها را می‌توان خاموش و مثل یک واگن معمولی به قطار بست (که لوکوموتیو دیگری آن را بکشد).
• همهٔ لوکوموتیو‌ها و واگن‌ها هم از جلو قلاب دارند و هم از عقب و از هر دو طرف می‌شود آن‌ها را به هم وصل کرد.

حالا سوال این‌جاست که چگونه و در چند حرکت می‌توانید قطارها را جوری جابه‌جا کنید که دو قطار از روی هم رد شوند. یعنی لوکوموتیو B در سمت راست قرار بگیرد و A را با خود بکشد و برود و لوکوموتیو C هم در سمت چپ قرار بگیرد و D را با خود ببرد (شکل زیر):