C++

Forum

 
Recursive & Iterative Maze solver

ZedjayCoder (24)
I am working on solving a maze via recursion and iteration but it appears that the recursive function doesn't know when to stop (It reaches the exit marked by an 'e'). The problem with the iterative solution is that it doesn't seem to even push things into the stack.

As an example, the mouse will try to get to the 'e' but won't know when to stop when solving recursively
m = mouse (start position)
e = exit
111111
1m0001
1000e1
100001
100001
111111
Please let me know if I need to include more of my code in order to get a better answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 
bool Maze::blockedCell(int x, int y)
{
	if(maze[x][y] == '1')
		return true;
	else 
		return false;
}

void Maze::Move(Cell& mouse, char key)
{
	int x, y;
	x = mouse.getX();
	y= mouse.getY();

	if(key == 'R')
	{
		maze[x][y += 1];
	}
	else if(key == 'L')
	{
		maze[x][y -= 1];
	}
	else if(key == 'D')
	{
		maze[x+=1][y] ;
	}
	else if(key == 'U')
	{
		maze[x -= 1][y];
	}
	else 
		cout << "Error check instance of Move()! \n";

	mouse.setX(x);
	mouse.setY(y);
}

 void Maze::solveRecursive(Cell& mouse)
{
	if(mouse.getX() == exitPosition.getX() && mouse.getY() == exitPosition.getY())
	{
		cout << exitPosition.getX() << " " << exitPosition.getY() << endl;
		return;
	}
	else {
	if(!blockedCell(mouse.getX() , mouse.getY() + 1) && (maze[mouse.getX()][mouse.getY() + 1] != '.'))
	{
		maze[mouse.getX()][mouse.getY()] = '.';
		Move(mouse, 'R');
		solveRecursive(mouse);
		
	}
	if(!blockedCell(mouse.getX() , mouse.getY() - 1) && (maze[mouse.getX()][mouse.getY() - 1] != '.'))
	{
		maze[mouse.getX()][mouse.getY()] = '.';
		Move(mouse, 'L');
		solveRecursive(mouse);
	}
	if(!blockedCell(mouse.getX() + 1 , mouse.getY()) && (maze[mouse.getX() + 1][mouse.getY()] != '.'))
	{
		maze[mouse.getX()][mouse.getY()] = '.';
		Move(mouse, 'D');
		solveRecursive(mouse);
	}
	if(!blockedCell(mouse.getX() - 1 , mouse.getY()) && (maze[mouse.getX() - 1][mouse.getY()] != '.'))
	{
		maze[mouse.getX()][mouse.getY()] = '.';
		Move(mouse, 'U');
		solveRecursive(mouse);
	}
	}
}

void Maze::solveIterative(Cell mouse)
{
 stack<Cell> moves;

 moves.push(Cell(mouse.getX(),mouse.getY()));

 while( currentPosition(mouse.getX(), mouse.getY()) != 'e')
 {
	 moves.push(Cell(mouse.getX(),mouse.getY()));
  if(!blockedCell(mouse.getX() + 1 , mouse.getY()))
  {
		moves.push(Cell(mouse.getX() + 1,mouse.getY()));
		//maze[mouse.getX()][mouse.getY()] = 'm';
   
  }

  if(!blockedCell(mouse.getX() - 1 , mouse.getY()))
  {
   moves.push(Cell(mouse.getX() - 1,mouse.getY()));
   //maze[mouse.getX()][mouse.getY()] = 'm';
   
  }
  
  if(!blockedCell(mouse.getX(), mouse.getY() - 1))
  {
   moves.push(Cell(mouse.getX(),mouse.getY() - 1));
   //maze[mouse.getX()][mouse.getY()] = 'm';
   
  }

  
  if(!blockedCell(mouse.getX(), mouse.getY() + 1))
  {
   moves.push(Cell(mouse.getX(),mouse.getY() + 1));
   //maze[mouse.getX()][mouse.getY()] = 'm';
   
  }

  if (!moves.empty())
  {
	  cout << "failure" << endl;
  }


  mouse = moves.top();
  moves.pop();


 }
}
Last edited on
cire (8284)
In the iterative version, you make no effort not to revisit cells you've already visited, leading to an infinite loop.

In the recursive version, your ifs execute consecutively regardless of whether or not a solveRecursive invocation is successful in reaching your target. Ask yourself what happens when you arrive at your target on line 50, and execution moves on to line 53.
Topic archived. No new replies allowed.