یافتن الگوریتمی برای حل معمای وزیرها

این معما به معمای «تکمیل وزیرها» (  n-Queens Completion ) معروف است و محققان اسکاتلندی معتقدند اگر برنامه‌‌ای کامپیوتری بتواند این معما را به بهترین شکل ممکن حل کند، توانایی لازم برای حل مشکلات اساسی‌تر  نظیر شکستن رمزهای امنیتی را که در حال حاضر غیرممکن به نظر می‌رسند خواهد داشت.

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

این معما زمانی توجه Ian Gent استاد کامپیوتر دانشگاه سنت‌اندروز (University of St Andrews ) را به خود جلب کرد که یکی از دوستانش در فیس‌بوک او را با این معما به چالش کشید. این گروه دریافتند اگر صفحه شطرنج هزار ستون و هزار سطر داشته باشد، برنامه‌های کامپیوتری در مقابل حجم بسیار بالای گزینه‌های موجود ناتوان خواهند بود. پروفسور Gent معتقد است: « اگر موفق به نوشتن برنامه‌ای شوید که این معما را به سرعت حل کند، می‌توانید آن برنامه را برای رفع بسیاری از مشکلات جدی‌تر نیز تعمیم دهید». حل بسیاری از مسائل نظیر شکستن کدهای امنیتی از این جهت برای کامپیوترها دشوار است که در این موارد با گزینه‌های زیادی مواجه هستند که باید آن‌ها را در نظر بگیرند و اینکار سال‌ها زمان می ‌برد.  برای کسب این جایزه، متقاضی دو راه پیش رو دارد؛ یا الگوریتمی ارائه دهد که این معما را در زمانی معقول حل کند یا اینکه ثابت کند برای حل این معما چنین الگوریتمی وجود ندارد.