A* Search Algorithm for N-Puzzle

আমরা A* সার্চ দিয়ে ৮-পাযল প্রব্লেমটি সল্ভ করার চেষ্টা করবো। শুরুতে একটি স্ট্রাকচার এ আমরা আমাদের স্টেট সেইভ রাখার জন্য স্ট্রিং, পাথ সেইভ রাখার জন্য আরেকটি স্ট্রিং, হিউরিস্টিক, ডেপথ এসব সেইভের জন্য ইন্টিজার। তাহলে স্ট্রাকচার এমন দাঁড়ায় ঃ
struct puzzle {
string state, path;
int heuristic, depth, f;
}
আমরা f এর মাঝে depth + heuristic সেইভ রাখবো প্রতিটি স্টেট এর জন্য। এখন আমাদের কাজ হচ্ছে একটি প্রায়োরিটি কিউ নেয়া। প্রায়োরিটি কিউ তে আমরা f এর মান অনুসারে নোড ইনসার্ট করবো। তাহলে যার f এর মান কম, সেটি আমরা আগে প্রসেস করবো।

আমরা ইনিশয়াল এ আমাদের স্টেট এর পাথ এর জন্য “0” পুশ করতে পারি path স্ট্রিং এ, depth হবে 0 এবং f এর মান হবে, depth + heuristic = ( হিউরিস্টিক হিসাব করে যত হয়, আমরা তা বসাবো )।
চাইল্ড নোড জেনারেট এর পরে, চাইল্ড এর ক্ষেত্রে depth = parent.depth + 1 এবং path এর ক্ষেত্রে আমরা যদি UP ,মুভ দেয়ার ফলে চাইল্ডটি পেয়ে থাকি, তাহলে path = parent.path + “U” এভাবে পুশ করে দিবো।
আমরা যদি আমাদের ফাইনাল স্টেট পেয়ে যাই, তাহলে আমরা path স্ট্রিংটি রিটার্ন করে দিবো, এবং এই path থেকে পরবর্তীতে আমরা ইনিশিয়াল থেকে ফাইনাল স্টেট এর গ্রিড ও প্রিন্ট করতে পারবো।

২ টি ভেক্টর নিবো open এবং close নামের। open এর কাজ হচ্ছে, আমরা যেসব নোড এখনও এক্সপান্ড করিনি, সেগুলি রাখবো। আর close এর মাঝে আমরা, যেসব নোড এর এক্সপান্ড হয়ে গেছে,সেগুলো রাখবো।open, close এর কাজ হল, অপ্রয়োজনীয় নোড নিয়ে আমাদের মাথা ব্যথা আর করা লাগবেনা। আমরা প্যারেন্ট নোড থেকে চাইল্ড বানানোর পর দেখবো যে, এই চাইল্ড আগে থেকেই open এর মাঝে আছে কিনা, যদি থাকে, এবং ঐ open এর চাইল্ড যদি আমাদের এখন পাওয়া চাইল্ড এর চেয়ে ভালো অথবা সমান হয়, তাহলে আমরা এখনকার চাইল্ড আর নোড এ পুশ করবোনা। একই কাজ আমরা close এর খেত্রেও করবো।
আর এরকম কিছু না হলে আমরা সেটি কিউ তে পুশ করবো। এভাবে কাজ চলতে থাকবে, এবং আমরা আমাদের ফাইনাল স্টেট পেলে ব্রেক করে দিবো আর পাথ এর স্ট্রিংটি থেকে আমরা ইনিশিয়াল থেকে সহজেই পাথ ও প্রিন্ট করতে পারবো।

psudocode :  A* search
path_finding : Path

N Puzzle Problem – part 3

আগের পর্ব এখানে ঃ part – 1 , part – 2

মেমরি স্পেস ( Memory Space )

আমরা আমাদের মেমরি স্পেস কমানোর জন্য স্ট্রাকচারকে একটু মডিফাই করতে পারি। আমরা একটি স্ট্রিং এর মধ্যে আমাদের প্রতি স্টেট এর প্রয়োজনীয় সব জিনিস সেইভ রাখতে পারি। 

final

