Maze Director Recording Backtracks

Question

I earned my maze solution program to work, but it seemed to include tracked spaces (the places it hit and hit the wall so it turned) on the final path of the solution it outputs. Here is an example:

How can I prevent this in my current implementation below:

int dir = 4; bool visited[Max_Maze][Max_Maze][dir]; for (row = 0; row < size; ++ row) { for (col = 0; col < size; ++ col) { for (dir = 0; dir < 4; ++ dir) { visited[row][col][dir]=false; } } } bool notSolved = true; int path = 0; row = 0; col = 0; rowStack.push(row); colStack.push(col); while (notSolved) { //from perspective of person looking at maze on screen if (((row-1)>=0)&&(maze[row - 1][col] == 0)&&(visited[row][col][0]==false)) { // if that space is not out of bounds and if you can go up // and you have not gone in that direction yet, go up visited[row][col][0] = true; row--; rowStack.push(row); colStack.push(col); path++; } else if (((col+1)<size)&&(maze[row][col + 1] == 0)&&(visited[row][col][1]==false)) { //else if you can go right etc., go right visited[row][col][1] = true; col++; rowStack.push(row); colStack.push(col); path++; } else if (((row+1)<size)&&(maze[row + 1][col] == 0)&&(visited[row][col][2]==false)) { //else if you can go down etc., go down visited[row][col][2] = true; row++; rowStack.push(row); colStack.push(col); path++; } else if (((col-1)>=0)&&(maze[row][col - 1] == 0)&&(visited[row][col][3]==false)) { //else if you can go left etc., go left visited[row][col][3] = true; col--; rowStack.push(row); colStack.push(col); path++; } else { //if stuck if (path == 0) { cout << "No Solution Path" << endl; notSolved = false; } else { rowStack.pop(); colStack.pop(); row = rowStack.top(); col = colStack.top(); path--; } } if((maze[row][col] == 0) && (row == (size - 1) && col == (size - 1))) { //if we reached an exit cout << "Solution Path:(in reverse)" << endl; for (int i = 0; i <= path; i++) { cout << "row:" << rowStack.top() << " col:" << colStack.top() << endl; rowStack.pop(); colStack.pop(); } notSolved = false; } } 

Need simple fixes or a complete restructuring?

Answer 1

When the solver goes to a dead end, he writes that he "settled to the right of (R, C)" because your visited array is three-dimensional. But he never writes that he "visited from the left of (R, C + 1)." Therefore, he thinks that he needs to move to the same position twice if he does not perform the same movement twice (and this is not so, since he moves to the left when he retreats, and not to the right).

It looks like it will work fine, as if you changed the visited one to be a two-dimensional array and only record positions , not move. Then each square that you visited blocks further movement, but this is good, because if the right decision requires returning to this square, you will eventually get into another matter to return to it, and from there three should never be unvisited area to explore.

Answer 2

Without commenting on your specific solution, you can think of reusing the first depth search as a standard algorithm, which, I think, you will agree, is somewhat more clear:

 boolean dfs (State s) { if (end_state(s)) { return true; } vector<option_t> options = generate_moves(s); for (vector<option_t>::iterator it = options.begin(); it != options.end(); it++) { make_move(s, it); boolean found = dfs(s); if (found) { cout << s << endl; } undo_move(s, it); if (found) return true; } return false; } 

As you can see, this will work as long as you can create:

• some kind of class state that contains the current state of the maze
• End_state function that knows when State is in solution
• Function generate_moves, which can find all parameters of the current state
• make_move, which can apply the transition to your state.
• undo_move, which can cancel the motion against the state
• you define option_t so that it represents a move option
• define the operator <<for the state

I can tell you that, of course, the solution that I give you has no problems with printing backspaces (it should be clear from the code too).