১৫ পাজল গেম: সমাধানের অস্তিত্ব#
এই গেমটি একটি $4 \times 4$ বোর্ডে খেলা হয়। এই বোর্ডে ১ থেকে ১৫ পর্যন্ত নম্বরযুক্ত $15$ টি খেলার টাইল আছে। একটি ঘর খালি রাখা হয় (০ দ্বারা চিহ্নিত)। তোমাকে বারবার একটি টাইলকে খালি জায়গায় সরিয়ে নিচে দেখানো অবস্থানে বোর্ড নিয়ে যেতে হবে:
$$\begin{matrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 0 \end{matrix}$$“১৫ পাজল” গেমটি ১৮৮০ সালে নয়েস চ্যাপম্যান তৈরি করেছিলেন।
সমাধানের অস্তিত্ব#
চলো এই সমস্যাটা দেখি: বোর্ডের একটি অবস্থান দেওয়া আছে, বের করো সমাধানে পৌঁছানোর কোনো চালের ক্রম আছে কিনা।
ধরি বোর্ডে আমাদের কোনো অবস্থান আছে:
$$\begin{matrix} a_1 & a_2 & a_3 & a_4 \\ a_5 & a_6 & a_7 & a_8 \\ a_9 & a_{10} & a_{11} & a_{12} \\ a_{13} & a_{14} & a_{15} & a_{16} \end{matrix}$$যেখানে উপাদানগুলোর একটি শূন্যের সমান এবং একটি খালি ঘর বোঝায় $a_z = 0$
চলো পারমুটেশনটি দেখি:
$$a_1 a_2 ... a_{z-1} a_{z+1} ... a_{15} a_{16}$$অর্থাৎ শূন্য উপাদান ছাড়া বোর্ডের অবস্থানের সাথে সঙ্গতিপূর্ণ সংখ্যাগুলোর পারমুটেশন (permutation)
ধরি $N$ হলো এই পারমুটেশনে ইনভার্সনের (inversion) সংখ্যা (অর্থাৎ এমন উপাদান $a_i$ এবং $a_j$ এর সংখ্যা যেখানে $i < j$, কিন্তু $a_i > a_j$)।
ধরি $K$ হলো সেই সারির ইনডেক্স যেখানে খালি উপাদানটি অবস্থিত (অর্থাৎ আমাদের প্রথা অনুযায়ী, $K = (z - 1) \div \ 4 + 1$)।
তাহলে, সমাধান বিদ্যমান যদি এবং কেবল যদি $N + K$ জোড় হয়।
ইমপ্লিমেন্টেশন#
উপরের অ্যালগরিদমটি নিচের প্রোগ্রাম কোড দিয়ে বোঝানো যায়:
int a[16];
for (int i=0; i<16; ++i)
cin >> a[i];
int inv = 0;
for (int i=0; i<16; ++i)
if (a[i])
for (int j=0; j<i; ++j)
if (a[j] > a[i])
++inv;
for (int i=0; i<16; ++i)
if (a[i] == 0)
inv += 1 + i / 4;
puts ((inv & 1) ? "No Solution" : "Solution Exists");প্রুফ#
১৮৭৯ সালে জনসন প্রুফ করেছিলেন যে যদি $N + K$ বিজোড় হয়, তাহলে সমাধান নেই, এবং একই বছরে স্টোরি প্রুফ করেছিলেন যে $N + K$ জোড় হলে সকল অবস্থানের সমাধান আছে।
তবে, এই সকল প্রুফ বেশ জটিল ছিল।
১৯৯৯ সালে আর্চার একটি অনেক সরল প্রুফ প্রস্তাব করেছিলেন (তুমি তাঁর আর্টিকেলটা এখানে ডাউনলোড করতে পারো)।