I'm currently working on a this program which through a 2 dimensional array creates a cave that should look like this;

B B B B B B

B T T T T B T = taversable squares in the cave

B T X X T B X =untraversable squares

B T T T T B B = border of the cave

B T T T T B

B B B B B B

Rules:

1. Always begin in square (1,1) lower left 'T'

2. Always move square to square either horizontally or vertically, never diagonally.

3. Never visit a square more than once, except square(1,1) when exiting the cave.

4. Squares marked X cannot be visited.

5. When traveling through the cave use 'V' to represent that the square has been visited.

The function main() should ensure that the following steps are carried out either through

direct instructions or function calls as appropriate.

1. Initialize maxX(maximum x coordinates), maxY(maximum y coordinates), and caveInfo(2-D array) to the input values

2. Set the caveInfo border.

3. Determine the total number of required moves.

4. Initialize the current state of the computation to reflect the start conditions of the

problem: starting in (1,1) which should be marked as visited, with no moves yet

made.

5. Invoke the solves function to see if either an East move or North move from the

start position will lead to a solution (obviously, we already know West and South

are impossible from the lower left corner).

if (solves(using East move) || solves(using North move)) then output moves

else output “Cave untraversable”

6. Produce the correct output depending on the outcome of step 5.

Besides main(), your program must contain the following functions as a minimum.

1. The solves(...) function. What type of value should it return to represent success

or failure?

2. A function that counts traversable or untraversable squares as appropriate.

3. A function that outputs the sequence of moves of a complete, legal traversal. the

format of the output should be one move per line. For example, the first few lines

of output for our sample cave would be:

Start (1,1)

East (2,1)

North (2,2)

The final line should be

South (1,1)

You may define additional helper functions as desired. A particularly useful helper

function might be a debugging function that displays the state of the cave at a given point

during the computation. That way you can see if you are properly marking squares as

visited and have set the border correctly.

My current problem I'm having is with the backtracking search algorithm I can't seem to figure out how to systematically check the possible moves from the current position, so any help would be greatly appreciated

B B B B B B

B T T T T B T = taversable squares in the cave

B T X X T B X =untraversable squares

B T T T T B B = border of the cave

B T T T T B

B B B B B B

Rules:

1. Always begin in square (1,1) lower left 'T'

2. Always move square to square either horizontally or vertically, never diagonally.

3. Never visit a square more than once, except square(1,1) when exiting the cave.

4. Squares marked X cannot be visited.

5. When traveling through the cave use 'V' to represent that the square has been visited.

The function main() should ensure that the following steps are carried out either through

direct instructions or function calls as appropriate.

1. Initialize maxX(maximum x coordinates), maxY(maximum y coordinates), and caveInfo(2-D array) to the input values

2. Set the caveInfo border.

3. Determine the total number of required moves.

4. Initialize the current state of the computation to reflect the start conditions of the

problem: starting in (1,1) which should be marked as visited, with no moves yet

made.

5. Invoke the solves function to see if either an East move or North move from the

start position will lead to a solution (obviously, we already know West and South

are impossible from the lower left corner).

if (solves(using East move) || solves(using North move)) then output moves

else output “Cave untraversable”

6. Produce the correct output depending on the outcome of step 5.

Besides main(), your program must contain the following functions as a minimum.

1. The solves(...) function. What type of value should it return to represent success

or failure?

2. A function that counts traversable or untraversable squares as appropriate.

3. A function that outputs the sequence of moves of a complete, legal traversal. the

format of the output should be one move per line. For example, the first few lines

of output for our sample cave would be:

Start (1,1)

East (2,1)

North (2,2)

The final line should be

South (1,1)

You may define additional helper functions as desired. A particularly useful helper

function might be a debugging function that displays the state of the cave at a given point

during the computation. That way you can see if you are properly marking squares as

visited and have set the border correctly.

My current problem I'm having is with the backtracking search algorithm I can't seem to figure out how to systematically check the possible moves from the current position, so any help would be greatly appreciated