مقدمه


مسئله N-Queen یکی از مسائل کلاسیک در حوزه برنامه‌نویسی و الگوریتم‌های جستجو است که در آن باید تعداد N شاهین را در یک صفحه شطرنجی N×N قرار داد، به طوری که هیچ دو شاهین در یک سطر، ستون یا قطر قرار نگیرند. این مسئله، نمونه‌ای عالی برای درک مفاهیم مختلف در طراحی الگوریتم، مانند روش‌های بازگشتی، جستجوی عمقی و سطحی، و همچنین کار با ساختارهای داده‌ای است. در این مقاله، ما به بررسی کامل و جامع نمونه سورس کد حل مسئله N-Queen با استفاده از روش‌های DFS و BFS در زبان برنامه‌نویسی سی‌شارپ خواهیم پرداخت و نحوه نمایش راه‌حل‌ها را نیز شرح می‌دهیم.
روش‌های حل مسئله N-Queen
در حل این مسئله، دو نوع الگوریتم کلی وجود دارد: روش جستجوی عمقی (Depth-First Search یا DFS) و روش جستجوی عرضی (Breadth-First Search یا BFS). هر کدام ویژگی‌های خاص خود را دارند و در پروژه‌های مختلف، بسته به نیاز، مورد استفاده قرار می‌گیرند.
روش DFS
روش DFS یا جستجوی عمقی، بر پایه‌ی بازگشت یا Backtracking است. در این الگوریتم، شروع می‌کنیم از اولین سطر و سعی می‌کنیم هر ستونی در آن را پر کنیم. سپس، در سطر بعدی، تنها خانه‌هایی را در نظر می‌گیریم که با قرار دادن شاهین در آنجا، هیچ تداخلی با شاهین‌های قبلی نداشته باشد. اگر در هر مرحله، به خانه‌ای برسیم که تداخل داشته باشد، بازمی‌گردیم و خانه قبلی را تغییر می‌دهیم. این روند ادامه می‌یابد تا زمانی که تمامی شاهین‌ها در صفحه قرار گرفته باشند یا تمام راه‌حل‌های ممکن بررسی شده باشند.
روش BFS
در مقابل، روش BFS با استفاده از صف (Queue) کار می‌کند. در این روش، ابتدا تمام حالت‌های ممکن در سطر اول را در صف قرار می‌دهیم. سپس، هر حالت را به نوبت از صف خارج کرده و حالت‌های بعدی را بر اساس آن توسعه می‌دهیم. در هر مرحله، سعی می‌کنیم خانه‌هایی در سطر بعدی قرار دهیم که با حالت قبلی تداخل نداشته باشد. این فرآیند ادامه می‌یابد تا زمانی که راه‌حلی کامل پیدا شود یا همه مسیرها بررسی شده باشند.
کد نمونه در سی‌شارپ
در ادامه، کد نمونه حل مسئله N-Queen با هر دو روش را ارائه می‌دهم و سپس نحوه نمایش نتیجه و برتری‌های هر روش را شرح می‌دهم.
کد حل با DFS (بازگشتی)
csharp  


using System;


using System.Collections.Generic;
class NQueenSolver  


{


    private int size;


    private int[] positions;


    private List<int[]> solutions;
public NQueenSolver(int n)


    {


        size = n;


        positions = new int[n];


        solutions = new List<int[]>();


    }
public void Solve()


    {


        PlaceQueen(0);


        DisplaySolutions();


    }
private void PlaceQueen(int row)


    {


        if (row == size)


        {


            solutions.Add((int[])positions.Clone());


            return;


        }


        for (int col = 0; col < size; col++)


        {


            if (IsSafe(row, col))


            {


                positions[row] = col;


                PlaceQueen(row + 1);


            }


        }


    }
private bool IsSafe(int row, int col)


    {


        for (int i = 0; i < row; i++)


        {


            if (positions[i] == col || Math.Abs(positions[i] - col) == Math.Abs(i - row))


                return false;


        }


        return true;


    }
private void DisplaySolutions()


    {


        int count = 1;


        foreach (var solution in solutions)


        {


            Console.WriteLine($"Solution {count++}:");


            for (int i = 0; i < size; i++)


            {


                for (int j = 0; j < size; j++)


                {


                    if (solution[i] == j)


                        Console.Write("Q ");


                    else  


                        Console.Write(". ");


                }


                Console.WriteLine();


            }


            Console.WriteLine();


        }


        Console.WriteLine($"Total solutions: {solutions.Count}");


    }


}

کد حل با BFS (جستجوی عرضی)
در الگوریتم BFS، از صف برای نگهداری حالت‌های در حال بر... ← ادامه مطلب در magicfile.ir