حل مسئله N-QUEEN در سی شارپ
مسئله N-Queen یکی از مسائل کلاسیک در زمینه الگوریتم‌ها و برنامه‌نویسی است. در این مسئله، هدف قرار دادن N ملکه بر روی یک تخته شطرنج N×N به گونه‌ای است که هیچ دو ملکه‌ای یکدیگر را تهدید نکنند. در ادامه، به بررسی روش‌های مختلف حل این مسئله با استفاده از زبان برنامه‌نویسی سی شارپ خواهیم پرداخت.
۱. اصول اولیه
در ابتدا، باید بدانیم که ملکه‌ها در شطرنج می‌توانند در عمود، ردیف، و قطر حرکت کنند. بنابراین، هیچ دو ملکه‌ای نباید در یک ردیف، یک ستون، یا یک قطر قرار داشته باشند. این محدودیت‌ها باعث می‌شود که مسئله N-Queen چالش‌برانگیز باشد.
۲. الگوریتم بازگشتی
روش متداول برای حل این مسئله استفاده از الگوریتم بازگشتی است. این الگوریتم به ما کمک می‌کند تا به صورت مرحله‌ای، ملکه‌ها را در ردیف‌های مختلف قرار دهیم و در صورت عدم امکان قرار دادن ملکه‌ها، به ردیف قبلی برگردیم.
۳. پیاده‌سازی در سی شارپ
در زیر یک پیاده‌سازی ساده از مسئله N-Queen در سی شارپ ارائه شده است:
```csharp
using System;
class NQueen
{
static int N = 8;
static void Main(string[] args)
{
SolveNQueen(N);
}
static void SolveNQueen(int n)
{
int[,] board = new int[n, n];
if (PlaceQueens(board, 0) == false)
{
Console.WriteLine("No solution exists");
}
else
{
PrintSolution(board);
}
}
static bool PlaceQueens(int[,] board, int row)
{
if (row >= N)
return true;
for (int col = 0; col < N; col++)
{
if (IsSafe(board, row, col))
{
board[row, col] = 1;
if (PlaceQueens(board, row + 1))
return true;
board[row, col] = 0; // Backtrack
}
}
return false;
}
static bool IsSafe(int[,] board, int row, int col)
{
for (int i = 0; i < row; i++)
{
if (board[i, col] == 1)
return false;
}
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
{
if (board[i, j] == 1)
return false;
}
for (int i = row, j = col; i >= 0 && j < N; i--, j++)
{
if (board[i, j] == 1)
return false;
}
return true;
}
static void PrintSolution(int[,] board)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
Console.Write(board[i, j] + " ");
}
Console.WriteLine();
}
}
}
```
۴. توضیحات کد
در این کد:
- تابع `SolveNQueen` تخته شطرنج را ایجاد کرده و از تابع `PlaceQueens` برای قرار دادن ملکه‌ها استفاده می‌کند.
- تابع `PlaceQueens` به صورت بازگشتی عمل می‌کند و هر بار سعی می‌کند ملکه را در یک ستون از ردیف مشخص قرار دهد.
- تابع `IsSafe` بررسی می‌کند که آیا می‌توان ملکه را در موقعیت مشخص قرار داد یا خیر.
- در نهایت، تابع `PrintSolution` وضعیت نهایی تخته را چاپ می‌کند.
۵. نتیجه‌گیری
مسئله N-Queen نه تنها یک معما جذاب است، بلکه به ما کمک می‌کند تا مهارت‌های حل مسئله و برنامه‌نویسی خود را تقویت کنیم. با استفاده از الگوریتم‌های بازگشتی و تکنیک‌های جستجو، می‌توانیم به راه‌حل‌های کارآمد و مؤثری دست یابیم.
