The circle on the initial square is a marker that can move to other squares along the row. At each step in the puzzle, you may move the marker the number of squares indicated by the integer in the square it currently occupies. 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 three squares to the right because there is no room to move three spaces to the left.

The goal of the puzzle is to move the marker to the 0 at the far end of the row. In this configuration, you can solve the puzzle by making the following set of moves:

Even though this puzzle is solvable—and indeed has more than one solution—some puzzles of this form may be impossible, such as the following one:

In this puzzle, you can bounce between the two 3’s, but you cannot reach any other squares.

Write a function bool Solvable(int start, Vector & squares) that takes a starting position of the marker along with the vector of squares. The function should return true if it is possible to solve the puzzle from the starting configuration and false if it is impossible.

You may assume all the integers in the vector are positive except for the last entry, the goal square, which is always zero. The values of the elements in the vector must be the same after calling your function as they are beforehand, (which is to say if you change them during processing, you need to change them back!)

bool Solvable(int start, Vector & squares)

NOTE: This assignment MUST use RECURSION.

Please add comments to your program!

This should be done in Java and not C++