Question
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
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
class RecursivePuzzleSolver { private:
vector
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
bool solvable();
void printPuzzle(); };
Using the above class:
#include
int main() {
vector
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]
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started