How to display solution path of a maze in the correct order?

Question

I have created a maze solver program which at the end displays the path you should take to get to the exit of the maze.

However when I display the path using if(sol[i][j]==1) inside 2 nested loops to display through std::cout:

for (int i = 0; i < rows; i++)
{
    for (int j = 0; j < cols; j++)
    {
        if (sol[i][j] == 1)
        {
            cout << " (" << i << "," << j << "), ";
        }
    }
}

The indices where the sol array is 1, I get them in the order compiler traverses through the array i.e.

I get:

(1,4), (1,5), (2,4), (3,0), (3,1), (3,2), (3,3), (3,4), (4,0)

Instead of:

(1,5), (1,4), (2,4), (3,4), (3,3), (3,2), (3,1), (3,0), (4,0)

How can I display them in the right order?

Answer 1

You haven't given us enough code to help directly, but I'll give it a try.

The maze solvers I've seen tend to be recursive. You pick a start location and do something like, "Can I go left? If so, recurse from there." Any path you go down that either dead-ends or loops returns "false", or some other code to indicate this branch is not the solution.

As you recurse through "can I go right? Can I go up? Can I go down?", you eventually solve the maze -- you end at the finish point without loops or breaking other rules.

At the point, you can do one of two things. You can print the path, or you can return the path and let the top level program print it for you.

So what you might have is:

bool solveMaze(Maze theMaze, Location location) {... }

What you can do is change this:

std::vector solveMaze(Maze theMaze, Location location, std::vector pathSoFar {...}

And at each step, you append to pathSoFar, but it's a COPY, so if you fail and bounce up a step, you still have the child.

This also requires you your Maze to keep track of where you've been.

But in the end, you can then print the results of your vector.