زومیت/ مسئله‌ی n وزیر درباره‌ی یافتن روش‌های مختلفی برای جایگذاری وزیرهای مختلف روی یک صفحه‌ شطرنج است؛ به‌طوری‌که هیچ‌کدام به یکدیگر حمله نکنند. ریاضیدانی به نام مایکل سیمکین توانست پس از ۱۵۰ سال این مسئله را حل کند.

اگر در خانه‌ی خود صفحه‌ی شطرنج دارید سعی کنید این تمرین را انجام دهید: هشت وزیر را روی صفحه به‌گونه‌ای قرار دهید که هیچ‌کدام به یکدیگر حمله نکنند. اگر برای بار اول موفق شدید آیا می‌‌توانید ترکیب دوم را پیدا کنید؟ چه تعداد ترکیب وجود دارد؟

چالش فوق بیش از ۱۵۰ سال قدمت دارد. قدیمی‌ترین نسخه‌ی این مسئله، مسئله‌ی ریاضی n وزیر نامیده می‌شود که مایکل سیمکین، پژوهشگر فوق دکترای مرکز کاربردها و علوم ریاضی دانشگاه هاروارد، در ماه جولای راه‌حل آن را در مقاله‌ای منتشر کرد. در اینجا به جای جایگذاری هشت وزیر روی یک صفحه‌ی شطرنج استاندارد، هشت در هشت (که در آن ۹۲ ترکیب‌بندی مؤثر متفاوت وجود دارد)، مسئله می‌پرسد چه تعداد روش برای جایگذاری n وزیر روی یک تخته‌ی n در n وجود دارد. n می‌تواند ۲۳ وزیر روی تخته‌‌ی ۲۳ در ۲۳ یا ۱۰۰۰ وزیر روی تخته‌ی ۱۰۰۰ در ۱۰۰۰ یا هر عدد دلخواه دیگری متناظر با صفحه‌ی شطرنج باشد.

سیمکین ثابت کرد برای صفحات شطرنج بزرگ با تعداد بالای وزیر، تقریبا (0.143n) به توان n ترکیب وجود دارد. در نتیجه روی صفحه‌ای به ابعاد یک میلیون در یک میلیون، تعداد روش‌های ترکیب‌بندی یک میلیون وزیر غیرتهدید‌کننده برابر است با عدد ۱ همراه با پنج میلیون صفر.

مسئله‌ی اصلی با صفحه‌ی شطرنج ۸ در ۸ برای اولین بار در یک مجله‌ی شطرنج آلمانی در سال ۱۸۴۸ مطرح شد. در سال ۱۸۶۹ مسئله به n وزیر تعمیم پیدا کرد. از آن زمان ریاضیدان‌ها به نتایج متعددی درباره‌ی مسئله‌ی n وزیر رسیدند. اگرچه پژوهشگران قبلی توانستند با شبیه‌سازی‌های کامپیوتری نتیجه را حدس بزنند، اما این سیمیکن بود که توانست مسئله را اثبات کند. به گفته‌ی شان ایبرهارد، پژوهشگر فوق دکترای دانشگاه کمبریج، سیمکین اثبات مسئله را به شیوه‌ای دقیق‌تر از افراد قبلی ارائه داد.

یکی از موانع حل مسئله‌ی n وزیر نبود راه‌های واضح برای ساده‌سازی آن است. حتی در تخته‌ای نسبتا ساده، تعداد ترکیب‌های احتمالی وزیر بسیار بالا است. در تخته‌های بزرگ‌تر مقدار محاسبات بسیار پیچیده و عظیم خواهد شد. در چنین موقعیتی ریاضی‌دان‌ها امیدوار هستند به الگو یا ساختاری اساسی دست پیدا کند که امکان تجزیه‌ی محاسبات به بخش‌های کوچک‌تر را بدهد؛ اما مسئله‌ی n وزیر هیچ‌کدام از این راه‌ها را پیش روی پژوهشگران نگذاشت.
این پیچیدگی از این حقیقت سرچشمه می‌گیرد که کل فضاهای روی یک صفحه به صورت برابر ایجاد نمی‌شوند. برای پی بردن به دلیل این مسئله، ساخت آرایش هشت وزیری را در نظر بگیرید. اگر اولین وزیر را نزدیک به مرکز قرار دهید، می‌تواند به هر فضایی در سطر، ستون خود یا در راستای قطرهای صفحه حمله کند. به این ترتیب، ۲۷ فضای خارج از محدوده‌ برای وزیر بعدی باقی می‌ماند؛ اما اگر وزیر اول را در گوشه‌ی تخته قرار دهید تنها می‌تواند ۲۱ فضا را تهدید کند؛ زیرا قطرهای مرتبط کوتاه‌تر می‌شوند. به بیان دیگر، مربع‌های گوشه و مرکز متمایز هستند و در نتیجه صفحه فاقد ساختار متقارنی است که باعث ساده‌ شدن مسئله شود.

به دلیل پیچیدگی‌های یادشده سیمکین حدود چهار سال قبل، همکاری خود را با ریاضی‌دانی به نام زور لوریا از مؤسسه‌ی فناوری زوریخ سوییس آغاز کرد؛ آن‌ها در نهایت مسئله‌ی متقارن و چنبره‌ای n وزیر را ارائه کردند. در نسخه‌ی تغییریافته، تخته‌ی شطرنج مانند یک چنبره دورتادور خود می‌پیچد. اگر به سمت راست حرکت کنید، مجددا در سمت چپ ظاهر خواهید شد. مسئله‌ی چنبره‌‌‌ای به دلیل وجود تقارن ساده‌تر به‌نظر می‌رسد. بر خلاف تخته‌ی کلاسیک، تمام قطرها طول یکسانی دارند و هر وزیر می‌تواند به تعداد یکسانی از فضاها (۲۷ فضا) حمله کند.

