java, جاوا, حل مسائل با جاوا, ساختمان داده در جاوا

معمای هشت وزیر در جاوا (Eight Queen)

معمای هشت وزیر در جاوا

در این جلسه تیم کدگیت را با آموزش معمای هشت  وزیر در جاوا همراهی کنید. پیش نیاز این آموزش شامل موارد زیر است:

  1. آشنایی با متد
  2. آشنایی با for
  3. آشنایی با روش بازگشتی
  4. آشنایی با if

چند وزیر

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

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

الگوریتم عقب گرد

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

پیاده سازی معمای هشت وزیر در جاوا

برای پیاده سازی معمای هشت وزیر در جاوا روش های مختلفی استفاده میشود. در اینجا ما از روش توضیح داده شده در بالا استفاده میکنیم. در کد جاوا ما تمام حالات هشت وزیر را نشان میدهیم(همانطور که میدانید هشت وزیر 92 جواب دارد). برای نشان دادن همه حالات از روش بازگشتی استفاده کردیم.

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

    public static boolean isConsistent(int[] q, int n) {
          for (int i = 0; i < n; i++) {
              if (q[i] == q[n])
                   return false; // same column
              if ((q[i] - q[n]) == (n - i))
                   return false; // same major diagonal
              if ((q[n] - q[i]) == (n - i))
                   return false; // same minor diagonal
          }
          return true;
     }

     public static void printQueens(int[] q) {

          int n = q.length;
          for (int i = 0; i < n; i++) {
              for (int j = 0; j < n; j++) {
                   if (q[i] == j)
                        System.out.print("Q ");
                   else
                        System.out.print("* ");
              }
              System.out.println();
          }
          System.out.println();
     }

     public static void enumerate(int n) {
          int[] a = new int[n];
          enumerate(a, 0);
     }

     public static void enumerate(int[] q, int k) {

          int n = q.length;
          if (k == n)
              printQueens(q);
          else {
              for (int i = 0; i < n; i++) {
                   q[k] = i;
                   if (isConsistent(q, k))
                        enumerate(q, k + 1);
              }
          }
     }

کد معمای هشت وزیر در جاوا شامل متد های زیر است:

  1. Printqueens: متدی است که 8 وزیر پیدا شده را نمایش میدهد.
  2. isConsistent: متدی است که بررسی میکند وزیر های تا الان پیدا شده با هم برخوردی دارند یا خیر.
  3. Enumerate: ما دو متد با این نام داریم. متد اول یک ورودی دارد و شروع کننده الگوریتم هشت وزیر ما است. و متد دوم دو ورودی دارد و به صورت بازگشتی تمام خانه های ممکن را برای 8 وزیر میپیماید و هر کدام که پیدا شد آنها را چاپ میکند.

به طور کلی کد معمای هشت وزیر در جاوا به این صورت عمل میکند که در هر سطر یک وزیر را به ترتیب از اول میچیند یعنی وزیر اول در سطر اول و در خانه اول میچیند اگر برخوردی نداشته باشد به سراغ سطر دوم میرود. در سطر دوم وزیر را در خانه اول میچیند و اگر برخورد با وزیر اول داشت یک خانه به جلو می آید و اگر نه به سطر بعد میرود. این کار را برای تمام سطر ها انجام میدهد.

حال اگر به آخر رسیدیم و در سطر هشتم هستیم و همه خانه های یک تا هشت را بررسی کرده باشیم.به سطر هفت برمیگردیم فرض کنید در خانه 3 قرار داریم. یک خانه به جلو میرویم و دوباره الگوریتم را طبق توضیحات ادامه میدهیم. با این کار تمام جواب های ممکن را بررسی میکنیم.

در کد معمای هشت وزیر در جاوا یک آرایه به نام q داریم که وزیرهای خود را در هر سطر نگه میداریم(اندیس وزیر ها نگه داری میشود). برای بررسی برخورد وزیر ها با هم این اندیس ها را با هم بررسی میکنیم به روش های زیر:

  1. اگر در یک ستون باشند میشود: q[i] = q[n]
  2. اگر در یک اریب اصلی باشند: q[i] –q[n] = n – i
  3. اگر در اریب فرعی باشند: q[n] –q[i] = n – i

تست برنامه معمای هشت وزیر در جاوا

برای تست کد بالا، کد main زیر را بزنید:

     public static void main(String[] args) {
          int n = 8;
          enumerate(n);

     }

متغیر n نشان دهنده وزیرهای شماست. در این جا برای نشان دادن هشت وزیر آن را هشت قرار دادیم شما میتوانید آن را کم یا زیاد کنید.

قسمتی از خروجی معمای هشت وزیر در جاوا به صورت زیر است:

* * * * * Q * *
Q * * * * * * *
* * * * Q * * *
* Q * * * * * *
* * * * * * * Q
* * Q * * * * *
* * * * * * Q *
* * * Q * * * *

* * * * * Q * *
* Q * * * * * *
* * * * * * Q *
Q * * * * * * *
* * Q * * * * *
* * * * Q * * *
* * * * * * * Q
* * * Q * * * *

نوشته های مشابه

2 دیدگاه در “معمای هشت وزیر در جاوا (Eight Queen)

  1. zzzzzzzzzzzzzzzzzzzzzzzzzz گفت:

    لام من ایمیل دادم ولی برای ایمیلم فایل دانلودی ک اومده میگه این فایل از بین رفته !!!! چ کنم ؟

    1. سلام. فایل دانلود بررسی شد و مشکلی نداشت. فایل های دانلود بعد از مدتی Expire میشوند. دانلود فایل را تکرار کنید تا مشکل حل شود
      تشکر.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *