رفتن به مطلب

مدل سازی و حل مسئله 8 وزیر


پست های پیشنهاد شده

مسئله 8 وزیر و در حالت پیشرفته n وزیر یکی از مسائل مهم در مبحث OR محسوب می شود ، در این مسئله به دنبال الگوریتم هایی هستیم که راه حلی برای قرار گرفتن 8 وزیر در صفحه شطرنج بدون اینکه یکدیگر را تهدید نمایند به ما ارائه دهد .

 

یکی از مقالات مربوط در این زمینه که به مدل سازی و حل این مسئله با لینگو و VBA پرداخته است در فایل پیوست مشاهده نمایید

OR-LINGO-Project.pdf

لینک ارسال

برای آشنایی بیشتر با مسئله فوق مطالب زیر خدمت دوستان ارائه میگردد و در ادامه به ارائه حل با VBA خواهیم پرداخت:

 

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

اولین و مشهورترین شکل این مسئله معمای هشت وزیر است که برای حل آن باید ۸ وزیر را در یک صفحهً معمولی (۸×۸) شطرنج قرار داد. این مسئله ۹۲ جواب دارد که ۱۲ جواب آن منحصر به‌فرد است یعنی بقیه جواب‌ها از تقارن جواب‌های اصلی به‌دست می‌آید.

مسئله n وزیر در صورتی جواب دارد که n مساوی ۱ یا بیشتر از ۳ باشد. یعنی مسئله دو وزیر و سه وزیر راه حلی ندارند.

 

این مسئله در سال ۱۸۴۸ توسط شطرنج بازی به نام Max Bezzel عنوان شد و ریاضی دانان بسیاری ازجمله Gauss و Georg Cantor بر روی این مسئله کار کرده و در نهایت آنرا به n وزیر تعمیم دادند. اولین راه حل توسط Franz Nauck در سال ۱۸۵۰ ارائه شد که به همان مسئله n وزیر تعمیم داده شد. پس از آن Gunther راه حلی با استفاده از دترمینان ارائه داد که J.W.L. Glaisher آنرا کامل نمود. در سال ۱۹۷۹، Edsger Dijkstra Nauck با استفاده از الگوریتم عقب گرد اول عمق، این مسئله را حل کرد.

لینک ارسال

[h=3]الگوریتم عقبگرد[/h]

از تکنیک عقبگرد Backtracking برای حل مسائلی استفاده می‌شود که در آن‌ها دنباله‌ای از اشیاء از یک مجموعه مشخص انتخاب می‌شود، به طوری که این دنباله، ملاکی را در بر می‌گیرد. عقبگرد حالت اصلاح شدهٔ جست و جوی عمقی یک درخت است. این الگوریتم همانند جست و جوی عمقی است، با این تفاوت که فرزندان یک گره فقط هنگامی ملاقات می‌شوند که گره امید بخش باشدو در آن گره حلی وجود نداشته باشد. با توجه به اینکه هیچ ۲ وزیری نباید همدیگر را گارد کنند و در یک سطر نمی‌توانند باشند، تعداد کل حالت‌ها برای n=۴ برابر ۴*۴*۴*۴=۲۵۶ است. در شطرنج یک وزیر می‌تواند به مهره‌هایی که در خانه‌های عمود یا مورب به وی قرار دارند حمله کند. یا به عبارت ریاضی، اگر ردیفها و ستونهای شطرنج را از یک تا هشت شماره گذاری کنیم و وزیر در خانه (i، j) قرار داشته باشد، مهره‌هایی که در خانه‌های (i، m) یا (m، j) یا (i ± m، j ± m) قرار دارند توسط وزیر تهدید می‌شوند.

 

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

مراحل جستجو برای یافتن جواب را به این صورت دنبال می‌کنیم که: وزیر اول را در ردیف اول و ستون اول قرار می‌دهیم.

در ردیف دوم از اولین ستون به جلو رفته و به دنبال خانه‌ای می‌گردیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در این خانه قرار می‌دهیم.

همانند قبل، در ردیف سوم از اولین ستون به جلو رفته و به دنبال خانه‌ای می‌گردیم که مورد تهدید وزیران اول و دوم نباشد. می‌بینیم که چنین خانه‌ای موجود نیست. پس به عقب یعنی ردیف دوم برگشته و وزیر دوم را به خانه‌ای دیگر از ردیف دوم منتقل می‌کنیم که مورد تهدید وزیر اول نباشد.

