نمونه سورس کد حل مسئله N-Queen توسط DFS و BFS و نمایش آن در سی شارپ
این توضیحات بصورت خودکار ارسال شده است برای دانلود فایل به سایت اصلی که لینک دانلود در پایین قرار داده شده است بروید
حل مسئله N-Queen با استفاده از الگوریتمهای DFS و BFS در زبان سیشارپ
مسئله N-Queen یکی از مسائل کلاسیک در زمینه برنامهنویسی و هوش مصنوعی است که هدف آن قرار دادن N عدد شاهین بر روی صفحهای شطرنجی N×N است، به گونهای که هیچ دو شاهین در یک ردیف، ستون یا قطر قرار نگیرند. این مسئله، نمونهای عالی برای نشان دادن روشهای جستجو و الگوریتمهای مختلف است؛ بهخصوص الگوریتمهای عمقی (DFS) و سطحی (BFS). در ادامه، به طور کامل و جامع، نمونه کد حل این مسئله با این دو الگوریتم و نمایش نتایج در زبان سیشارپ را بررسی میکنیم.
مقدمه و اهمیت مسئله N-Queen
قبل از هر چیز، باید بدانیم که چرا این مسئله مهم است. مسئله N-Queen، نه تنها یک تمرین در طراحی الگوریتم است، بلکه به ما کمک میکند تا مفاهیم پایهای در جستجو در فضای حالت، برنامهنویسی بازگشتی، و ساختار دادهها را یاد بگیریم. همچنین، حل این مسئله با الگوریتمهای مختلف، نشان میدهد که چگونه میتوان با روشهای متفاوت، به یک هدف مشابه رسید؛ یعنی پیدا کردن تمامی حالتهای ممکن یا فقط یک حالت صحیح.
نمای کلی مسئله در قالب یک برنامه
در زبان سیشارپ، باید ابتدا ساختارهای دادهای مناسب برای نمایش صفحه، وضعیت حال حاضر، و نگهداری راهحلها را تعریف کنیم. در این حالت، صفحه بازی میتواند به صورت یک آرایه یکبعدی یا دوبعدی نشان داده شود. رایجترین روش، استفاده از یک آرایه یکبعدی است که شماره هر عنصر، نشاندهنده ستون قرارگیری شاهین در هر ردیف است. برای مثال، اگر N=4 باشد، و آرایه به صورت `[1, 3, 0, 2]` باشد، یعنی:
- در ردیف 0، شاهین در ستون 1 قرار دارد.
- در ردیف 1، شاهین در ستون 3 قرار دارد.
- در ردیف 2، شاهین در ستون 0 قرار دارد.
- در ردیف 3، شاهین در ستون 2 قرار دارد.
در ادامه، الگوریتمهای DFS و BFS برای جستجو راهحلها به طور کامل شرح داده میشود.
---
قسمت ۱: حل با الگوریتم DFS (جستجوی عمقی)
مفهوم اصلی
در روش DFS، شروع میکنیم از ردیف صفر، و در هر مرحله، سعی میکنیم بهترین گزینه یعنی قرار دادن شاهین در یک ستون خاص را امتحان کنیم، سپس به ردیف بعدی میرویم و همین کار را تکرار مینماییم. اگر در هر مرحله، نتوانیم جای مناسبی پیدا کنیم، پس برمیگردیم (Backtracking) و گزینههای دیگر را امتحان میکنیم.
کد نمونه برای DFS
csharp
using System;
using System.Collections.Generic;
class NQueenSolver
{
private int size;
private int[] board;
private List<int[]> solutions;
public NQueenSolver(int n)
{
size = n;
board = new int[size];
solutions = new List<int[]>();
}
public void Solve()
{
PlaceQueen(0);
PrintSolutions();
}
private void PlaceQueen(int row)
{
if (row == size)
{
StoreSolution();
return;
}
for (int col = 0; col < size; col++)
{
if (IsSafe(row, col))
{
board[row] = col;
PlaceQueen(row + 1);
}
}
}
private bool IsSafe(int row, int col)
{
for (int i = 0; i < row; i++)
{
int placedCol = board[i];
if (placedCol == col || Math.Abs(placedCol - col) == Math.Abs(i - row))
return false;
}
return true;
}
private void StoreSolution()
{
int[] solution = new int[size];
Array.Copy(board, solution, size);
solutions.Add(solution);
}
private void PrintSolutions()
{
Console.WriteLine($"Total Solutions: {solutions.Count}");
int count = 1;
foreach (var solution in solutions)
{
Console.WriteLine($"\nSolution {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();
}
}
}
}
توضیحات مهم:
- تابع `PlaceQueen` به صورت بازگشتی، هر بار سعی میکند در هر ستون، قرار دهد.
- تابع `IsSafe` بررسی میکند که قرار دادن شاهین در خانه موردنظر، تداخل ندارد.
- در صورت رسیدن به انتهای صفحه، راهحل ثبت میشود.
- در انتها، تمام راهحلها چاپ میشوند.
---