দাবার বোর্ডে বিশপ বসানো#
একটি $N \times N$ দাবার বোর্ডে $K$ টি বিশপ এমনভাবে বসানোর উপায়ের সংখ্যা বের করুন যাতে কোনো দুটি বিশপ একে অপরকে আক্রমণ না করে।
অ্যালগরিদম#
এই সমস্যাটি ডায়নামিক প্রোগ্রামিং ব্যবহার করে সমাধান করা যায়।
দাবার বোর্ডের কর্ণগুলোকে নিম্নরূপে নম্বর দেওয়া যাক: কালো কর্ণগুলোর ইনডেক্স বিজোড়, সাদা কর্ণগুলোর ইনডেক্স জোড়, এবং কর্ণগুলো তাদের ঘরের সংখ্যার অ-হ্রাসমান ক্রমে নম্বরযুক্ত। এখানে একটি $5 \times 5$ দাবার বোর্ডের উদাহরণ দেওয়া হলো।
$$\begin{matrix} \bf{1} & 2 & \bf{5} & 6 & \bf{9} \\\ 2 & \bf{5} & 6 & \bf{9} & 8 \\\ \bf{5} & 6 & \bf{9} & 8 & \bf{7} \\\ 6 & \bf{9} & 8 & \bf{7} & 4 \\\ \bf{9} & 8 & \bf{7} & 4 & \bf{3} \\\ \end{matrix}$$ধরি D[i][j] হলো i বা তার চেয়ে কম ইনডেক্সের কর্ণগুলোতে (যেগুলো i কর্ণের সাথে একই রঙের) j টি বিশপ বসানোর উপায়ের সংখ্যা।
তাহলে i = 1...2N-1 এবং j = 0...K।
আমরা শুধুমাত্র D[i-2] এর মান ব্যবহার করে D[i][j] হিসাব করতে পারি (আমরা ২ বিয়োগ করি কারণ শুধুমাত্র $i$ এর সাথে একই রঙের কর্ণগুলো বিবেচনা করি)।
D[i][j] পাওয়ার দুটি উপায় আছে।
হয় আমরা সবগুলো j টি বিশপ আগের কর্ণগুলোতে বসাই: তাহলে এটি অর্জনের উপায় সংখ্যা হলো D[i-2][j]।
অথবা আমরা i কর্ণে একটি বিশপ এবং আগের কর্ণগুলোতে j-1 টি বিশপ বসাই।
এটি করার উপায়ের সংখ্যা হলো i কর্ণের ঘরের সংখ্যা বিয়োগ j-1, কারণ আগের কর্ণগুলোতে বসানো j-1 টি বিশপের প্রত্যেকটি বর্তমান কর্ণের একটি ঘর ব্লক করবে।
i কর্ণের ঘরের সংখ্যা নিচের মতো করে হিসাব করা যায়:
int squares (int i) {
if (i & 1)
return i / 4 * 2 + 1;
else
return (i - 1) / 4 * 2 + 2;
}বেস কেসটি সহজ: D[i][0] = 1, D[1][1] = 1।
আমরা D[i][j] এর সব মান হিসাব করার পর, উত্তরটি নিচের মতো করে পাওয়া যায়:
কালো কর্ণগুলোতে বসানো বিশপের সব সম্ভাব্য সংখ্যা i=0...K বিবেচনা করুন, এবং সাদা কর্ণগুলোতে সংশ্লিষ্ট সংখ্যক বিশপ হবে K-i।
কালো এবং সাদা কর্ণগুলোতে বসানো বিশপগুলো কখনো একে অপরকে আক্রমণ করে না, তাই বসানো স্বাধীনভাবে করা যায়।
শেষ কালো কর্ণের ইনডেক্স হলো 2N-1, শেষ সাদা কর্ণের ইনডেক্স হলো 2N-2।
প্রতিটি i এর জন্য আমরা উত্তরের সাথে D[2N-1][i] * D[2N-2][K-i] যোগ করি।
ইমপ্লিমেন্টেশন#
int bishop_placements(int N, int K)
{
if (K > 2 * N - 1)
return 0;
vector<vector<int>> D(N * 2, vector<int>(K + 1));
for (int i = 0; i < N * 2; ++i)
D[i][0] = 1;
D[1][1] = 1;
for (int i = 2; i < N * 2; ++i)
for (int j = 1; j <= K; ++j)
D[i][j] = D[i-2][j] + D[i-2][j-1] * (squares(i) - j + 1);
int ans = 0;
for (int i = 0; i <= K; ++i)
ans += D[N*2-1][i] * D[N*2-2][K-i];
return ans;
}