کد هشت وزیر در 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: تابعی که تخته شطرنج نهایی را چاپ می‌کند.
نتیجه‌گیری
مسئله هشت وزیر یک مثال عالی از استفاده از الگوریتم‌های بازگشتی و بهینه‌سازی است. این کد می‌تواند به راحتی برای تعداد وزرای بیشتری تغییر یابد و به ما امکان می‌دهد تا درک عمیق‌تری از مفاهیم الگوریتمی پیدا کنیم.
