شمارش تعداد جواب‌های مربع جادویی در CP Optimizer

 

 

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

مربع‌های جادویی بالغ بر ٣٠٠٠ هزار سال مورد مطالعه و بحث ریاضی‌دانان بوده‌اند. اولین مربع جادویی باقی‌مانده متعلق به تمدن چینی‌ها در ٢٢٠٠ سال پیش از میلاد مسیح است. در قرن نهم منجمان عرب از آن برای محاسبه جداول ساعات روزانه استفاده می‌کردند. اعتقادات بر این بوده‌است که مربع جادویی پایه‌های نجومی و پیش‌گویی دارد و پیش گوها از آن برای اندازه‌گیری طول عمر یا جلوگیری از بیماری استفاده می‌کردند. در سال ۱۵۱۰ میلادی هاینریش کورنلیوس آگریپا در کتاب فلسفه علوم خفیه از متون هرمسی برای کشیدن مربع‌های جادویی هفت سیاره استفاده کرده است (آن‌ها اعتقاد داشتند که مربعهای جادویی در ابعاد بین ۳ تا ۹ در ارتباط با هفت سیاره اصلی منظومه شمسی شناخته می‌شدند). امروزه از مربع‌های جادویی در معماری‌های کامپیوتر و سایر علوم پایه استفاده می‌شود.

مربع جادویی جدولی است \( n \times n \) خانه، که خانه‌های آن با عددهای مثبت از ۱ تا \( n^2 \) به ترتیبی پر شده‌ است که مجموع عددهای هر ردیف افقی یا هر ستون عمودی یا هر قطر آن، عددی ثابت را نشان دهد. به عنوان مثال یک ماتریس \( ۳ \times 3 \) در زیر قابل مشاهده است:

همانطور که مشاهده می‌شود مجموع عددهای هر ردیف افقی یا هر ستون عمودی یا هر قطر آن دقیقا برابر ۱۵ است. هم‌چنین مجموع آنها از رابطه‌ی زیر حاصل می‌شود.

 $$ \frac{ n(n^2+1)}{2} = \frac{ 3(3^2+1)}{2} = 15$$

در ابتدا برای فراخوانی دستورات cp optimizer در محیط cplex دستور زیر در ابتدای فایل mod. قرار داده می‌شود.

using CP;

پارامترها، متغیرها و محدودیت‌های مساله به شرح زیر است. مدل دربردارنده چهار محدودیت محلی به فرم جمع ستون‌ها، جمع سطرها، جمع قطر اصلی و جمع قطع فرعی است. محدودیت سراسری allDifferent نیز وظیفه‌ی تخصیص اعداد متفاوت به سلول‌های جدول را بر عهده دارد.

int N = ...;
int sumN = N*(N*N+1) div 2;
int Npower = N*N;
range Nrange = 1..N;
range Xrange = 1..Npower;

dvar int x[Nrange][Nrange] in Xrange;

subject to {
  forall(i in Nrange)
    sum(j in Nrange) x[i][j] == sumN;
  forall(j in Nrange) {
    sum(i in Nrange) x[i][j] == sumN;
    sum(i in Nrange) x[i][i] == sumN;
    sum(i in Nrange) x[i][N+1-i] == sumN; }
    allDifferent(all(i,j in Nrange) x[i][j]);
}

در انتهای فایل mod. بلوک کنترل جریان زیر به‌کار گرفته می‌شود. کلیدی‌ترین دستورات این بلوک (متدهای شی cp)، دو دستور ()startNewSearch و ()next است که به ترتیب وظیفه شروع جستجوی جدید در گره فعلی درخت و ادامه‌ی جستجو هنگام تولید جواب جدید راایفا می‌کنند. رویه جستجو تا زمانی که تمامی گره‌ها بسته نشود ادامه دارد.

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

جالب است بدانید که برای یک جدول \( ۴ \times 4 \) به تعداد \( ۸۸۰ \) مربع جادویی منحصربفرد وجود دارد. تعداد مربع‌های جادویی برای \( ۵ \times 5 \) به تعداد \( ۲۷۵,۳۰۵,۲۲۴ \) و \( ۶ \times 6 \) تعداد \( (۰٫۱۷۷۴۵ \pm 0.00016) \times 10^{20} \) است!

کد این مسئله در لینک زیر بارگذاری شده است.

این محتوا برای اعضا قابل مشاهده است. لطفا وارد شوید

RelatedPost

دیدگاه بگذارید