دوباره در ردیف سوم اولین خانه‌ای را میابیم که مورد تهدید دو وزیر قبلی نباشد. این بار خانه را می‌یابیم و وزیر سوم را در آن قرار می‌دهیم.

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

در ردیف دوم اولین خانه‌ای را میابیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در آن خانه قرار می‌دهیم.

در ردیف سوم اولین خانه‌ای را میابیم که مورد تهدید وزیران اول و دوم نباشد و وزیر سوم را در آن خانه می‌گذاریم.

در ردیف چهارم اولین خانه‌ای را میابیم که مورد تهدید وزیران پیشین نباشد. این بار خانه را می‌یابیم و وزیر چهارم را در آن خانه قرار می‌دهیم.

به یک جواب می‌رسیم. حال اگر فرض کنیم که این خانه جواب نیست و به مسیر خود ادامه دهیم، احتمالا" می‌توانیم جوابهای دیگری نیز بیابیم.

لینک ارسال

[h=4]شبه کد پیاده سازی الگوریتم عقبگرد برای مسئله n وزیر[/h]

 


void queens (index i)
       {
              index j;
              if (promising(i))
                   if (i == n)
                          cout << col [1] through col [n];
                   else
                          for (j = 1 ; j ≤ n ; j++)  {
         col [ i +۱ ] = j;
         queens (i + 1);
      }
}
bool promising  (index i)
{
      index k ;
      bool  switch;
      k = ۱;
      switch  = true ;
        while (k < i && switch) {
        if (col [i] == col[k] || abs(col[i] – col[k] == i-k))
                 switch = false;
           k++;
        }
     return switch;
  }

 

 

.mayjp2y87ep6u4j4ldf.gif

لینک ارسال

در ادامه مبحث فوق کد مسئله 8 وزیر برای n=8 رو قرار میدم البته به کیفیت تصویر فوق نیست ، در آینده فایل مربوط به حالت n وزیر و با گرافیک تصویر بالا قرار داده خواهد شد.

Sub Eight_Queens()
   Dim Conflict As Boolean
   Dim i As Integer
   Dim j As Integer
   Dim k As Integer
   
   Dim x(1 To 8) As Integer
   For i = 1 To 8
       x(i) = 0
   Next
   
   i = 1
   While (i < 9)
       For j = x(i) + 1 To 8
           Conflict = False
          
           If i <> 1 Then
              
               For k = 1 To i - 1
                   If x(k) = j Then
                       Conflict = True
                       Exit For
                   End If
               Next
              
               i_copy = i
               j_copy = j
               Do While (i_copy > 1 And j_copy > 1 And Not Conflict)
                   i_copy = i_copy - 1
                   j_copy = j_copy - 1
                   If x(i_copy) = j_copy Then
                       Conflict = True
                   End If
               Loop
               
               
               i_copy = i
               j_copy = j
               Do While (i_copy > 1 And j_copy < 9 And Not Conflict)
                   i_copy = i_copy - 1
                   j_copy = j_copy + 1
                   If x(i_copy) = j_copy Then
                       Conflict = True
                   End If
               Loop
           End If
           
           If Not Conflict Then
               x(i) = j
               Exit For
           End If
       Next
       If Conflict Then
           x(i) = 0
           i = i - 1
       Else
           i = i + 1
       End If
   Wend
   
   
   For i = 1 To 8
       Range("A1").Select
       ActiveCell.Offset(x(i) - 1, i - 1).Select
       ActiveCell.FormulaR1C1 = "*"
   Next
   Columns("A:H").Select
   Columns("A:H").EntireColumn.AutoFit
   Rows("1:8").Select
   Rows("1:8").EntireRow.AutoFit
   Range("A1").Select
End Sub

لینک ارسال

به گفتگو بپیوندید

هم اکنون می توانید مطلب خود را ارسال نمایید و بعداً ثبت نام کنید. اگر حساب کاربری دارید، برای ارسال با حساب کاربری خود اکنون وارد شوید .

مهمان
ارسال پاسخ به این موضوع ...

×   شما در حال چسباندن محتوایی با قالب بندی هستید.   حذف قالب بندی

  تنها استفاده از 75 اموجی مجاز می باشد.

×   لینک شما به صورت اتوماتیک جای گذاری شد.   نمایش به صورت لینک

×   محتوای قبلی شما بازگردانی شد.   پاک کردن محتوای ویرایشگر

×   شما مستقیما نمی توانید تصویر خود را قرار دهید. یا آن را اینجا بارگذاری کنید یا از یک URL قرار دهید.

×
×
  • اضافه کردن...