دانشمندان جایزه‌ی ۱ میلیون دلاری برای فردی که موفق به حل معمای کلاسیک پیچیده‌ی شطرنج که معمای کوئینز یا معمای چند وزیر نام دارد، تعیین کرده‌اند.
زیبایی این معما در این است که برای حل آن، نیازی نیست تمام قوانین شطرنج را بدانید؛ اما این مسأله به معنای آسان بودن آن نیست. در حقیقت پژوهشگران عقیده دارند پیچیدگی ریاضی این معنا به حدی است که حل کردن آن ممکن است هزاران سال به طول انجامد.
برای فهم بیشتر، بهتر است از ابتدا مسأله را بررسی کنیم.
معمای کوئینز (Queen’s Puzzle) که با نام معمای هشت وزیر نیز شناخته می‌شود، ابتدا در سال ۱۸۴۸ منشتر شد؛ در این معما، ۸ وزیر در خانه‌های ۸×۸ یک صفحه‌ی شطرنج قرار می‌گیرند، به گونه‌ای که هیچ‌کدام از آنان توسط وزیر دیگر تهدید نشوند. در صورتی که قوانین شطرنج را بدانید، خواهید دانست که وزیر قوی‌ترین مهره‌ی موجود روی صفحه است که می‌تواند در ۸ جهت حرکت کند؛ بالا، پایین، هر دو طرف و مورب و محدودیتی برای آن وجود ندارد. همین حرکات بدون محدودیت علت دشواری معمای ۸ وزیر هستند که ریاضی‌دانان و شطرنج‌بازان با آن مواجه‌اند.
در حقیقت ۹۲ شیوه‌ی مختلف برای حل معما و نزدیک به ۴.۵ بیلیون شیوه‌ی مختلف برای آرایش قرارگیری مهره‌ها در صفحه وجود دارد.
حال تصور کنید دامنه‌ی حرکت و صفحه را گسترش دهیم؛ به جای صفحه‌ی محدود و استاندارد ۸×۸ که در مجموع ۶۴ خانه دارد، بعدهای دیگری اضافه کنیم و در صفحه‌ای سه بعدی با هر تعداد ملکه مسأله را گسترش دهیم و یا در صفحه‌ای دوبعدی، برای مثال، ۲۰ وزیر را در خانه‌های ۲۰×۲۰ یا ۱۰۰ وزیر را در خانه‌های ۱۰۰×۱۰۰ قرار دهیم و بدین ترتیب، برای تعداد n از وزیرها، به خانه‌هایی n x n نیاز دارید تا معمای دست نیافتنی بسازید!
این مجموعه از معما را در دنیای علم، n-Queens puzzle می‌نامند. به جای n، هر عدد طبیعی می‌تواند قرار گیرد. حتی با استفاده از کامپیوترهای بسیار قدرتمند نیز حل این معما با دشواری بسیاری همراه است.
چالش‌برانگیز بودن معما با اضافه کردن پیچیدگی‌های جانبی افزایش می‌یابد؛ برای مثال، می‌توان امکان حرکت چند وزیر را در صفحه، سلب کرده و جاهای ثابتی برای آنان در نظر گرفت. دانشمند کامپیوتر، ایان جنت۱ از دانشگاه سنت اندروزِ بریتانیا۲ توضیح می‌دهد:
پژوهش‌های جدید نگرانی‌هایی در رابطه با معمای n-Queens وجود دارد؛ چرا که نه تنها می‌تواند ابعاد صفحه و تعداد وزیرها را افزایش داد، بلکه می‌توان جایگاه برخی وزیرها را ثابت کرد. آیا می‌توانید در این صورت پاسخ این معما، بدون جابه‌جا کردن چند وزیر، را بیابید؟
تصور این شیوه شاید چندان در تئوری مشکل نباشد؛ اما حل آن در واقعیت یکی از دشوارترین پیچیدگی‌های محاسباتی است.
به همین دلیل، جنت و همکارانش به طراحی برنامه‌ای کامپیوتری می‌اندیشند که توانایی حل انواع مختلف این معما را در زمانی کوتاه داشته باشد؛ چرا که کامپیوترهای معاصر قادر به حل آن نیستند. جنت اضافه می‌کند:
در صورت نوشتن برنامه‌ای که قادر باشد این مسأله را به سرعت حل کند، می‌توان آن را به گونه تغییر داد که بسیاری از مشکلات روزانه را نیز با این قدرت حل کند؛ برخی از این چالش‌ها عبارتند از مدیریت گروه بزرگی از دوستان فیس‌بوکتان که یکدیگر را نمی‌شناسند یا مسائل مهم‌تری نظیر نظیر کرک کدهایی که کلیه‌ی تعاملات اینترنتی ما را امن نگه می‌دارند.
به همین دلیل است که مؤسسه‌ی ریاضیاتِ کِلِی جایزه‌ای ۱ میلیون دلاری برای شخصی که بتواند این معما را حل کند، در نظر گرفته است؛ پس از آن که تیم جنت مقاله‌ای جدید منتشر کردند که اعلام کرده است معمای n-Queens نمونه‌ای از چیزی است که P vs NP Problem نامیده می‌شود. بدین معنا که هر الگوریتمی که بتواند آن را حل کند، به شکل غیرمستقیم هر مشکلی را که در دسته‌ی NP قرار می‌گیرد را نیز حل می‌کند. این جایزه در دو صورت می تواند به شخص برنده اهدا شود:
- در صورتی که بتواند ثابت کند الگوریتمی برای حل معما در یک مدت منطقی وجود ندارد
- در صورتی که الگوریتمی ابداع کند که در زمان کوتاهی معما را حل کند؛ در اصطلاح ریاضی، polynomial time شناخته می‌شود.
در صورتی که به دنبال این جایزه هستید، جنت می‌گوید برای آن که فردی شانس برنده شدن آن را داشته باشد باید فوق‌العاده باهوش و مدرک PhD در پیچیدگی‌های محاسباتی داشته باشد!
پیتر نایتینگل۳، از پژوهشگران مجموعه اضافه می‌کند:
همه‌ی این‌ها در تئوری است؛ در واقعیت، هیچ‌کس تا کنون موفق نشده است برنامه‌ای بنویسد که با سرعت بتواند معما را حل کند؛ بنابراین تا جایی که پژوهش‌های ما نشان می‌دهند، انجام‌پذیر نیست.
آیا داوطلبی وجود دارد به آنان نشان دهند اشتباه می‌کنند؟
این نتایج در Journal of Artificial Intelligence Research منتشر شده‌اند.
پی‌نوشت
۱. Ian Gent
۲. St Andrews
۳. Peter Nightingale
سلام من راهش رو بلدم بسیار ساده و دقیق میتونی کمک کنی کلی وقت گزاشتم چطور باهاشون باید تماس گرفت