Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Backtracking Search Algorithm (http://www.go4expert.com/forums/backtracking-search-algorithm-t23760/)

squall_890 4Nov2010 02:59

Backtracking Search Algorithm
I'm currently working on a this program which through a 2 dimensional array creates a cave that should look like this;
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

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

shabbir 4Nov2010 08:27

Re: Backtracking Search Algorithm
Add the needed information here in the thread and reporting post is for spam only.

xpi0t0s 4Nov2010 12:48

Re: Backtracking Search Algorithm
You could have a second array that stores whether or not you've visited a given square.
Then you can just recurse from any point for North, South, East or West, if any of those are unvisited.

All times are GMT +5.5. The time now is 12:42.