Pancake Problem and A* The pancake problem is the problem of sorting a disordered stack of pancakes so that the smallest piece is placed on the top and the largest one in the bottom. To do that, a spatula can be inserted at any point in the stack and used to flip all pancakes above it. This process can be repeated many times until we get the pancakes sorted. The cost of each flip operation equals to the number of flipped pancakes. In this assignment, we need to use A* algorithm to solve the problem and find the plan (the sequence of actions) needed to reach the solution (goal state). Assume we have n pieces of pancake; we give numbers to these pieces starting from 1 for the smallest piece to n for the largest one. The user inputs the number of pancakes (n) and then the start state (initial ordering of pancakes), then the A* algorithm is applied to print the sequence of actions that leads to the goal state (required ordering) along with the number of states expanded until the goal state is reached. For example, if user enter n=4, and the start state corresponds to the following configurations: Then,

the output should be as follows:

Flip top 2

Flip top 3

Please note that you have to accomplish the following tasks:

1. Provide a good description of a state with all needed configurations to solve the problem.

2. Build an admissible heuristic then describe why it is admissible.

3. Use this heuristic while implementing the A* algorithm. The input of the system will be (1) the number of pancakes (2) the initial state. The output should include (1) the sequence of actions leading to the goal state as described above and (2) the number of expanded states.

write c++ program