Issue in my recursive algorithm for finding all shortest, unique paths

I've been working on a recursive algorithm that is supposed to find all the shortest, unique possible paths to get from point A to point B in an n by m matrix. Currently I have it to the point where my algorithm can find all possible paths starting from a single direction. However when I get back to the first stack frame where the algorithm begins, I'm stuck with whatever directions have been taken in the previous actions taken in the first frame. I've determined that this is due to the fact that my movement function takes a reference to the current solution I'm working with. I think what needs to happen is that I need to further localize my parameters so that I in essence can start again from square one. I'm just jnot sure how to do that though because any time that I try to move away from passing references to my movement algorithm, the "solutions" come back as one letter.

Any tips on making the first stack frame more independent from my movement algorithm?

{void Robot::findTreasureHelper(Board whichBoard, int x, int y, std::string solution)

++callCount;

if (x == TREASURE_X && y == TREASURE_Y)
{
    ++numSolutions;
    return;
}

if (move(whichBoard, 'N', x, y, solution))
    findTreasureHelper(whichBoard, x, y, solution);
if (move(whichBoard, 'E', x, y, solution))
    findTreasureHelper(whichBoard, x, y, solution);
if (move(whichBoard, 'S', x, y, solution))
    findTreasureHelper(whichBoard, x, y, solution);
if (move(whichBoard, 'W', x, y, solution))
    findTreasureHelper(whichBoard, x, y, solution);

{bool Robot::move(Board& whichBoard, const char& whichDir, int& x, int& y, std::string& solution)

bool didMove = false;

int direction = 1;
if (whichDir == 'S' || whichDir == 'E')
    direction = -1;
int  *coordinate = &x;
if (whichDir == 'N' || whichDir == 'S')
    coordinate = &y;

//check bounds, consecutive movements, and whether robot has been here on this solution
if (x == TREASURE_X && y == TREASURE_Y)
    *coordinate += direction;
else if (*coordinate - direction >= 0 && *coordinate - direction < whichBoard.board.size() 
    && *coordinate - direction < whichBoard.board[y].size() && moveCount < CONSECUTIVE_MOVES)
{
    *coordinate -= direction;
    //check blocks and previously been here
    if (whichBoard.board[y][x] == -1 || whichBoard.board[y][x] == currentSolutionIndex)
        *coordinate += direction;
    else if (x == TREASURE_X && y == TREASURE_Y)
    {
        switch (whichDir)
        {
        case 'N':
        case 'S':
            //check consecutive moves
            solution.back() == 'N' || solution.back() == 'S' ? ++moveCount : moveCount = 0;
            //add correct character to solution
            direction == 1 ? solution += 'N' : solution += 'S';
            break;
        case 'E':
        case 'W':
            //check consecutive moves
            solution.back() == 'E' || solution.back() == 'W' ? ++moveCount : moveCount = 0;
            //add correct character to solution
            direction == 1 ? solution += 'W' : solution += 'E';
            break;
        }
        //*coordinate += direction;
        this->solutions.push_back(solution);
        didMove = true;
    }
    else // complete the move randomly
    {
        switch (whichDir)
        {
        case 'N':
        case 'S':
            //check consecutive moves
            solution.back() == 'N' || solution.back() == 'S' ? ++moveCount : moveCount = 0;
            //add correct character to solution
            direction == 1 ? solution += 'N' : solution += 'S';
            break;
        case 'E':
        case 'W':
            //check consecutive moves
            solution.back() == 'E' || solution.back() == 'W' ? ++moveCount : moveCount = 0;
            //add correct character to solution
            direction == 1 ? solution += 'W' : solution += 'E';
            break;
        }
        didMove = true;
        whichBoard.board[y][x] = currentSolutionIndex;
    }

}
return didMove;

}