هشت وزیر در سی شارپ (Eight queen in csharp)

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

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 bool 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)
                        Console.Write("Q ");
                    else
                        Console.Write("* ");
                }
                Console.WriteLine();
            }
            Console.WriteLine();
        }

        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 وزیر میپیماید و هر کدام که پیدا شد آنها را چاپ میکند.

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

در کد معمای هشت وزیر در سی شارپ یک آرایه به نام 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);

            Console.ReadKey ();
        }

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

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

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

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