Thread: Help needed with backtracking

  1. #1
    Registered User
    Join Date
    Oct 2003
    Posts
    27

    Help needed with backtracking

    Code:
    #include <stdio.h> 
    
    /* Entry FREE means the position is free to be traversed.
     * Entry WALL means the position can never be traversed.
     * Entry USED means the position has already been visited, 
     * and should not be visited again to avoid running in circles.
     * Such entries USED are introduced during the search.
     */
    
    #define FREE 0
    #define WALL 1
    #define USED 2
    
    /* Our maze. */
    
    #define ROWS 5
    #define COLS 7
    
    int maze[ROWS][COLS] = 
    	{ { FREE, WALL, FREE, FREE, FREE, WALL, FREE },
    	  { FREE, FREE, FREE, WALL, FREE, WALL, FREE },
    	  { FREE, FREE, WALL, WALL, FREE, FREE, FREE },
    	  { WALL, FREE, FREE, FREE, WALL, FREE, WALL },
    	  { FREE, FREE, WALL, FREE, FREE, FREE, FREE } };
    
    /* Initial length of shortest path, which is more than largest
     * possible length if any path exists. This value indicates no path exists.
     */
    
    #define NOPATH (ROWS*COLS)
    
    /* Length of shortest path. Initialized to upper bound, which would
     * indicate no path exists. 
     */
    
    int shortest = NOPATH;
    
    /* Positions of mouse and cheese. */
    
    #define MOUSE_ROW 2
    #define MOUSE_COL 1
    
    #define CHEESE_ROW 0
    #define CHEESE_COL 6
    
    /* First check if current position exists, and can be traversed (it is FREE),
     * and whether current path length is shorter than shortest path.
     * If cheese found, record length of path.
     * Otherwise, mark current position as used, and try moving up, down, left, right
     * by recursive calls, and then make position unused again.
     */
    
    void find_cheese(int row, int col, int length)
    {
      Complete function
    }
    
    int main()
    {
        find_cheese(MOUSE_ROW, MOUSE_COL, 0);
        if (shortest < NOPATH)
    	printf("Shortest path has length: %d\n", shortest);
        else
    	printf("No path exists\n");
        return 0;
    }
    This is a homework assignment. I have done a search on this forum regarding backtracking and I didn't find anything. What I need to do seems quite simple, completing the code by creating the function, because it's backtracking it has to be a recursive function. However, despite the guidance of the comments, I don't get it. What is meant by "current position"? Íf someone could explain that to me, I can finish the code myself. Thanks

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Code:
    void find_cheese(int row, int col, int length)
    {
      Complete function
    }
    There are two bits of code which go in here
    Code:
    if ( row == CHEESE_ROW && col == CHEESE_COL ) {
      if ( length < shortest ) shortest = length;
      return;
    }
    This compares your position with the objective and returns

    Now do this for all possible directions
    Code:
    if ( maze[row+1][col] == FREE ) find_cheese(row+1,col,length+1);
    Don't forget to
    - check the bounds of maze[row][col]
    - mark the current position as used before making recursive calls.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. free needed or not?
    By quantt in forum Linux Programming
    Replies: 3
    Last Post: 06-25-2009, 09:32 AM
  2. C Programmers needed for Direct Hire positions
    By canefan in forum Projects and Job Recruitment
    Replies: 0
    Last Post: 09-24-2008, 11:55 AM
  3. Alignment tutorial needed!!
    By mynickmynick in forum C++ Programming
    Replies: 11
    Last Post: 09-12-2008, 04:41 AM
  4. C++ help needed
    By Enkindu in forum Projects and Job Recruitment
    Replies: 3
    Last Post: 08-31-2004, 11:24 PM
  5. BackTracking
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 12-03-2002, 07:41 PM