شمارش تمامی جواب های معمای n وزیر

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

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

 

حال سوال این است که چه تعداد از این حالت‌ها در یک صفحه \(n \times n\) ممکن است؟ تعداد حالت‌های انتخاب \(n\) خانه برای چیدن \(n\) وزیر ترکیب \(n\) از \(n^2\) یا \(C(n^2,n)\) است که حتی شمارش آن برای تعداد مهره‌های کم نیز کار آسانی به نظر نمی‌رسد. اجازه دهید مساله را ساده‌تر کنیم. فرض کنید مقدار \(n\) را برابر ۸ قرار می‌دهیم. بنابراین ۸ مهره وزیر را در یک صفحه ۸ در ۸ با شروط قید شده بایستی قرار دهیم. به عبارتی، ترکیب ۸ از ۶۴ حالت را بایستی بررسی کنیم! یعنی ۴۴۲۶۱۶۵۳۶۸ حالت! جالب است بدانیم که از بین این تعداد حالت تنها ۹۲ حالت منحصر بفرد برای معمای ۸ وزیر وجود دارد!

در این پست قصد داریم از رویکرد برنامه‌ریزی محدودیت constraint programming برای حل این معما استفاده کنیم. جهت آشنایی ابتدایی با این روش به این پست مراجعه کنید. ابتدا فضای شدنی را با استفاده از متغیر \(x\) که هر آیتم آن نشان‌دهنده جایگاه وزیر در ستون‌های مختلف باشد، تشکیل می‌دهیم:

$$x=(5,8,4,1,3,6,2,7)$$

به عبارتی، عدد ۵ نشان‌دهنده این است که اولین مهره وزیر را در ستون اول و سطر پنجم قرار دهیم. یا عدد ۳ نشان‌دهنده این است که پنجمین وزیر را در ستون پنجم و سطر سوم قرار دهیم. واضح است که جایگشتی از اعداد ۱ تا ۸ در این بردار آورده شده است. برای تولید چنین فضای جایگشتی از محدودیت سراسری allDifferent(x) استفاده می‌شود. این محدودیت به صورت خودکار از قرارگیری دو یا چند مهره وزیر در یک سطر جلوگیری می‌کند. ولی برای این که دو مهره به در اریب همدیگر قرار نگیرند بایستی محدودیت‌های x[i] - x[j] != i - j  و x[i] - x[j] != j - i به ازای \(i \in \{1,\ldots,8\}\) به مدل تزریق شوند. برای مدل‌سازی این مساله از پکیج cp optimizer نرم‌افزار CPLEX استفاده می‌کنیم. تنها کافی است عبارت using CP را در سربرگ کد قرار دهیم.

using CP;
int NUUM_CELL = 8;
range set_column = 1..NUUM_CELL;

dvar int x[set_column] in 1..8;

subject to {

allDifferent(all(i in set_column) x[i]);
forall(i,j in set_column:i>j) {
x[i] - x[j] != i - j;
x[i] - x[j] != j - i;
}
}

در ادامه نوع جستجو را DepthFirst و تعداد جستجوگرها Workers را برابر عدد یک قرار می‌دهیم. این تنظیمات باعث می‌شود یک جواب دوبار شمرده نشود. دستور cp.next موتور جستجوگر را در لحظه یافتن یک جواب شدنی متوقف کرده و پس از انجام عملیات بعدی، به جستجوی خود تا یافتن آخرین جواب شدنی ادامه می‌دهد.

main {
cp.param.SearchType = "DepthFirst";
cp.param.Workers = 1;
thisOplModel.generate();
cp.PLEASE_PURCHASE();
var k=1;
while (cp.next()) {
writeln(k, "th solution");
k++;
}
cp.endSearch(); 
}

 

و تمامی ۹۲ حالت ممکن!

 

 

جهت حمایت از توسعه سایت و تولید محتوا،‌ این کد این مساله را خریداری نمایید.

0 نظرات
بازخورد (Feedback) های اینلاین
View all comments