Recursion-

[Allen04]

Hello everyone,

I'm trying to understand Backtracking Algorithm. As I understand, Backtracking should include Choose, Explore, and Un-Choose. My teacher gave me some of an example for Backtracking. In the first example of DiceSum problem below:

voice diceSumHelper(int dice, int desiredSum, Vector<int> &chosen)
{
    if (dice == 0)
    {
        if(sumAll(chosen) == desiredSum)
        {
            cout << chosen << endl; // base case
        }
        else
        {
            for (int i = 1; i <= 6; i++)
            {
                chosen.add(i); //choose
                diceSumHelper(dice - 1, desiredSum, chosen); //explore
                chosen.remove(chosen.size() - 1); //un-choose
            }
        }
    }
}

In this example, I understand what is base case, choose, explore and unchoose (that I noted in the code).

But in the Maze problem:

bool escapeMaze(Maze &maze, int row, int col)
{
    if(!maze.inbound(row,col))
        return true;
    else if(!maze.isOpen(row,col))
        return false;
    else
    {
        maze.mark(row,col);
        if(escapeMaze(maze,row-1,col)
        ||escapeMaze(maze,row+1,col)
        ||escapeMaze(maze,row,col-1)
        ||escapeMaze(maze,row,col+1))
        {
            return true;    
        }
        else
        {
            maze.taint(row,col);
            return false;
        }
    }
}

I don't understand what lines for the base case, choose, explore, and unchoose.
Can someone help me, please?

[jonnin]

the base cases are the 2 returns at the top. return true or false under the given conditions (which are not named anything sensible to me, but that is aside). Presumably it returns if it solved the maze (found exit) or cannot solve the maze (no exit).

choose / explore are the recursive calls. it goes up, down, left, right or something like that looking for a way out.
unchose is done by the recursion popping back out.

do you understand the maze solver algorithm on paper? Or real life? You do the 'always go left' (or right, does not matter really ..) approach?
take a look at an animation of it:
https://www.youtube.com/watch?v=8Hs5gptvBxU

the general idea is you go as far as you can until you get totally stuck or solve it. If solved, you stop. If not solved, you backtrack until you can do something new, and proceed from there... get stuck again, back up again...

[mbozzi]

Your maze program just flood-fills the maze;
It quits early when the exit is reached.

If we record the path we'll have to "un-choose" explicitly:

#include <iostream>

int constexpr rows = 8, cols = 8;

char maze[rows * cols]
{ 
  ' ',' ',' ',' ',' ',' ','X',' ',
  'X',' ',' ','X','X',' ','X',' ',
  ' ','X',' ',' ','X',' ',' ',' ',
  ' ',' ','X',' ',' ','X','X',' ',
  ' ','X','X','X',' ',' ',' ',' ',
  ' ',' ',' ','X',' ',' ','X',' ',
  ' ','X',' ','X',' ','X',' ',' ',
  ' ','X',' ',' ',' ',' ',' ','X',
};

[[nodiscard]] int constexpr xy(int x, int y) { return y * cols + x; }
[[nodiscard]] bool constexpr in_halfopen(int val, int lb, int ub)
{ return val >= lb && val < ub;}
[[nodiscard]] bool constexpr in_bounds(int x, int y) 
{ return in_halfopen(x, 0, cols) && in_halfopen(y, 0, rows); }
[[nodiscard]] bool constexpr passable(int x, int y)
{ return in_bounds(x, y) && maze[xy(x, y)] == ' '; }

int constexpr exit_square = xy(0, 7);
bool find_exit(char* maze, int x, int y)
{
  if (! passable(x, y)) return false; // can't move through walls
  if (xy(x, y) == exit_square) return true; // "base case"; found the exit
  
  maze[xy(x, y)] = '.'; // "choose"; leave a breadcrumb
  
  // "explore"; search for the exit from adjacent squares
  if (find_exit(maze, x - 1, y) || find_exit(maze, x + 1, y) ||
      find_exit(maze, x, y - 1) || find_exit(maze, x, y + 1)) 
    return true;
  
  maze[xy(x, y)] = ' '; // "un-choose"; couldn't find the exit from here
  return false;
}

int main()
{
  find_exit(maze, 0, 0); 

  for (int y = 0; y < rows; ++y)
  {
    for (int x = 0; x < cols; ++x) std::cout << maze[xy(x, y)] << ' '; 
    std::cout << '\n';
  }
}

[dhayden]

In this example, I understand what is base case, choose, explore and unchoose

You shouldn't. The algorithm is wrong. Line 18 should be before line 9. In other words, the "else" should match the "if dice == 0" instead of "if(sumAll(chosen) == desiredSum)"

It also doesn't compile. Assuming you #include the right files and add necessary "using" statements:

line 1: "voice" should be "void" and "Vector" should be "vector"
line 7: there's no default << operator for vectors.
line 13: "add" should be "push_back"
line 15 should be chosen.pop_back()