سیمکین و لوریا تلاش کردند آرایش‌های روی تخته‌ی چنبره‌ای را با استفاده از دستورالعملی دو بخشی بسازند. در هر مرحله یک وزیر را به‌صورت تصادفی در فضایی با احتمال برابر قرار دادند. سپس تمام فضاهای احتمالی حمله را مسدود کردند. آن‌ها امیدوار بودند با ردیابی تعداد گزینه‌ها در هر مرحله بتوانند به یک کران پائین (حداقل مطلق تعداد ترکیب‌ها) برسند. به این استراتژی الگوریتم تصادفی حریصانه می‌گویند که برای حل تعداد زیادی از مسائل در حوزه‌ی ترکیبات به کار می‌رود.
تقارن تخته‌ی چنبره‌ای برای سیمکین و لوریا به نقطه‌ی شاخص مهمی در حل مسئله تبدیل شد. اما نسخه‌ی چنبره‌ای آزادی کمتری داشت و آن‌ها را به اشتباه انداخت. در صفحه‌ی شطرنج کلاسیک، اغلب وزیرها به کمتر از ۲۷ فضا دسترسی دارند؛ در نتیجه انعطاف بیشتری برای ساخت ترکیب‌ها وجود دارد.
سیمکین و لوریا در نهایت نتوانستند فضایی را برای چند وزیر آخر در یک ترکیب معین پیدا کنند و پیشرفت آن‌ها در حل مسئله‌ی چنبره‌ای در همین‌جا متوقف شد. در نهایت هر کدام روی پروژه‌های دیگری کار کردند؛ اما سیمکین متوجه شد روشی که برای مسئله‌ی چنبره‌ای ناموفق بود برای تخته‌ی شطرنج عادی قابل حل است. او می‌گوید:

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

به دلیل محدودیت‌های یادشده، سیمکین و لوریا کران پائینی معلومی را برای مسئله توسعه دادند. آن‌ها در ماه می نتایج را منتشر کردند؛ اما سیمکین به فکر کردن درباره‌ی مسئله ادامه داد. او در نهایت توانست الگوریتم حریصانه‌ی تصادفی را برای محیط نامتقارن تخته‌ی شطرنج n در n تطبیق دهد. درک کلیدی او این بود که هر چقدر وزیرها در ترکیب n وزیری دورتر باشند احتمال اشغال مربع‌ها توسط آن‌ها افزایش می‌یابد. او می‌گوید:
متوجه شدم می‌توان از عدم تقارن صفحه‌ی شطرنج به سود خود مسئله استفاده کرد.
از آنجا که وزیرهای وسط صفحه‌ به فضاهای بیشتری حمله می‌کنند، اغلب ترکیب‌ها وزیرهای بیشتری را در گوشه‌ی صفحه‌ی قرار می‌دهند تا مرکز آن. در نتیجه سیمکین برای صفحاتی با ۱۰۰ فضا یا بیشتر در هر گوشه به این نتیجه رسید که این ترکیب‌ بر احتمالات دیگر غلبه می‌کند. تقریبا در تمام ترکیب‌ها وزیر به شیوه‌ای مشخص توزیع می‌شود؛ به‌طوری‌که تعداد کمتری از وزیرها در مرکز صفحه و تعداد بیشتری از آن‌ها در کنار قرار می‌گیرند. سیمکین فقط نیاز داشت وزن دقیق برای تخصیص هر مربع را هنگام تخصیص تصادفی هر وزیر پیدا کند.

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

در نهایت سیمکین با روشی به نام انتروپی ثابت کرد این فرمول صرفا بیش از یک مقدار حداقل است. او توانست مقدار حداکثر ترکیب‌ها را با ردیابی تعداد فضاهایی که پس از افشای موقعیت وزیر جدید مورد حمله قرار نگرفتند، محاسبه کند. این مقدار حداکثر کاملا منطبق با حداقل بود و در نهایت سیمکین به تعداد واقعی ترکیب‌های n وزیر رسید. اثبات سیمکین شفاف‌ترین راه‌حلی است که تاکنون برای این مسئله ارائه شده است.
ریاضی‌دان‌ها همچنان به بازی با این مسئله ادامه خواهند داد و سعی می‌کنند این محدودیت‌ها را به یکدیگر نزدیک‌تر کنند. گرچه نتیجه‌ی سیمکین بخش زیادی از راز این مسئله را حل کرده است. مقاله‌ی سیمکین تنها بخشی از تلاش‌ها برای حل مسائل مشابه است. اخیرا کاندیدا بوتل و پیتر کیواش از دانشگاه آکسفورد به راه‌حلی مشابه برای حل مسئله‌ی چنبره‌ای n وزیر رسیدند. این مقاله هنوز به‌طور کامل در دسترس نیست. همچنین تعداد دیگری مسئله‌ی باز در حوزه‌ی ترکیب‌ها وجود دارند که می‌توان از ایده‌ی پژوهش‌ها برای حل آن‌ها استفاده کرد.

به پیج اینستاگرامی «آخرین خبر» بپیوندید
instagram.com/akharinkhabar