যেমন চিত্রের পাযলটির জন্য আমরা ২ডি অ্যাারে তে ভ্যালুগুলি না রেখে একটি স্ট্রিং এ এভাবে রাখতে পারি ঃ string a = “123046758” । এর মাধ্যমে আমরা পরে এটিকে ইচ্ছা করলে ২ডি গ্রিড এ কনভার্ট করে আমাদের কাজ করতে পারি। এখন আমরা আমাদের প্যারেন্ট ও এভাবে স্ট্রিং এর শেষে অ্যাড করে দিতে পারি। যেমন ঃ a = “123046758L” , এর মানে হচ্ছে এই স্টেট টি Left মুভ দেয়ার পরে আমরা পেয়েছি। আর আমাদের বাকি হিউরিস্টিক ভ্যালু সেইভ। এটাও আমরা একই ভাবে করতে পারি। ব্যাপারটা তোমাদের উপর ছেড়ে দিলাম। এখন আমরা একটি ম্যাপ রাখবো এরকম ঃ map < string, bool > visited;
এই ম্যাপ এর কাজ হচ্ছে আমাদের স্টেট গুলি চেক এ রাখা। মানে একই স্টেট এ যেনো আমরা আবার ফিরে না আশি। এর একটি সুবিধা হল আমাদের অপ্রয়োজনীয় বারতি স্টেট সেইভ রাখা লাগবেনা। আমরা একবার ভিজিটেড কোন স্টেট আবার পেয়েছি কিনা, এটা ম্যাপ এর মাধ্যমে এভাবে চেক করতে পারবো। আরো একটি কাজ আমরা করবো যে, যদি unsolvable state কখনো চলে আসে, তাহলে আমরা তাকে মার্ক করে রাখবো যে এটি বাজে স্টেট, এখানে আসলে সামনে আর একে এক্সপান্ড এর কোন প্রয়োজন নেই। আর আমরা কিউ তে একের বেশি স্টেট কখনো রাখছি না, কাজেই আমাদের মেমরি বেড়ে গিয়ে রান টাইম এরর খাওয়ার সম্ভাবনা কম।

টাইম কমপ্লেক্সিটি ( Time Complexity )

বি এফ এস, ডি এফ এস এর জন্য আমাদের টাইম কমপ্লেক্সিটি হবে O ( b) । এখানে,
b = branching factor ( একটি নোড থেকে সর্বোচ্চ যে কয়টি চাইল্ড নোড জেনারেট হতে পারে, আমাদের পাযল এর ক্ষেত্রে সর্বোচ্চ ৪ টি হতে পারে {উপরে, নিচে, ডানে, বামে} )।
d = depth ( আমাদের নোড জেনারেটের সর্বোচ্চ লেভেল, )

Capture.JPG

ইটারেটিভ ডিপেনিং সার্চ এর জন্য হবে O ( bd ), O ( b) এর পরিবর্তে। অর্থাৎ আমরা ডি এফ এস মত এগিয়ে যাবো এবং যখন দরকার হবে তখন আমরা নতুন চাইল্ড তৈরী করবো।

A* সার্চ সম্পর্কে জানার জন্য এখানে দেখতে পারো ঃ A* search

N Puzzle Problem – part 2

আগের পর্ব এখানে ঃ part – 1

আগের পর্বে আমরা পাযল এর solvable state নিয়ে কথা বলেছি। এখন আমরা দেখবো কিভাবে আগালে আমরা সহজে পাযল প্রব্লেম সল্ভ করতে পারি।

image6.jpg

ছবিটি হল একটি ৮-পাযল এর স্টেট কিভাবে জেনারেট হবে তার একটি স্যাম্পল।

ডি এফ এস ( Depth First Search )

আমরা এটি সল্ভ এর জন্য প্রথমেই ভাবতে পারি ডি এফ এস (Depth_First_Search) এর কথা। এরজন্য আমরা একেকটি স্টেট থেকে সবচেয়ে ডীপ এ যাওয়ার চেষ্টা করবো। যদি আর কোন স্টেট এ না যেতে পারি, তাহলে আবার রিকার্সিভলি ব্যাক করে ফিরে আসবো। কিন্তু এর একটি বড় সমস্যা হল, আমাদের এই নোড জেনারেট এর ব্যাপারটি আমাদের ফাইনাল স্টেট থেকে অনেক অনেক দূরে নিয়ে যেতে পারে, যার কারনে আমরা এক্সপেক্টেড সলুশন পাবোতো নাই, উলটো আমাদের প্রোগ্রাম মেমরি ধারন করতে না পারার কারনে ক্র্যাশ করার সল্ভাবনা অনেক বেশি। কাজেই ডি এফ এস নরমালি করতে গেলে আমাদের জন্য তা সুবিধার হবেনা।

বি এফ এস ( Breadth First Search )

আমরা বি এফ এস এর মাধ্যমেও কাজ করতে গেলে সেইম আগের মতন প্রবলেম এ পরবো। অর্থাৎ BFS & DFS সেইম টাইপ নোড জেনারেট করবে। আমাদের তাই কিছু ট্রিক কাজে লাগাতে হবে যাতে অপটিমাল সলুশন পাওয়া যায়।

