A Recursive Puzzle

You are given a puzzle consisting of a row of squares each containing an integer, like this:

The bolded number in 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.

Assignment:

Implement a class called RecursivePuzzleSolver that includes a recursive method that would determine whether the puzzle is solvable. If the puzzle is solvable, the class must also save the solution as a vector of chars (e.g. {R, L, R, R}) that would represent the movements necessary to reach the final square in the puzzle. It must also have a print method that would print the solution in the format shown in the sample run below.

You may use the following design if you wish:

/********************** RecursivePuzzleSolver.h **********************/

#pragma once #include using namespace std;

class RecursivePuzzleSolver { private:

vector puzzle; vector solution;

bool solvable(int);

void printRow(int); public:

// stores the puzzle as passed in by user // stores the solution to the puzzle if solvable

RecursivePuzzleSolver(vector &); ~RecursivePuzzleSolver();

bool solvable();

void printPuzzle(); };

Using the above class:

#include #include #include "RecursivePuzzleSolver.h" using namespace std;

int main() {

vector puzzle; int num;

cout

cin >> num;

puzzle.push_back(num); } while (num != 0);

RecursivePuzzleSolver solver(puzzle);

if (solver.solvable()) solver.printPuzzle();

else cout

return 0; }

============== Sample Run: ==============

Please enter the puzzle: 3 641342530

Solution: [3] 6 4 1 3 4 2 5 3 0

3 6 4 [1] 3 4 2 5 3 0

3 6 4 1 [3] 4 2 5 3 0

3 6 4 1 3 4 2 [5] 3 0

3 6 [4] 1 3 4 2 5 3 0

3 6 4 1 3 4 [2] 5 3 0

3 6 4 1 3 4 2 5 [3] 0

3 6 4 1 3 [4] 2 5 3 0

3 6 4 1 3 4 2 5 3 [0]