Interesting Java game, must use STACK

Implement a game called RightMagnetic Cave. RightMagnetic Cave is a 1-player game consisting of a row of squares of any sizes each containing an integer, like this:

The rules of the game are simple. The circle on the initial square is a marker that can move to other squares along the row. At each step in the game, you may move the marker the number of squares indicated by the integer in the square it currently occupies divided by 2 if the number is even, and moved (n/2+1) if the number is odd. The marker may move either left or right along the row but may not move past either end. For example, the only legal first move is to move the marker four squares (8/2) to the right because there is no room to move four spaces to the left. The goal of the game is to move the marker to the magnetic cave, the 0 at the far end of the row. In this configuration, you can solve the game by making the following set of moves:

Though the RightMagnetic Cave game is solvable, actually with more than one solutionsome configurations of this form may be impossible, such as the following one:

In this configuration, you will bounce between the two 10s, but you cannot reach any other square.

Requirements: 1. You will design using pseudo code and implement in java code Stackl version of the RightMagnetic game. -Has to be based on stack 2. Your solution takes a starting position of the marker along with the list of squares. Your solution should return true if it is possible to solve the game from the starting configuration and false if it is impossible. Your solution should also work for any size of the games row, and a random value in each square. You may assume all the integers in the row are positive except for the last entry, the goal square. At the end of the game, the values of the elements in the list must be the same after calling your solution as they are beforehand, (that is, if you change them during processing, you need to change them back.).

3) Briefly explain the time and space complexity for your game. You can write your answer in a separate file and submit it together with the other submissions.

816 1046 102 12 8O