যাদের বি এফ এস, ডি এফ এস সম্পর্কে জানা নেই, তারা শাফায়েত ভাই এর ব্লগ থেকে দেখে নিতে পারো।
বি এফ এস
ডি এফ এস
একটি ছোট উদাহরন দেই। ধরি আমি পিযা ডেলিভারি দিবো একটি ১০ তলা বিল্ডিং এ। বিল্ডিং এর প্রতি তলায় আবার ১০ টি করে রুম আছে। একদিন কোন এক কারনে এলাকার মেয়র ঘোষনা দিল যে আজকে এই বিল্ডিং এর সবাইকে পিযা খাওয়ানো হবে । পুরো বিল্ডিং এ পিযা সার্ভের দায়িত্ব পরলো আমার ঘাড়ে -_- । এখন আমার কাছে ২ টি অপশন আছে। আমি প্রথেম ১ তলার সব রুম এ পিযা ডেলিভারি দিলাম, এরপরে ২ তলার সব রুম, এরপরে ৩ তলা… এভাবে ১০ তলা পর্যন্ত ডেলিভারি শেষ করলাম। আরেক কাজ করতে পারি যে, আমি প্রথমে ১ তলার একটি রুম এ পিযা দিয়ে ২ তলায় চলে গেলাম, সেখানের হাতের সবচেয়ে কাছের রুম এ পিযা দিয়ে আবার ৩ তলায়… এভাবে ১০ তলায় দেয়ার পরে আবার ১ তলায় নেমে পরর রুম থেকে একই ভাবে ডেলিভারি শুরু করলাম। এই ২ কাজের মধ্যে প্রথমটি হচ্ছে বি এফ এস, এবং পরেরটি হল ডি এফ এস। আশা করি কোনরকম আইডিয়া তোমরা পেয়েছো।

এখন আমরা কাজের কথায় আসি। আমরা ৮-পাযল সল্ভের ক্ষেত্রে আমাদের জন্য reachable state হল 9! / 2 = 1,81,440। এই ব্যাপারটি কিভাবে আসলো তা এখানে আলোচনা করছিনা। ১৫-পাযল এর জন্য এই মান 16! / 2 = 10,461,394,944,000 । বুঝতেই পারছো, ৮-পাযল শুধুমাত্র ব্রুটফোর্স দিয়ে করা গেলেও, ১৫ এর ক্ষেত্রে এটি সম্ভব না। এজন্য আমাদের লাগবে A* ( এ স্টার ) সার্চ বা ইটারেটিভ ডিপেনিং সার্চ ( Iterative Deepening A* Search or IDA* search )।
আমরা এখানে ডি এফ এস, বি এফ এস স্টাইল এর কাজ করবো, কিন্তু একটু আলাদাভাবে। আমরা একটি ফাংশন নিবো
f  ( n ) = g ( n ) + h ( n ), যেখানে,
f  ( n ) = n তম স্টেট এর ভ্যালু ( cost ) ।
g ( n ) = ইনিশিয়াল স্টেট থেকে  n তম স্টেট পর্যন্ত দূরত্ব।
h ( n ) = হিউরিস্টিক জেনারেশন এর জন্য একটি ফাংশন।
হিউরিস্টিক হল এমন একটি টেকনিক, যা আমাদের অপটিমাল সলুশন খুঁজে বের করতে সাহায্য করে। আমাদের পাযল সল্ভিং এর ক্ষেত্রে A* সার্চে আমরা এই হিউরিস্টিক ব্যবহার করবো। সহজ কথায়, এটি সিম্পল একটি ভ্যালু যা প্রতিটি স্টেট এর জন্য বের করে আমরা আমাদের সুবিধামত সামনে এগিয়ে যাবো।
ছবিটিতে আমরা দেখতে পাচ্ছি যে, ইনিশিয়াল স্টেট থেকে ৪ টি নতুন স্টেট জেনারেট হয়েছে। আমরা A* সার্রচের জন্য এই প্রতিটি চাইল্ড স্টেট এর হিউরিস্টিক ভ্যালু বের করবো। এরমধ্যে যেই ভ্যালু সবার চেয়ে কম, আমরা সেই চাইল্ড কে পরবর্তী স্টেট এর জন্য এক্সপান্ড ( Expand or Branching; creating next child for further calculation ) করবো।

 

হিউরিস্টিক ব্যবহারের সুবিধা ঃ

অপটিমাল সলুশন সহজে স্বল্প সময়ের মধ্যে বের করে নিয়ে আসা যায়,  এবং অপ্রয়োজনীয় নোড মেরে ফেলে ( removal of unnecessary nodes )।

