نمونه سورس کد حل مسئله N-Queen توسط DFS و BFS و نمایش آن در سی شارپ
این توضیحات بصورت خودکار ارسال شده است برای دانلود فایل به سایت اصلی که لینک دانلود در پایین قرار داده شده است بروید
نحوه حل مسئله N-Queen با استفاده از الگوریتمهای DFS و BFS در زبان برنامهنویسی سیشارپ
مقدمه
مسئله N-Queen یکی از مسائل کلاسیک در حوزه بهینهسازی و جستجو است که در آن هدف این است که تعداد N شاه در صفحهای N در N قرار داده شوند، به طوری که هیچکدام از آنها تهدید کننده یکدیگر نباشند. به عبارت دیگر، هیچ دو شاه نباید در یک ردیف، ستون، یا قطر قرار داشته باشند. این مسئله، نمونهای عالی برای آزمایش الگوریتمهای جستجو و بهینهسازی است و روشهای مختلفی برای حل آن وجود دارد؛ از جمله، الگوریتمهای جستجوی عمقی (DFS) و جستجوی عرضی (BFS). در ادامه، قصد دارم که به طور کامل و جامع، نحوه پیادهسازی این الگوریتمها در زبان سیشارپ را توضیح دهم.
۱. الگوریتم DFS در حل مسئله N-Queen
در ابتدا، باید بدانید که الگوریتم DFS یا جستجوی عمقی، بر اساس فرضیه پیشرفت در عمق است، یعنی، در هر مرحله، یکی از گزینههای ممکن را انتخاب میکند و در صورت نیاز، به سمت گزینههای بعدی میرود، و در صورت عدم موفقیت، به عقب برمیگردد و گزینههای دیگر را امتحان میکند.
در مسئله N-Queen، این الگوریتم به صورت بازگشتی پیادهسازی میشود. فرض کنید که یک صفحه N در N دارید، و میخواهید در آن شاهها را قرار دهید. ابتدا، از ردیف اول شروع میکنید، و در هر ردیف، سعی میکنید که ستون مناسبی را پیدا کنید که در آنجا شاه قرار گیرد، بدون اینکه با شاههای قبلی برخورد کند.
برای این منظور، چند تابع کمکی نیاز است:
- تابعی برای بررسی صحت قرارگیری شاه در یک خانه خاص.
- تابع اصلی برای انجام جستجوی عمقی که، در هر گام، سعی میکند در هر ستون، شاه قرار دهد و در صورت موفقیت، به ردیف بعدی میرود.
کد نمونه برای حل مسئله N-Queen با DFS در سیشارپ:
csharp
using System;
namespace NQueenDFS
{
class Program
{
static int N; // اندازه صفحه و تعداد شاهها
static int[] board; // آرایه برای نگهداری ستونهای قرارگیری شاهها در هر ردیف
static void Main(string[] args)
{
Console.WriteLine("Enter the value of N (size of the board): ");
N = int.Parse(Console.ReadLine());
board = new int[N];
for (int i = 0; i < N; i++)
board[i] = -1; // مقدار اولیه برای هر ردیف
if (SolveNQueenDFS(0))
{
Console.WriteLine("Solution found:");
PrintBoard();
}
else
{
Console.WriteLine("No solution exists.");
}
}
static bool SolveNQueenDFS(int row)
{
if (row == N)
return true; // تمام ردیفها پر شده است
for (int col = 0; col < N; col++)
{
if (IsSafe(row, col))
{
board[row] = col; // قرار دادن شاه در خانه
if (SolveNQueenDFS(row + 1))
return true; // ادامه جستجو در ردیف بعدی
// backtracking
board[row] = -1;
}
}
return false; // اگر هیچ خانهای مناسب نبود
}
static bool IsSafe(int row, int col)
{
for (int i = 0; i < row; i++)
{
// بررسی برخورد در ستون و قطرها
if (board[i] == col || Math.Abs(board[i] - col) == Math.Abs(i - row))
return false;
}
return true;
}
static void PrintBoard()
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (board[i] == j)
Console.Write("Q ");
else
Console.Write(". ");
}
Console.WriteLine();
}
}
}
}
در این کد، ابتدا اندازه صفحه را از کاربر میپرسیم، سپس آرایه `board` را مقداردهی میکنیم تا هر ردیف را با ستونی که شاه قرار دارد، نشان دهد. تابع `SolveNQueenDFS` با استفاده از بازگشت (backtracking) سعی میکند در هر ردیف، خانههای مناسب را پیدا کند و در صورت نیاز، به عقب برگردد.
۲. الگوریتم BFS در حل مسئله N-Queen
در مقایسه با DFS، الگوریتم BFS یا جستجوی عرضی، به صورت سطح به سطح عمل میکند. در این روش، همه حالتهای ممکن در یک سطح بررسی میشود و سپس به سطح بعدی میرود. این روش، به طور معمول، حافظه بیشتری مصرف میکند، اما در بعضی موارد، میتواند سریعتر باشد، زیرا زودتر میتواند راه حلهای نزدیک به ریشه درخت جستجو را پیدا کند.
برای پیادهسازی BFS در مسئله N-Queen، باید از صف (Queue) استفاده کنیم. هر عنصر در صف، یک حالت است که نشان میدهد چه ردیفهایی پر شده و شاهها در چه ستونهایی قرار دارند.
کد نمونه برای حل مسئله N-Queen با BFS در سیشارپ: