How do you solve the frog puzzle with reccurtion

Question

i need to solve the riddle where you have five frogs facing another five and they need to cross the same road. a frog can move one step at a time. he cant go backwards. and he can leap over another frog asuming the space behind that frog is empty. and the puzzle starts with one empty space between the two rows of frogs

now solving it on paper is easy but i need a program to sove it using recurtion in c++

Answer 1

how about like this:
have an array that will include all of the toads and frogs locations
when a frog is marked as 1 a toad is marked as 2 and the empty space is 0.
the location of each frog/toad is according to its location in the array.
for example the array will print as
1 1 1 1 1 0 2 2 2 2 2

make a recursive function that receives the array and the index of the cell with 0 (the empty spot)

in every iteration u can only move either a frog or a toad
decide to move a frog and check if its a bad situation (i think the only 2 situations where the movemenet isnt good is when you end up with either 1 2 2 0 or 0 1 1 2)
if it brings you to a bad situation move a toad instead
note that with every iteration you can only move 1 specific toad - the left most toad on the right side of the empty space
or 1 specific frog - the right most frog on the left side of the empty space.

once you made a move call the same function with the 'new' array and the new empty space

dont forget to add a finishing 'if' for the recursion iterations

it might be worth to print the location of all the frogs after each iteration - will help visualize the solution for the user and help you find mistakes along the way

Answer 2

I understand where you're coming from, but the issue remains that I am required to use only recursion to solve this. So I can't use iteration like you suggested.

Answer 3

when i say iteration i mean recursion iteration
meaning every iteration is every time you are calling the function

the function should be something like
void move(int* arr,int emptyplace)
{
if( something to check if the problem is already solved)
if( moving a frog is ok)
move a frog
else
move a toad
print_new_array
move(arr, newemptyplace)
}

Answer 4

i thought a bit more about the code you need to use - every recursion iteration you need to move all the ones you can - until you reach a position where 1 0 1 and you need to stop
the same for toads
since you need to use recursion - u can use a recursion for moving toads and frogs
should look like
the function should be something like
void move(int* arr,int emptyplace)
{
if( something to check if the problem is already solved)
newepmtyplace = move_frogs_till_101(int* arr,int emptyplace) /* another recursive function for moving frogs */
newepmtyplace = move_toads_till_202(int* arr,int emptyplace)/* another recursive function for moving toads */
move(arr, newemptyplace)
}