Coding:

এখন আমরা আলোচনা করবো কোডিং নিয়ে। প্রথমেই আমরা ইনিশিয়াল স্টেট থেকে নোড এক্সপান্ড করবো। এখন যেকোন একটি হিউরিস্টিক ফাংশন আমরা ব্যবহার করবো। ইনিশিয়াল স্টেট এ g ( n ) = 0। এই স্টেট এর জন্য আমরা h ( n ) , f ( n ) বের করবো। আমরা এই প্যারেন্ট কে এক্সপান্ড করে কতগুলি চাইল্ড নোড পাবো। এবার কাজ হচ্ছে প্রতিটি চাইল্ড নোড এর জন্য আমরা f ( n ) বের করবো। এবং এর মধ্যে সবচেয়ে কম যার মান, আমরা সেটি নিয়ে সামনে এগিয়ে যাবো। এই সামনে এগিয়ে যাওয়ার মানে হচ্ছে একটি কিউ তে আমরা স্টেট গুলি জমা রাখবো। এখন আমরা এভাবে একটি স্ট্রাকচার ডিক্লার করতে পারি–>
struct node
{
int grid [ N ] [ N ] ;            // 2D grid to save the state
int h_val;                            // heuristic value of the state
char parent ;                     // parent =  { ‘U’, ‘D’, ‘L’, ‘R’ }
};
এখানে grid ২ডি অ্যাারেতে আমরা আমাদের পাযল এর স্টেট এর ভ্যালুগুলি রাখবো। h_val এর মাঝে থাকবে এই গ্রিড এর জন্য জেনারেট করা হিউরিস্টিক ভ্যালু। parent ভ্যারিয়েবল এর মাঝে আমরা প্যারেন্ট স্টেট থেকে কোন মুভ এ এই স্টেট এ এসেছি সেটি সেভ রাখবো। (এ ব্যাপারটি আমাদের জানা থাকলে ব্যাকট্র্যাক এর ক্ষেত্রে সুবিধা হবে)
এখন আমাদের একটি কিউ লাগবে যেখানে এই নোডগুলি রাখবো আমরা। শুরুতে আমরা কিউ তে আমাদের ইনিশিয়াল স্টেট এর যে পাযল দেয়া আছে তা রাখবো। এরপরে আমরা কিউ থেকে এই নোড পপ করে এর চাইল্ড জেনারেট করবো। এখন চাইল্ড জেনারেট এর সাথে সাথে আমরা প্রত্যেক চাইল্ডের হিউরিস্টিক ও জেনারেট করবো। এরপরে আমরা এই হিউরিস্টিক এর মধ্যে যার মান কম, সেই চাইল্ডকে কিউ তে পুশ করবো। এখন নরমাল বি এফ এস এ আমরা কিন্তু সব চাইল্ড ই পুশ করতাম। এখানেও তা করা যাবে, কিন্তু ১৫-পাযল এর ক্ষেত্রে খুব কষ্টকর হবে ব্যাপারগুলি ঠিকমত হিসাব নিকাশ করা। কারন, মেমরি, টাইম কমপ্লেক্সিটি এর ব্যাপারগুলি আমাদের মাথায় রাখা লাগবে। আর যেহেতু আমরা A* সার্চ ব্যবহার করছি, আমাদের অপ্রয়োজনীয় চাইল্ড নোড জেনারেট না করাই উত্তম। যখন দরকার হবে আমরা তখন জেনারেট করবো। নিচের ছবিটি খেয়াল করি ঃ 

8-puzzle-manhattan.jpg

