Recursive maze solver

Question

Up for review today is some C++11 code to recursively search a maze for a path to a specified goal. This one shows dead-ends it explored on the way to finding the solution.

#include <iostream>
#include <vector>
#include <string>
enum { GOAL = '*', SPACE = ' ', WALL = '#', TRIED = '!', USED = '+' };
class maze {
 std::vector<std::string> data;
public:
 char &operator()(size_t x, size_t y) {
 return data[y][x];
 }
 friend std::istream &operator>>(std::istream &is, maze &m) {
 std::string temp;
 while (std::getline(is, temp))
 m.data.push_back(temp);
 return is;
 }
 friend std::ostream &operator<<(std::ostream &os, maze const &m) {
 for (auto const &s : m.data)
 os << s << '\n';
 return os;
 }
 size_t y_dim() { return data.size(); }
 size_t x_dim() { return data[0].size(); }
};
bool solve(maze &m, size_t x = 0, size_t y=0) {
 if (x < 0 || y < 0 || x >= m.x_dim() || y >= m.y_dim())
 return false;
 if (m(x, y) == GOAL) 
 return true;
 if (m(x, y) != SPACE)
 return false;
 m(x, y) = USED;
 bool solved 
 = solve(m, x - 1, y)
 || solve(m, x + 1, y)
 || solve(m, x, y - 1)
 || solve(m, x, y + 1);
 if (!solved)
 m(x, y) = TRIED;
 return solved;
}
int main(){
 maze m;
 std::cin >> m;
 solve(m);
 std::cout << m; 
}

Input is a simple text file of walls, spaces, and a goal, such as:

 #######
# # ##
# #### #
# ##
# ### ###
##### *#

Searching always commences from position 0, 0 (i.e., the top, left corner).

• Jamal: I don't have too much to say here. One obvious thing is that y_dim() and x_dim() should be const.
• Morwenn: I'm not sure about it, but wouldn't it be a good idea to manually control the type of the enum with enum: char { ... }? Since you use std::string, I don't think that there is any advantage with letting it be implementation defined.

Answer 1

A few items:

solve should be a member function

Since solve actively manipulates the maze and makes no sense outside the context of a maze, it really ought to be a member function.

size_t is unsigned

Since size_t is an unsigned type it will never be less than zero and so checks for x < 0 || y < 0 within solve should be removed.

Several methods should be const

The y_dim() and x_dim() methods should be declared const.

The enum should be inside maze

If solve becomes a member, then the enum should be made a private member of maze.

Add user validation to operator>>

The code seems to assume that each line is the same length and that it consists solely of valid characters. Interestingly, it accepts (but cannot solve) its own source code as though it were a maze. Perhaps it is! :)

Replace y_dim() and x_dim()

The only reason to have the x_dim and y_dim functions is to check to make sure that the passed coordinates are within bounds. For that reason, what would make more sense, I think, is to have a bool maze::in_bounds(size_t x, size_t y) const function instead.

Make operator() private

Because the operator() returns a reference to internal data, it should be made private. Since the only user of the function is solve this works if solve is also made a member function.

Answer 2

Try and engage the move constructor:

m.data.push_back(temp);

Because temp is a named variable it will hit the version that uses const& T. To try and get the alternative version that engages the move constructor add std::move

m.data.push_back(std::move(temp));

The input operator does not make any attempt to make sure each line is the same size.

size_t x_dim() { return data[0].size(); }

So the above may not be accurate.
You can add a fake set of cells at the top/bottom/left/right of type 'WALL' then you don't need the test if (x < 0 || y < 0 || x >= m.x_dim() || y >= m.y_dim()) as it can never reach outside the bounds of the maze (this can be forced to be true because it is part of the code and not part of the user input). This means you don't need y_dim() as that is the only use case.

My main issue is that solve() actually mutates the maze object. Some form of visitor pattern may be a more re-usable technique, or solve() would be better as a member of maze().

• Edward: Good catch on the use of std::move. I missed that one.