مقاله زیر از قسمت  Math Trek سایت انجمن ریاضی آمریکا انتخاب شده و نویسنده آن  Ivars Peterson است. لینک این مقاله در زیر موجود است.

http://www.maa.org/news/mathtrek.html

حرکت به اطراف

در اینجا ما یک معمای به ظاهر ساده داریم .

طراح :  Courtesy of Robert A. Hearn

چهار  سکه  روی دایره های ردیف آخر(G،D،E و R)  قرار دهید و حروف MARTIN را بدون پوشش بگذارید. وظیفه شما این است ، این چهار سکه را از مسیر هایی که دایره ها به هم وصل می شوند طوری حرکت دهید که چهار دایره بالایی (M،T،I و دایره خالی) را بپوشاند و حروف GARDNER  بدون پوشش باقی بماند.

ساده به نظر می رسد؟ اما قانونی که باید رعایت شود این است که هیچ زمانی دو سکه اجازه ندارند در دایره های کناری یکدیگر که توسط یک مسیر به هم مربوط می شوند قرار گیرند. بعنوان مثال در ابتدا شما نمی توانید سکه یG را تکان دهید زیرا تنها حرکت مجاز برای این سکه آن را در کنار سکه ی D قرار می دهد. سکه D می تواند به دایره T رود ولی نمی تواند به دایره ی A یا دایره ی I برود. شما همچنین مجبور ید هر بار سکه را یک مرتبه در هر مسیر(یک یال)  از یک دایره به دایره دیگر حرکت دهید .و جایی که دو مسیر از روی یکدیگر برخورد می کنند ، شما نمی توانید از یک یال به یال دیگر تعویض مسیر داشته باشید.

