In this C exercise, we will solve a puzzle using recursion. Specifically, the puzzle involves traversals of an array. We are given a puzzle consisting of a row of squares each containing an integer, like this:

Figure 1: A puzzle configuration.

The circle on the initial square is a marker that can move to other squares along the row. At each step in the puzzle, we 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, we can solve the puzzle by making the following set of moves:

Figure 2: Steps to solve the puzzle.

This problem should be solved recursively. Recursion involves calling a function within itself with input that is closer to its base case. The first step is to define your base case (i.e. when have I solved the problem to the point where there are no more subproblems?). The next step is to determine your recursive call - the key to this step is to ensure your recursive call is getting closer to your base case to avoid infinite recursion. Specifically for this puzzle, we will need to keep track of which indices have been visited to avoid an infinite traversal (memoization). In our code, we use an array to present the configuration of the puzzle.

1

int a[] = {3, 6, 4, 1, 3, 4, 2, 5, 3, 0}; 

We need to implement the following function.

int puzzle(int a[], int n, int idx, int v[], int p_flag) { 

}

Here a[ ] is the array that configures the puzzle, n is the size of the puzzle, idx is the location of the marker in the array. v[ ] is an array that indicates which indices have already been visited. If the value of v[i] is 1, then the index i has been visited; otherwise, it has not been visited yet. Last, p flag indicates whether to print out a solution to the puzzle.

This function returns 1 if the puzzle is solvable. Otherwise, the functions returns 0. Below is the main() function of the program; note how the above function is used.

int main() {

 int a[] = {1, 2, 3, 4, 5, 6, 7, 0}; int v[8] = {0}; if(puzzle(a, 8, 0, v, 1)) 

 printf(" This puzzle is solvable. "); else 

 printf(" This puzzle is not solvable. "); 

 int b[] = {1, 2, 1, 3, 2, 0, 1, 0}; int v1[8] = {0}; 

 if(puzzle(b, 8, 0, v1, 1)) printf(" This puzzle is solvable. "); 

 else printf(" This puzzle is not solvable. "); 

 int n = 1024; int c[n]; int v2[n]; 

int i, j;

 for(i = 0; i < n; i++) c[i] = i + 1; 

 for(j = 1; j <= n; j++) { 

 for(i = 0; i < n; i++) v2[i] = 0; 

 if(puzzle(c, j, 0, v2, 0)) printf("%d ", j); } 

return 0; }

2

Below output can be used to check correctness of our code.

$ ./puzzle 12345670 7310 This puzzle is solvable. 12132010 76310

This puzzle is solvable. 1 2 4 

8 16 32 64 128 256 512 1024 

Note for the first two puzzles, solutions are shown. The solutions are shown in the reverse order. For example, the solution for the first puzzle is

7310

which indicates that indices 0, 1, 3, and 7 are visited consecutively. Read the rest of the output, and try to figure out why these numbers are printed by reading the code in the

main() function.