N Puzzle Problem - part 1

ছবিটি একটি ৮-পাযল ( 8 - Puzzle ) এর ছবি। এখানে ১ থেকে ৮ পর্যন্ত ইউনিক ৮ টি নম্বর আছে। এবং একটি ফাঁকা ঘর আছে। আমাদের কাজ হচ্ছে পাযলটি কে ফাইনাল স্টেট এ নিয়ে আসা। এক্ষেত্রে আমরা ফাঁকা ঘরটির উপর ভিত্তি করে উপরে, নিচে, ডানে এবং বামে মুভ দিতে পারবো। আমাদের কাজ হচ্ছে নিচের ছবির মতন স্টেট এ আসা।

আমরা হিসাবের সুবিধার্থে ফাঁকা ঘরটিতে 0 (শুন্য) বসিয়ে হিসাব করবো। একটি ডেমোন্সট্রেশন দেখা যাক -->

আমরা প্রথমে বামে( 4 কে 0 এর ঘরে নিয়েছি, কাজেই আমাদের বামদিকে মুভ হয়েছে ), এরপরে উপরে এবং আবার বামে গিয়ে স্টেট মিলাতে পেরেছি। আমাদের ইনিশিয়াল থেকে মোট ৩ টি মুভ দেয়া লাগার কারনে আমাদের টোটাল মুভ লেগেছে ৩ টি। আমাদের কাজ হচ্ছে, এরকম পাযল দেয়া থাকলে ইনিশিয়াল থেকে ফাইনাল স্টেট এ সবচেয়ে কম কত মুভ এ যাওয়া যায় এবং মুভগুলি কিকি তা হিসাব করা।
এটা একটি ৮-পাযল প্রব্লেম। এখানে n এর মান ৩। কাজেই একটি n*n ২ডি গ্রিড এর মধ্যে 0 থেকে n²-1 পর্যন্ত সংখ্যা থাকবে। n এর মান ৪ হলে আমরা তাকে ১৫-পাযল বলবো।

Unsolvable State for N Puzzle Problem

আমরা এখানে ৮-পাযল নিয়ে আলোচনা করবো। সব ৮-পাযল স্টেট কিন্তু সল্ভ করা নাও যেতে পারে। unsolvable এরকম স্টেট আসতে পারে আমাদের কোন এক মুভ এ। আমরা হাতে কলমে কিছুদূর আগালে হয়তোবা বুঝতে পারবো যে এটা সল্ভ করা সম্ভব না। কিন্তু কম্পিউটার কে এটা কিভাবে বুঝাবো? এরজন্য আমাদের কিছু প্যাটার্ন অ্যাানালাইসিস করা লাগবে যে কিকি কারনে একটি পাযল unsolvabel state আছে তা আমরা সহজে বুঝতে পারি।
আমাদের একটি n*n গ্রিড দেয়া আছে। কিছু নিয়ম খেয়াল করলে আমরা বলতে পারবো যে n*n-1 পাযলটি সল্ভ করা যাবে কিনা। নিয়মগুলি খেয়াল করি --- >

১। যদি n এর মান বেজোড় হয়, তাহলে পাযলের স্টেটটি সল্ভ করা যাবে শুধুমাত্র তখনি যখন ঐ স্টেট এর ইনভার্শন (inversion) সংখ্যা জোড় হবে।

২। যদি n এর মান জোড় হয় (১৫-পাযল এর ক্ষেত্রে n এর মান ৪, যা জোড়) তাহলে পাযলের স্টেটটি সল্ভ করা যাবে যদি-->

• যদি গ্রিড এর নিচ থেকে শুরু করে জোড় পজিশন (second_last, fourth_last,... ) এ ফাঁকা ঘরটি থাকে এবং ইনভার্শন সংখ্যা বেজোড় হয় অথবা,
• যদি গ্রিড এর নিচ থেকে শুরু করে বেজোড় পজিশন (last, third_last,fifth_last,... ) এ ফাঁকা ঘরটি থাকে এবং ইনভার্শন সংখ্যা জোড় হয়।
  

** এখানে পজিশন হল, নিচের সারি ( একদম শেষ সারিকে ১ ধরে ) থেকে শুরু করে উপরে উঠতে থাকলে যেই সারি তে আমরা ফাঁকা ঘরটি পাবো সেই সারি নম্বর।

৩। বাকি সকল ক্ষেত্রে পাযলটি সল্ভ করা সম্ভব হবেনা।

Inversion Count for a N Puzzle State

