এই সমস্যা হলো একটি চেস বোর্ডে Nটি কুইন (queen) úgy সাজানো যাতে কোনো কুইন অন্য কোনো কুইনকে আক্রমণ (attack) না করতে পারে।
চেস কুইন যেকোনো দিকেই আক্রমণ করতে পারে: হরিজেন্টাল (horizontal), ভার্টিক্যাল (vertical), এবং ডায়াগোনাল (diagonal)।
একটি বাইনারি ম্যাট্রিক্স (binary matrix) ব্যবহার করে N কুইনların পজিশন দেখানো হয়, যেখানে কুইনরা একে অপরকে আক্রমণ করতে না পারে। এখানে আমরা ৮ কুইন সমস্যা সমাধান করব।
ইনপুট (Input)
চেস বোর্ডের সাইজ। এখানে ৮ (কারণ ৮x৮ নরমাল চেস বোর্ড)।
আউটপুট (Output)
ম্যাট্রিক্স যা দেখাবে কোন রো (row) এবং কলাম (column)-এ N কুইন রাখা যাবে।
যদি সমাধান না থাকে, তবে false রিটার্ন করবে।
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0
এই আউটপুটে ১ মানটি কুইনların সঠিক পজিশন বোঝায়। ০ মানে চেস বোর্ডের খালি স্পেস।
এলগরিদম
isValid(board, row, col)
Begin
যদি বাম পাশে কুইন থাকে, তবে return false
যদি বাম-উপরের ডায়াগোনালে কুইন থাকে, তবে return false
যদি বাম-নিচের ডায়াগোনালে কুইন থাকে, তবে return false
return true // অন্যথায় ভ্যালিড প্লেস
End
solveNQueen(board, col)
Begin
যদি সব কলাম ফিল হয়ে যায়, তবে return true
বোর্ডের প্রতিটি রো için:
যদি isValid(board, i, col) true হয়, তবে
বোর্ডে (i, col) পজিশনে কুইন রাখুন
যদি solveNQueen(board, col+1) true রিটার্ন করে, তবে return true
অন্যথায় (i, col) পজিশন থেকে কুইন সরিয়ে দিন (backtrack)
done
return false
End
উদাহরণ (৪x৪ বোর্ডের জন্য)
#include <iostream>
using namespace std;
#define N 4
void printBoard(int board[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
cout << board[i][j] << " ";
cout << endl;
}
}
bool isValid(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 solveNQueen(int board[N][N], int col) {
if (col >= N) // N কুইন সফলভাবে প্লেস হয়েছে
return true;
for (int i = 0; i < N; i++) { // প্রতিটি রো চেক
if (isValid(board, i, col)) {
board[i][col] = 1; // ভ্যালিড হলে কুইন রাখুন
if (solveNQueen(board, col + 1)) // রিকার্শন
return true;
board[i][col] = 0; // ব্যাকট্র্যাক (backtrack)
}
}
return false;
}
bool checkSolution() {
int board[N][N];
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
board[i][j] = 0;
if (solveNQueen(board, 0) == false) {
cout << "Solution does not exist";
return false;
}
printBoard(board);
return true;
}
int main() {
checkSolution();
}
আউটপুট (৪x৪ বোর্ড)
1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0
