حل مکعب روبیک در ۲۰ حرکت

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

الگوریتم الهی مفهومی است که از مباحثی در مورد طریقه حل پازل مکعب روبیک سر چشمه می گیرد.اما علاوه بر این برای دیگر پازل های ترکیبی و بازی های ریاضی نیز بکار برده می شود.این مفهوم به الگوریتم هایی مربوط می شود که راه حلی را ارایه می دهند که کمترین تعداد حرکات را شامل می شوند.این مفهوم بر این تفکر استوار است که یک فرد همه چیز دان یا دانای کل باید مناسب ترین و بهترین گام در هر امری را بردارد.زمانی یک الگوریتم را الگوریتم الهی می نامیم که کاربردی باشد. به این معنا که الگوریتم مورد نظر نیازمند صرف هزینه و زمان طولانی و غیر معمول نباشد. برخی از پازل های شناخته شده ای که در این چهارچوب جای می گیرند پازل های مکانیکی مثل مکعب روبیک، برج های هانویHanoi) (و ۱۵ پازل هستند.

در سال ۱۹۹۷الگوریتمی به عنوان بهترین راه حل برای مکعب روبیک توسط ریچارد کرف ( Richard Korf) منتشر شد. اگر چه پیش از آن در سال ۱۹۹۵ نیز اعلام شده بود که مکعب در سخت ترین حالت به هم ریخته شده خود تنها با ۲۰ حرکت حل می شود. در سال ۲۰۱۰ از طریق محاسبات کامپیوتری گسترده این ادعا بار دیگر به اثبات رسید.بنابراین عدد ۲۰ دقیق ترین و کمترین عدد برای بهترین راه حل مکعب روبیک است. این عدد به عنوان ” عدد الهی” نام گرفته است. مورلی دیویدسون(Morely Davidson)، پروفسور ریاضی از دانشگاه ایالت کنت به نقل از شبکه بی بی سی می گوید: اکنون ما با قاطعیت می گوییم که رقم جادویی حل مکعب روبیک ۲۰ است. این تیم بین المللی با استفاده از یک بانک کامپیوتری در گوگل موفق شدند به این راه حل دست یابند. تعداد موقعیت های به هم ریخته یک مکعب ۴۳۲۵۲۰۰۳۲۷۴۴۸۹۸۵۶۰۰۰ است. این تیم تحقیقاتی عدد فوق را به ۲۲۱۷۰۹۳۱۲۰ گروه ۱۹۵۰۸۴۲۸۸۰۰ تایی تقسیم بندی کردند.

به عبارت دیگر آنها برای سرعت بخشیدن به پردازش همه راههای ممکن برای حل مکعب، تمام احتمالات را به ۲/۲ بیلیون گروه تقسیم کردند که هر گروه شامل تقریبأ ۲۰ بیلیون راه حل بود. پروفسور دیویدسون می گوید: امکان محاسبه تمامی گروهها به هیچ عنوان وجود نداشت.بنابراین برای اینکه محاسبات قابل کنترل و هدایت شوند ما تعداد راه حل ها را با پیدا کردن موارد تکراری و موارد متقارن کاهش دادیم.

در نتیجه این تیم موفق شد تعداد راه حل ها را از ۲۰ بیلیون به ۵۶ میلیون کاهش دهد.به گفته پروفسور دیویدسون هر گروه از اطلاعات را اگر توسط کامپیوتر معمولی قرار بود ذخیره کنند حدود ۲۰-۳۰ ثانیه طول می کشید. به عبارت دیگر ذخیره اطلاعات توسط یک کامپیوتر استاندارد وقت بسیار زیادی را صرف می کرد. در نتیجه این تیم تحقیقاتی تصمیم گرفتند پردازش اطلاعات را توسط یک ابر کامپیوتر انجام دهند. سپس گوگل پا پیش نهاده و مسؤلیت انجام محاسبات را بر عهده گرفت. در پایان این پروژه پروفسور دیویدسون و تیم همراهش اعلام کردند که رقم الهی برای مکعب روبیک ۲۰ است. این پروژه توسط John Dethridge مهندس گوگل، Herbert Kosiemba مدرس ریاضی، و Tomas Rokickiیک برنامه نویس اهل کالیفرنیا انجام شد. هم اکنون این تیم تحقیقاتی توجه خود را معطوف نسخه چهار لایه ای مکعب کرده و در آینده به تمامی مسایل ریاضی مرتبط با مکعب خواهند پرداخت.