আমরা গ্রিডটি কে ২ডি থেকে ১ডি তে কনভার্ট করি। তাহলে উপরের উদাহরন অনুসারে আমরা এভাবে মানগুলিকে সাজাই --> 1  2  3  0  4  6  7  5  8
এখানে পজিশন হল ২, কারন নিচ থেকে শুরু করে ২ নং সারিতে আমাদের ফাঁকা ঘরটি আছে।
এখন এটি একটি ১ডি অ্যাারের মতন হয়ে গেল। এখন আমরা এখানে সকল পেয়ার (pair) সংখ্যা এর জন্য দেখবো যে ,
একটি সংখ্যা তার পরের সংখ্যা থেকে বড় কিনা। যদি বড় হয়, তাহলে আমরা ইনভার্শন এর মান বাড়াবো। তাহলে এই অ্যাারে থেকে খেয়াল করলে আমরা সকল পেয়ার এর মধ্যে হিসাব করলে দেখবো যে ২ টি সংখ্যা এর মধ্য নিচের পেয়ারগুলি আমাদের ইনভার্শন হবার শর্ত পূরণ করে-->

• ( 6, 5 ) as 6 > 5
• ( 7, 5 ) as 7 > 5

তাহলে আমাদের ইনভার্শন সংখ্যা হচ্ছে ২ যা জোড়। এবং এই পাযল এর জন্য n এর মান ৩, যা বেজোড়। এবং এটি আমাদের unsolvable puzzle state এর ১ নং শর্তটি পূরণ করেছে। কাজেই, পাযলের এই স্টেটটি সল্ভেবল একটি স্টেট। আরেকটি পাযল দেখা যাক-->

এখানে  2  1  3  4  5  6  7  8  9  10  11  12  13  14  15  0
সুতরাং আমাদের ইনভার্শন সংখ্যা হবে ১। ( যেহেতু পেয়ার < 2, 1 > ই কেবলমাত্র শর্ত মানে )।
আর যেহেতু ইনভার্শন সংখ্যা বেজোড় এবং n  এর মান এখানে জোড় ( 4 ) কাজেই এটি unsolvable puzzle state এর ২নং শর্ত অনুযায়ী , 0 নিচ থেকে শুরু করে বেজোড় পজিশন এ আছে। এবং ইনভার্শন সংখ্যা এর মান ও বেজোড়। কাজেই এটি একটি unsolvable state । এই স্টেট থেকে কখনো আমরা ফাইনাল স্টেট এ যেতে পারবোনা।

** আমরা কিন্তু ইনভার্শন কাউন্ট এর সময় 0 কে কখনো ধরবো না। হিসাবের সুবিধার্থে আমরা 0 নিয়েছি, যাতে প্রোগ্রাম লিখার ক্ষেত্রে আমাদের সুবিধা হয়। এখানে 0  আসলে ফাঁকা ঘর, যা আমরা আগেই বলে এসেছি।

আরো কিছু উদাহরন দেখা যাক--->

এখানে একটি n-puzzle এর সল্ভ চেকিং এর কোড দেয়া হল। ইচ্ছামতন গ্রিড সাইজ দিয়ে কোড রান করলে আমরা বলতে পারবো স্টেট টি সল্ভ করা সম্ভব কিনা।

	// C++ program to check if a given instance of N*N-1
	// puzzle is solvable or not
	#include <iostream>
	using namespace std;
	#define N 4 // you can edit the size according to your program
	// optimized to work in O(n Log n) time.
	int getInvCount(int arr[])
	{
	int inv_count = 0;
	for (int i = 0; i < N * N - 1; i++)
	{
	for (int j = i + 1; j < N * N; j++)
	{
	/* count pairs(i, j) such that i appears
	before j, but i > j. */
	if (arr[j] && arr[i] && arr[i] > arr[j])
	inv_count++;
	}
	}
	return inv_count;
	}
	// find Position of blank from bottom
	int findXPosition(int puzzle[N][N])
	{
	for (int i = N - 1; i >= 0; i--)
	for (int j = N - 1; j >= 0; j--)
	if (puzzle[i][j] == 0)
	return N - i;
	}
	bool isSolvable(int puzzle[N][N])
	{
	// Count inversions in given puzzle
	int invCount = getInvCount((int*)puzzle);
	if (N & 1)
	return !(invCount & 1);
	else
	{
	int pos = findXPosition(puzzle);
	if (pos & 1)
	return !(invCount & 1);
	else
	return invCount & 1;
	}
	}
	/* Driver program to test above functions */
	int main()
	{
	int puzzle[N][N] = {{1, 8, 2},
	{0, 4, 3},
	{7, 6, 5}};
	isSolvable(puzzle)? cout << "Solvable":
	cout << "Not Solvable";
	return 0;
	}

view raw puzzle sovable state.cpp hosted with ❤ by GitHub

Sources:
https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
পরবর্তী পর্ব পাওয়া যাবে এখানে ঃ part - 2