১৫ পাজল গেম: সমাধানের অস্তিত্ব#
এই গেমটি একটি $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}$$অর্থাৎ শূন্য উপাদান ছাড়া বোর্ডের অবস্থানের সাথে সঙ্গতিপূর্ণ সংখ্যাগুলোর পারমুটেশন
ধরি $N$ হলো এই পারমুটেশনে ইনভার্সনের সংখ্যা (অর্থাৎ এমন উপাদান $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$ জোড় হলে সকল অবস্থানের সমাধান আছে।
তবে, এই সকল প্রমাণ বেশ জটিল ছিল।
১৯৯৯ সালে আর্চার একটি অনেক সরল প্রমাণ প্রস্তাব করেছিলেন (আপনি তাঁর নিবন্ধটি এখানে ডাউনলোড করতে পারেন)।