# Backtracking Search Algorithm

Discussion in 'C' started by squall_890, Nov 3, 2010.

1. ### squall_890New Member

Joined:
Feb 11, 2010
Messages:
1
0
Trophy Points:
0
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
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

Joined:
Jul 12, 2004
Messages:
15,334
377
Trophy Points:
83
Add the needed information here in the thread and reporting post is for spam only.

Joined:
Aug 6, 2004
Messages:
3,009