کد هشت وزیر در C++
مسئله هشت وزیر یکی از مسائل کلاسیک در علم کامپیوتر و نظریه بازی‌هاست. در این مسئله، هدف ما قرار دادن هشت وزیر بر روی یک تخته شطرنج ۸x۸ به گونه‌ای است که هیچ دو وزیری یکدیگر را تهدید نکنند. وزرا می‌توانند در هر راستا، عمودی و مایل حرکت کنند. بنابراین، باید دقت کنیم که هیچ دو وزیری در یک ردیف، ستون یا قطر قرار نگیرند.
الگوریتم حل مسئله
برای حل این مسئله، از رویکرد بازگشتی یا Backtracking استفاده می‌شود. ایده اصلی این است که وزرا را یکی یکی قرار دهیم و در هر مرحله بررسی کنیم آیا قرار دادن وزیر در موقعیت فعلی مجاز است یا نه.
- ایجاد یک تخته شطرنج: تخته شطرنج را به صورت یک آرایه ۲ بعدی یا یک آرایه یک بعدی در نظر می‌گیریم.
- قرار دادن وزرا: از ردیف اول شروع می‌کنیم و در هر ردیف تلاش می‌کنیم وزیر را در ستون‌های مختلف قرار دهیم.
- بررسی مجاز بودن: برای هر موقعیت جدید، بررسی می‌کنیم که آیا وزیری در آن ردیف، ستون یا قطر وجود دارد یا خیر.
- بازگشت: اگر قرار دادن وزیر مجاز بود، به ردیف بعدی می‌رویم و اگر در نهایت نتوانستیم وزیری قرار دهیم، به عقب برمی‌گردیم و موقعیت‌های قبلی را تغییر می‌دهیم.
کد نمونه به زبان C++
```cpp
#include <iostream>
using namespace std;
#define N 8
bool isSafe(int board[N][N], int row, int col) {
for (int i = 0; i < col; i++)
if (board[row][i])
return false;
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
for (int i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;
return true;
}
bool solveNQUtil(int board[N][N], int col) {
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1))
return true;
board[i][col] = 0; // BACKTRACK
}
}
return false;
}
void solveNQ() {
int board[N][N] = { {0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0} };
if (solveNQUtil(board, 0) == false) {
cout << "Solution does not exist";
return;
}
printSolution(board);
}
void printSolution(int board[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
cout << " " << board[i][j] << " ";
cout << endl;
}
}
int main() {
solveNQ();
return 0;
}
```
توضیحات کد
در این کد:
- isSafe: تابعی است که بررسی می‌کند آیا قرار دادن وزیر در موقعیت مشخص مجاز است یا نه.
- solveNQUtil: تابع بازگشتی است که به طور مکرر وزرا را قرار می‌دهد و در صورت عدم موفقیت به عقب برمی‌گردد.
- printSolution: تابعی که تخته شطرنج نهایی را چاپ می‌کند.
نتیجه‌گیری
مسئله هشت وزیر یک مثال عالی از استفاده از الگوریتم‌های بازگشتی و بهینه‌سازی است. این کد می‌تواند به راحتی برای تعداد وزرای بیشتری تغییر یابد و به ما امکان می‌دهد تا درک عمیق‌تری از مفاهیم الگوریتمی پیدا کنیم.
کد هشت وزیر در زبان C++ یکی از مسائل کلاسیک در حوزه برنامه‌نویسی و علوم کامپیوتر است. این مسئله، تلاش می‌کند تا تعداد بیشتری از وزیران را بر روی صفحه‌ی شطرنج، به نحوی قرار دهد که هیچ‌کدام به یکدیگر حمله نکنند. در ادامه، به صورت کامل و جامع، مفاهیم، راه‌کارها و نمونه کد این مسئله را بررسی می‌کنیم.
مقدمه و اهمیت مسئله هشت وزیر
در این مسئله، هدف اصلی، یافتن تمامی ترکیبات ممکن است که در آن، هشت وزیر روی صفحه‌ی ۸x8 قرار می‌گیرند، به‌طوری که هیچ‌کدام از وزیران در معرض حمله قرار نگیرند. این مسأله، در اصل، نمونه‌ای خوب برای درک مفاهیم بازگشتی، جستجوهای عمقی، و الگوریتم‌های جستجو است. علاوه بر آن، راه‌کارهای آن می‌تواند در حل مسائل مشابه، مثل قرار دادن چندین عنصر در یک فضای محدود، موثر باشد.
مراحل حل مسئله
در حل این مسئله، معمولاً از روش‌های بازگشتی و backtracking استفاده می‌شود. این روش‌ها، به صورت مرحله‌به‌مرحله، سعی می‌کنند هر موقعیت ممکن برای وزیر بعدی را آزمایش کنند و در صورت توافق، ادامه می‌دهند؛ در غیر این صورت، به عقب برمی‌گردند و مسیرهای دیگر را امتحان می‌کنند.
نحوه پیاده‌سازی در C++
در زبان C++، ابتدا باید یک ساختار داده مناسب برای نگهداری وضعیت صفحه داشته باشیم. به طور معمول، از آرایه‌ای یک‌بعدی یا دو‌بعدی استفاده می‌شود. در اینجا، بهتر است از آرایه‌ی یک‌بعدی که نشان می‌دهد هر وزیر در چه ستون قرار دارد، استفاده کنیم. این به دلیل سادگی و کاهش پیچیدگی است.
سپس، تابع بازگشتی برای قرار دادن وزیر در هر ردیف، و بررسی اینکه آیا قرار دادن آن در ستون مشخص، منجر به حمله می‌شود یا خیر، نوشته می‌شود.
کد نمونه هشت وزیر در C++
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int N = 8; // اندازه صفحه‌ی شطرنج
vector<int> positions(N, -1); // نگهداری موقعیت وزیران در هر ردیف
int solutions = 0; // شمارش تعداد راه‌حل‌ها
// تابع برای بررسی اینکه آیا قرار دادن وزیر در ردیف و ستون خاص مجاز است یا نه
bool isSafe(int row, int col) {
for (int prevRow = 0; prevRow < row; prevRow++) {
int prevCol = positions[prevRow];
// بررسی حمله در ستون و قطرها
if (prevCol == col || abs(prevCol - col) == abs(prevRow - row))
return false;
}
return true;
}
// تابع بازگشتی برای قرار دادن وزیران
void solve(int row) {
if (row == N) {
solutions++;
// می‌توانید اینجا راه‌حل را چاپ کنید
return;
}
for (int col = 0; col < N; col++) {
if (isSafe(row, col)) {
positions[row] = col; // قرار دادن وزیر در این ستون
solve(row + 1); // ادامه‌ی قرار دادن وزیر در ردیف بعد
positions[row] = -1; // بازنشانی قبل از امتحان حالت دیگر
}
}
}
int main() {
solve(0);
cout << "تعداد راه حل‌ها: " << solutions << endl;
return 0;
}
```
توضیحات کد
در این کد، ابتدا آرایه‌ی `positions` تعریف می‌شود که هر عنصر نشان می‌دهد وزیر در کدام ستون قرار دارد. تابع `isSafe` بررسی می‌کند که آیا قرار دادن وزیر در ردیف `row` و ستون `col`، حمله ایجاد می‌کند یا نه. در حلقه‌ی `for`، سعی می‌شود در هر ستون، در صورت مجاز بودن، وزیر قرار گیرد و سپس به ردیف بعدی می‌رویم. اگر تمام ردیف‌ها پر شدند، تعداد راه‌حل‌ها افزایش می‌یابد.
در نتیجه
در مجموع، کد هشت وزیر در C++، نمونه‌ای است که نشان می‌دهد چگونه می‌توان از روش‌های بازگشتی و backtracking برای حل مسائل ترکیبی و جایگذاری بهره برد. این کد، پایه‌ای است که می‌تواند برای حل مسائل بزرگ‌تر، مثل نوزده وزیر یا دیگر نسخه‌های عمومی، توسعه یابد.
در صورت نیاز، می‌توان راه‌کارهای بهینه‌تر، مانند استفاده از الگوریتم‌های دقیق‌تر یا کاهش فضای جستجو، ارائه داد. اما، این نمونه، بهترین نقطه شروع برای درک مفاهیم است.
