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 এর খেত্রেও করবো।
আর এরকম কিছু না হলে আমরা সেটি কিউ তে পুশ করবো। এভাবে কাজ চলতে থাকবে, এবং আমরা আমাদের ফাইনাল স্টেট পেলে ব্রেক করে দিবো আর পাথ এর স্ট্রিংটি থেকে আমরা ইনিশিয়াল থেকে সহজেই পাথ ও প্রিন্ট করতে পারবো।

pseudocode:

	struct puzzle {
	string state, path;
	int heuristic, depth, f;
	};
	//put initial state in the priority queue Q.
	while Q not empty
	{
	puzzle u = Q.top();
	check if u.state is equal to goal state or not;
	if equals to goal state, then return u.path;
	while ( create child node )
	{
	if child already exists in the open list and the open list's child is
	as good as this child, then discard this child and continue;
	// do the above same thing for the close list too.
	set child.depth = u.depth+1;
	set child.path = u.path+{"U","D","L","R"}//according to your movement
	set child.f = child.depth + heuristic (child.state);
	push the child node in the open list;//as we will expand it in future
	}
	push the u node to the close list; // as we have expanded u above,
	// so it will go to the close list
	Q.pop(); // discard the u from queue;
	}

view raw a* pseudocode.cpp hosted with ❤ by GitHub

path_finding:

	/*
	// path printing :
	suppose you got the resulting string like this:
	0RRRDLLLRDUUULLDDRRLDDDDUUUL
	now 0 is the initial state, so we won't look at this at all.
	1. we will first do some checking, if the path size is 1, then
	the puzzle is already solved.
	2. if the path size is null, then the puzzle is unsolvable.
	// we will return an empty string if the initial state is unsolvable.
	3. we will now iterate through the string, and do the movement operation
	into our initial state and we will print the resulting state each time.
	I did it like this :
	if a 2d grid is like this : 1 2 3
	4 6 7
	5 0 8
	then the string representation of the state would be "123467508"
	*/
	#define N 4
	int posx,posy;
	char temp[N][N];
	map<char,int>movepos;
	// store the value for every move. this will help us to get direction
	void make()
	{
	movepos['U']=0;
	movepos['D']=1;
	movepos['L']=2;
	movepos['R']=3;
	}
	// these two arrays are direction array for movement
	int dx[]= {-1,1,0,0};
	int dy[]= {0,0,-1,1};
	// from 2d array temp, i generated the string in this function.
	string make_string()
	{
	string x="";
	for(int i=1; i<=3; i++)
	for(int j=1; j<=3; j++)
	x+=temp[i][j];
	return x;
	}
	// from string, creating the 2d array for movement operation
	void make_2d(string x)
	{
	int j;
	for(int i=0,p=1; i<9; i++)
	{
	if(p==4)p=1;
	if(i<3)j=1;
	else if(i>=3&&i<6)j=2;
	else if(i>=6)j=3;
	temp[j][p]=x[i];
	if(x[i]=='0')posx=j,posy=p; // posx,posy holds the blank tile's value
	p++;
	}
	}
	int main()
	{
	string s = "123476508"
	string px = a_star_search(s); // a* algo that returns path as a string
	// I saved the string in px
	cout<<"The problem can be solved in "<<px.size()-1<<" moves.They are:"<<endl;
	// as initially there was a 0 in the string, so the actual size is px.size()-1
	for(int tc=1; tc<px.size(); tc++)
	{
	cout<<"Step"<<tc<< ". ( "<<px[tc]<<" )"<<endl; //ex: step 1. ( R )
	make_2d(x); // convert the string into 2d array temp
	int pos = movepos[px[tc]];
	int nx = posx+dx[pos],ny = posy+dy[pos];
	swap(temp[posx][posy],temp[nx][ny]);
	for(int i=1; i<=3; i++) // printing the state
	{
	for(int j=1; j<=3; j++)
	cout<<temp[i][j]<< " ";
	cout<<endl;
	}
	x = make_string(); // generate the string again from temp for next child
	}
	}

view raw a* path finding.cpp hosted with ❤ by GitHub