void getSolution(int initial[N][N])
{
	int loopStop = 0; //for debug
	//for keeping track which goal matching board has the lowest cost
	Board* bestSolution = NULL;
	int bestCost = INT_MAX;
	//create queue to find next board to process based on lowest hueristic
	priority_queue<Board*, vector<Board*>,compare > pq, pq2;

	//find intial coords of zero
	int X,Y;
	bool foundZero = false;
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < N; j++)
		{
			if(initial[i][j] == 0)
			{
				foundZero = true;
				X = i;
				Y = j;
				break;
			}
		}
		if(foundZero)
			break;
	}
	if(debug)cout<<X<<", "<<Y<<endl;
	//create root node
	Board* root = new Board(initial,X,Y);
	//check if intial is already equal to goal
	if(root->isGoal(GOAL))
	{
		cout << "initial state is equal to the goal state";
		exit(-1);
	}
	else
	{
		//calc cost of root node and push to queue
		root->hueristic = manhattanSum(root)+root->costFromRoot;
		if(debug){cout<<"root board:"<<endl;printBoardStats(root);}
		pq.push(root);

		//for debug
		Board* lowest = NULL;

		while(!pq.empty() && loopStop < 3)
		{
			//******************************************************
			//******************************************************
			pq2 = priority_queue<Board*, vector<Board*>,compare >(pq);
			if (debug)
			{
				cout << "******************" <<endl<<"whats in priority queue"<<endl;
				while(!pq2.empty())
				{
					printBoardOnly(pq2.top());
					pq2.pop();
				}
				// for(int i = 0; i < stack.size(); i++)
				// 	pq.push(stack[i]);
				cout<<"end of priority queue"<<endl<<"**************"<<endl;
			}
			//******************************************************
			//******************************************************
			int thisMoveCost = 0;
			lowest = pq.top();
			if(debug){cout<<"\ntop should be"<<endl;printBoardOnly(pq.top());cout<<"^^^top^^^\n";}
			pq.pop();
			if(debug){cout<<"board with lowest hueristics"<<endl;printBoardStats(lowest);}

			//check if this is the best solution
			if(lowest->isGoal(GOAL) && lowest->costFromRoot < bestCost)
			{
				if(debug)cout<<"gonna set best solution"<<endl;
				bestSolution = lowest;
				bestCost = lowest->costFromRoot;
			}
			else if (!lowest->isGoal(GOAL))
			{
				//add neighbors
				if (lowest->zeroX > 0)
				{
					Board* up = newBoard(lowest);
					int newX = up->zeroX - 1;
					thisMoveCost = up->array[newX][up->zeroY];
					up->array[up->zeroX][up->zeroY] = up->array[newX][up->zeroY];
					up->array[newX][up->zeroY] = 0;
					//if(debug){cout<<"up move:"<<endl;printBoardStats(up);}
					if(!up->isEqual(lowest->parent))
					{
						up->costFromRoot = thisMoveCost + lowest->costFromRoot;
						up->manhattan = manhattanSum(up);
						up->hueristic = up->manhattan + up->costFromRoot;
						up->zeroX = newX;
						if(debug){cout<<"up move:"<<endl;printBoardStats(up);}
						pq.push(up);
					}
				}

				if (lowest->zeroY > 0)
				{
					Board* left = newBoard(lowest);
					int newY = left->zeroY - 1;
					thisMoveCost = left->array[left->zeroX][newY];
					left->array[left->zeroX][left->zeroY] = left->array[left->zeroX][newY];
					left->array[left->zeroX][newY] = 0;
					//if(debug){cout<<"left move:"<<endl;printBoardStats(left);}
					if(!left->isEqual(lowest->parent))
					{
						left->costFromRoot = thisMoveCost + lowest->costFromRoot;
						left->manhattan = manhattanSum(left);
						left->hueristic = left->manhattan + left->costFromRoot;
						left->zeroY = newY;
						if(debug){cout<<"left move:"<<endl;printBoardStats(left);}
						pq.push(left);
					}
				}

				if (lowest->zeroX < 2)
				{
					Board* down = newBoard(lowest);
					int newX = down->zeroX + 1;
					thisMoveCost = down->array[newX][down->zeroY];
					down->array[down->zeroX][down->zeroY] = down->array[newX][down->zeroY];
					down->array[newX][down->zeroY] = 0;
					//if(debug){cout<<"down move:"<<endl;printBoardStats(down);}
					if(!down->isEqual(lowest->parent))
					{
						down->costFromRoot = thisMoveCost + lowest->costFromRoot;
						down->manhattan = manhattanSum(down);
						down->hueristic = down->manhattan+ down->costFromRoot;
						down->zeroX = newX;
						if(debug){cout<<"down move:"<<endl;printBoardStats(down);}
						pq.push(down);
					}
				}

				if (lowest->zeroY < 2)
				{
					Board* right = newBoard(lowest);
					int newY = right->zeroY + 1;
					thisMoveCost = right->array[right->zeroX][newY];
					right->array[right->zeroX][right->zeroY] = right->array[right->zeroX][newY];
					right->array[right->zeroX][newY] = 0;
					//if(debug){cout<<"right move:"<<endl;printBoardStats(right);}
					if(!right->isEqual(lowest->parent))
					{
						right->costFromRoot = thisMoveCost + lowest->costFromRoot;
						right->manhattan = manhattanSum(right);
						right->hueristic = right->manhattan+ right->costFromRoot;
						right->zeroY = newY;
						if(debug){cout<<"right move:"<<endl;printBoardStats(right);}
						pq.push(right);
					}
				}
			}
			loopStop++;//for debug
		}
	}
	printSolution(bestSolution);
	cout << "The total cost for this path is " << bestSolution->costFromRoot;
}