এই সমস্যা হলো একটি চেস বোর্ডে N কুইন সাজানোর ব্যবস্থা খুঁজে বের করা, যাতে কোনো কুইন অন্য কুইনকে আক্রমণ করতে না পারে।
চেস কুইন যেকোনো ডিরেকশনে আক্রমণ করতে পারে - হরিজেন্টাল, ভার্টিক্যাল, এবং ডায়াগোনাল।
একটি বাইনারি ম্যাট্রিক্স ব্যবহার করা হয় N কুইন পজিশন ডিসপ্লে করতে, যেখানে কোনো কুইন অন্য কুইনকে আক্রমণ করতে পারে না।
ইনপুট এবং আউটপুট
ইনপুট: চেস বোর্ডের সাইজ। সাধারণত এটি ৮। কারণ (৮ x ৮ হলো নরমাল চেস বোর্ডের সাইজ।) আউটপুট: ম্যাট্রিক্স যা রিপ্রেজেন্ট করে কোন রো এবং কলামে 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 এই আউটপুটে, ভ্যালু ১ ইন্ডিকেট করে কুইনদের সঠিক প্লেস। ০ ডিনোট করে চেস বোর্ডের খালি স্পেস।
অ্যালগরিদম
isValid(board, row, col)
ইনপুট: চেস বোর্ড, রো এবং বোর্ডের কলাম।
আউটপুট - True যখন row এবং col পজিশনে কুইন রাখা বৈধ।
শুরু
যদি কারেন্ট কলামের বামে কুইন থাকে, তবে
return false
যদি বাম উপরের ডায়াগোনালে কুইন থাকে, তবে
return false
যদি বাম নিচের ডায়াগোনালে কুইন থাকে, তবে
return false;
return true //অন্যথায় এটি বৈধ প্লেস
শেষ
solveNQueen(board, col)
ইনপুট - চেস বোর্ড, কলাম যেখানে কুইন রাখার চেষ্টা করা হচ্ছে।
আউটপুট - কুইন প্লেস করা পজিশন ম্যাট্রিক্স।
শুরু
যদি সব কলাম ফিল্ড হয়ে যায়, তবে
return true
বোর্ডের প্রতিটি রোর জন্য করুন
যদি isValid(board, i, col), তবে
বোর্ডে (i, col) প্লেসে কুইন সেট করুন
যদি solveNQueen(board, col+1) = true, তবে
return true
অন্যথায় বোর্ড থেকে (i, col) প্লেসের কুইন রিমুভ করুন।
শেষ
return false
শেষ
উদাহরণ
#include<iostream> using namespace std; #define N 8 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) //যখন N কুইন সফলভাবে প্লেস হয়েছে return true; for (int i = 0; i < N; i++) { //প্রতিটি রোের জন্য, কুইন প্লেসিং সম্ভব কিনা চেক করুন if (isValid(board, i, col) ) { board[i][col] = 1; //যদি বৈধ হয়, (i, col) প্লেসে কুইন রাখুন if ( solveNQueen(board, col + 1)) //রিকার্শিভলি অন্যান্য কলামের জন্য যান return true; board[i][col] = 0; //যখন কোনো প্লেস খালি নেই, সেটি রিমুভ করুন } } return false; //যখন কোনো সম্ভাব্য অর্ডার পাওয়া যায় না } bool checkSolution() { int board[N][N]; for(int i = 0; i
আউটপুট
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
