1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Backtracking Search Algorithm

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

  1. squall_890

    squall_890 New Member

    Joined:
    Feb 11, 2010
    Messages:
    1
    Likes Received:
    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
    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
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,285
    Likes Received:
    364
    Trophy Points:
    83
    Add the needed information here in the thread and reporting post is for spam only.
     
  3. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    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.
     

Share This Page