ইনিশিয়াল স্টেট টি থেকে আমরা ৩ টি চাইল্ড নোড পেলাম। এদের f ( n ) বের করলাম। এবং এরমধ্যে সবচেয়ে কম যার মান, তাকে আমরা পরবর্তীতে কিউ তে পুশ করবো। এখন যেহেতু আমরা কিউ তে বাকি ২ টি নোড পুশ করছিনা, কাজেই আমাদের মেমরি স্পেস এক্ষেত্রে অনেক বেঁচে যাবে। কিউ তে চাইল্ড নোডটি পুশ এর সময় আমরা parent ভ্যারিয়েবল এর মধ্যে ‘L’ ক্যারেক্টারটি রাখবো, কারন 4 কে Left এ নেয়ার মাধ্যমে আমরা এই চাইল্ড নোডটি পেয়েছি। আমরা বলেছিলাম যে আমাদের এই ভ্যারিয়েবল এর মান ব্যাকট্র্যাকিং এর কাজে লাগবে। আমরা সেটি এখন আলোচনা করবো। আশা করি, এ পর্যন্ত সবকিছু বুঝে গেছো। এখন ধরি আমাদের প্যারেন্ট নোডের f এর মান এর চেয়ে প্রতিটি চাইল্ড নোডের f এর মান বেশি আসলো। এখন আমরা যেই চাইল্ড ই নেই না কেনো, ব্যাপারটি কিন্তু আসলে খারাপ হবে, কারন কম f এর মান থেকে আমরা আবার বেশি মানের দিকে আগাচ্ছি। আমাদের মেইন টার্গেট হচ্ছে যত কম মুভ এ পাযল সল্ভ করা যাএ, অর্থাৎ আমাদের f এর মান কমাতে হবে। এখন যদি এরকম অবস্থা হয়, তখন আমাদের সেই চাইল্ড নোড থেকে আবার প্যারেন্ট এ ব্যাক করতে হবে।
এখন আমাদের কাছে তো বর্তমান নোড ছাড়া আর কোন নোড নেই, তাহলে কিভাবে প্যারেন্ট এ ব্যাক করবো? এরজন্য আমাদের তখন দেখতে হবে parent ভ্যারিয়েবল এর মধ্যে কি আছে।যা থাকবে তার বিপরীত স্টেট দিয়ে ব্যাক মুভ করলে আমরা আমাদের প্যারেন্টকে আবার পাবো। মানে যদি ভ্যারিয়েবল এ থাকে ‘L’, তাহলে আমাদের ‘Right’ মুভ করতে হবে আগের স্টেট পাওয়ার জন্য। এখন আগের স্টেট পাবার পরে আবার আমরা সব চাইল্ড জেনারেট করবো। এখন যেই চাইল্ড আগে নিয়েছিলাম, সেটি না নিয়ে, তার ঠিক পরের হিউরিস্টিক মান অনুযায়ী আমরা চাইল্ড নিবো।

1

ধরি আমাদের ইনিশিয়াল স্টেট এ f = 45। এর ৩ টি চাইল্ড জেনারেট করি।

2

৩ টি চাইল্ডের মধ্যে f = 42 আমরা সিলেক্ট করবো এবং একে কিউ তে পুশ করে এক্সপান্ড করবো।

3

এখন খেয়াল করে দেখি যে, আমরা নতুন যে ৩ টি চাইল্ড পেলাম, তাদের প্রত্যেকের  f এর মান প্যারেন্ট এর f এর মান থেকে বেশি। কাজেই আমাদের এই নোড এক্সপান্ড করা আসলে ঠিক হয়নি। তাই আমাদের ব্যাকট্র্যাক করতে হবে।

2

ব্যাকট্র্যাক করে আগের অবস্থায় ফিরে আসলাম। এখন আমরা নিবো f = 43  কারন, আগের f এর মানের ঠিক পরবর্তী মান এটি।

4

এবার আমরা এই নোডকে এক্সপান্ড করে নতুন চাইল্ড পেলাম, যার মধ্যে একটির f এর মান 41, যা আগের তুলনায় ভালো মান আমাদের প্রব্লেম সল্ভিং এর জন্য। তাই আমরা এখন এটি নিয়ে কাজ করবো।

এই ছিল আসলে ব্যাসিক কোডিং এর হিন্টস। একেকজনের কোডিং স্টাইল অনুযায়ী কোডের আইডিয়া চেঞ্জ হবে, আরো বেটার আইডিয়া আসবে। পরবর্তী পর্বে আমরা দেখবো এই সার্চিং এর মধ্যে কিছু অপটিমাইজেশন আনা যায় কিনা।

পরবর্তী পর্ব : part – 3

N Puzzle Problem – part 1

posa

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

8 puzzle

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

Capture.JPG

আমরা প্রথমে বামে( 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

final

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

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

তাহলে আমাদের ইনভার্শন সংখ্যা হচ্ছে ২ যা জোড়। এবং এই পাযল এর জন্য n এর মান ৩, যা বেজোড়। এবং এটি আমাদের unsolvable puzzle state এর ১ নং শর্তটি পূরণ করেছে। কাজেই, পাযলের এই স্টেটটি সল্ভেবল একটি স্টেট। আরেকটি পাযল দেখা যাক–>
for.JPG
এখানে  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  আসলে ফাঁকা ঘর, যা আমরা আগেই বলে এসেছি।
আরো কিছু উদাহরন দেখা যাক—>


15puz115puz215Puzz315Puzz4

 

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

Sources:
https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html

পরবর্তী পর্ব পাওয়া যাবে এখানে ঃ part – 2