project$-6$d

You are given a puzzle consisting of a row of squares that contain nonnegative integers, with a zero in the rightmost square. Keep in mind that it's possible for other squares to contain a zero. You have a token that starts on the leftmost square. On each turn, the token can shift left or right a number of squares exactly equal to the value in its current square, but is not allowed to move off either end. For example, if the row of squares contains these values: $[2,0,5,3,1,3,1,4,0],$ then on the first turn the only legal move is to shift right two squares, because the starting square contains a $2,$ and the token can't move off the left end. The goal is to get the token to the rightmost square. This row has a solution $($more than one$),$ but not all rows do$.$ If we start with the row $[1,3,2,1,3,4,0],$ then there is no way for the token to reach the rightmost square.

Write a recursive function named row$\_$puzzle that takes a list of integers $($the row$)$ as a parameter and returns True if the puzzle is solvable for that row, but returns False otherwise. After the function has finished, the list must be the same as it was when the function was called.

You may use default arguments and$/$or helper functions.

Your recursive function must not:

use any loops

use any variables declared outside of the recursive function

use any mutable default arguments $($see the Code Style Requirements$)$

Hint $1$: Your recursive function should always try both directions. You want it to explore all of the possibilities, and again, you should avoid trying to look ahead to see if a direction wouldn't work out at the next level of recursion. Let each level worry about itself.

Hint $2$: If there are possible cycles $($as in the first example above$),$ then there are an infinite number of valid paths, but if there is any valid path, then there is a valid path that doesn't visit any index more than once, so you only need to worry about paths that don't revisit indices. You may find memoization useful for keeping track of what indices have been visited.

Hint $2.$a: To add the memo parameter, you can use either a helper function or a default argument. If you want to add it using a default argument, see the example in the Code Style Requirements for how to avoid mutable default arguments $($since set is a mutable type$).$

Hint $2.$b: Use a set for the memoization. Testing membership in a list or tuple uses iteration, but not in a set or dictionary. Also, testing membership in a set or dictionary is faster $-$ O$(1)$ instead of O$($n$).$

The file must be named: row$\_$puzzle.py