Robert A Hearn یکی از دانشجویان فارغ تحصیل از آزمایشگاه هوش مصنوعی دانشگاه MIT ، این بازی را به افتخار  Martin Gardner ریاضیدان نابغه طراحی کرده است. در بازی های متداولی  که بر پایه حرکت دادن سکه ها است یک مجموعه از سکه ها که با ترکیب خاصی در بیرون چیده شده اند باید با کمترین حرکت ممکن به وضعیتی جدید جا به جا شوند("معما های حرکت سکه ها" را در اینجا ببینیدhttp://www.sciencenews.org/articles/20030201/mathtrek.asp).این نکته برای این قبیل بازی ها ثابت شده که همیشه تعیین اینکه این معما ها قابل حل است یا نه  براحتی قابل محاسبه است .

معمای  حرکت سکه هایMartin Gardner  که به Hearn متعلق است اگرچه موجودی تا حدودی متفاوت ،است.ولی نسبت به سایر معما های متداول حرکت سکه ها ، بیشتر شبیه به معما های نفرت انگیز بلوک های لغزنده 14-15است (" منطق در بلوک ها " را در اینجاhttp://www.sciencenews.org/articles/20020817/bob10.asp ببینید.)

برای حل معمای Martin Gardner 25 حرکت اتفاق می افتد .به دنبال اکتشاف اینکه چقدر این معما ها می توانند سخت باشند Hearn کشف کرد که یک راه ساده برای تولید مثال هایی که به اندازه دلخواه سخت باشند وجود دارد . واقعاً ساختن معماهایی که بررسی قابل حل بودن آنها از راه محاسبه خیلی دشوار باشد، آسان است.

در حالت رسمی تر ، این بر می گردد به گونه جدیدی از معما های Hearn  که به دسته مسائل محاسباتی ای  تعلق دارد که تحت عنوان PSPACE-complete توصیف می شوند. این به این معنی است که شما باید انتظار داشته باشید که هنگامیکه تعداد دایره ها و مسیرها افزایش یابد ، مقدار زمانی که کامپیوتر لازم دارد تا این مسائل را حل کند به صورت توانی افزایش یابد ، اگر چه مقدار حافظه مورد نیاز تنها به  صورت جبری  افزایش می یابد.

این هم یک مسئله دیگر برای تلاش بیشتر شما :

چهار سکه بر روی دایرهای قرمز قرار دهید سپس سکه ها را در طول مسیر ها طوری حرکت دهید که بر روی هر دایره ستاره دار یک سکه قرار بگیرد .با این شرط که هیچ زمان نباید دو سکه ، دو دایره مجاور که با یک مسیر به هم وصل هستند را اشغال کنند.شما باید قادر باشید که این معما را با 28 حرکت حل کنید.

طراح: Bob Hearn

  Hearn شماری از تغییرات را امتحان کرد ، مانند استفاده از نشان یا سکه هایی از رنگ های متفاوت    Hearn می گوید :"بنابراین ترکیب شروع و ترکیب پایانی نشان ها  مکان های مشخصی را برای هر نشان دارد ".

این کار معماهای امکان پذیر پیچیده تری را بر روی گراف های کوچکتر می سازد."از نظر ریاضیاتی یک گراف آرایه ای از رئوس یا گره ها (دراین مورد دایره ها راس هستند) است که بوسیله یال ها (مسیر ها) به هم وصل می شوند).

 در این معما  هر کدام از این 4 نشان رنگ متفاوت با بقیه دارد ، در ابتدا همانطور که با نقطه های رنگی نشان داده شده اند  قرار گرفته اند(م . یعنی هر نقطه نماینده یک نشان است). هدف شما حرکت هر نشان به سمت فضایی است که دایره همرنگ با آن نشان را دارد.حل تنها این معما به 116 حرکت نیاز است.

معمای حرکت سکه ی Martin Gardner همچنین الهام بخش James Stephens هم بود کسی که وب سایت PuzzleBeast را راه اندازی کرد http://www.puzzlebeast.com/ و برای ایجاد یک مجموعه از معما هایی که "Meandering Monk Maze." نامیده می شوند بصورت on line از این سایت استفاده کنید.

 http://www.puzzlebeast.com/monkmaze/index.html

لینک فایل PDF معما های اضافی که توسط Bob Hearn طراحی شده

http://www.maa.org/mathland/more-puzzles.pdf

مراجع:

Demaine, E.D., and M.L. Demaine. 2005. Sliding-coin puzzles. In Tribute to a Mathemagician, B. Cipra, E.D. Demaine, M.L. Demaine, and T. Rodgers, eds. Wellesley, Mass.: A K Peters.

Gardner, M. 2005. Martin Gardner's Mathematical Games: The Entire Collection of His Scientific American Columns. Washington, D.C.: Mathematical Association of America.

Hearn, R.A. 2005. The complexity of sliding-block puzzles and plank puzzles. In Tribute to a Mathemagician, B. Cipra, E.D. Demaine, M.L. Demaine, and T. Rodgers, eds. Wellesley, Mass.: A K Peters.

Peterson, I. 2003. It's not you, it's the puzzle. Muse 7(March):21. Available at http://www.sciencenewsforkids.org/pages/puzzlezone/muse/muse0303.asp.

______. 2003. Sliding-coin puzzles. MAA Online (Feb. 3).

______. 2002. Logic in the blocks. Science News 162(Aug. 17):106-108. Available at http://www.sciencenews.org/articles/20020817/bob10.asp.

برای اینکه مطالب بیشتری راجع به پیچیدگی محاسباتی این قبیل بازی ها یاد بگیرید به لینک زیر مراجعه کنید.

http://www.ics.uci.edu/~eppstein/cgt/hard.html.

اطلاعاتی راجع به مثال هایی از معما های بلوک های لغزنده در لینک زیر قابل دسترسی است.

http://www.puzzleworld.org/SlidingBlockPuzzles/default.htm.

"Meandering Monk Maze"      الهام گرفته شده ازمعماMartin Gardner  

http://www.puzzlebeast.com/monkmaze/index.html

Bob Hearn در لینک زیر وب سایت دارد.

http://www.swiss.ai.mit.edu/~bob/