c++ recursion with arrays

Question

I have this project that I'm working on for a class, and I'm not looking for the answer, but maybe just a few tips since I don't feel like I'm using true recursion. The problem involves solving the game of Hi Q or "peg solitaire" where you want the end result to be one peg remaining (it's played with a triangular board and one space is open at the start.)

I've represented the board with a simple array, each index being a spot and having a value of 1 if it has a peg, and 0 if it doesn't and also the set of valid moves with a 2 dimensional array that is 36, 3 (each move set contains 3 numbers; the peg you're moving, the peg it hops over, and the destination index.)

So my problem is that in my recursive function, I'm using a lot of iteration to determine things like which space is open (or has a value of 0) and which move to use based on which space is open by looping through the arrays. Secondly, I don't understand how you would then backtrack with recursion, in the event that an incorrect move was made and you wanted to take that move back in order to choose a different one.

This is what I have so far; the "a" array represents the board, the "b" array represents the moves, and the "c" array was my idea of a reminder as to which moves I used already. The functions used are helper functions that basically just loop through the arrays to find an empty space and corresponding move. :

void solveGame(int a[15], int b[36][3], int c[15][3]){

    int empSpace;
    int moveIndex;
    int count = 0;

    if(pegCount(a) < 2){

        return;

    }
    else{

        empSpace = findEmpty(a);
        moveIndex = chooseMove( a, b, empSpace);

        a[b[moveIndex][0]] = 0;
        a[b[moveIndex][1]] = 0;
        a[b[moveIndex][2]] = 1;

        c[count][0] = b[moveIndex][0];
        c[count][1] = b[moveIndex][1];
        c[count][2] = b[moveIndex][2];

            solveGame(a,b,c);

    }

}

"backtrack with recursion, in the event that an incorrect move was made and you wanted to take that move back" - generally you want the function to enumerate the list of moves that are legal in the situation described by its parameters, then call itself passing modified parameters that describe the situation resulting from that move. The function should return an indication of success, so you can stop iterating over potential moves. Or, you may want to find the best move - iterate over all potential moves but remember which worked best, having the function return some measure. — Tony Delroy
– Tony Delroy, Commented Feb 2, 2012 at 3:40

Borealid · Accepted Answer · 2012-11-27 23:02:07Z

Here's the key concept to keep in your mind: you're not actually playing the game. What you're doing is searching for a solution - this is called a space search, because you have a space of possible boards through which you want to chart a path. To guarantee that you'll find the right answer, you have to write code that can search all possibilities - since, as you know from finding your house keys, the right answer is always in the last place you look.

So, you can't just make one recursive call and phone it in for the day. You're going to have to write code which will loop over every possible move from a given board state, and make a recursive call for each one.

From the perspective of each of those calls, their parents don't even need to exist - the current call is just examining a board which happens to be a little further into the game than the ones which came before it.

Now, when you actually run a space search, it's likely you won't really bother checking all those moves out - if you're at all lucky, you'll find the "right" move before then. So you return something from the function saying "I've got it, everybody above me bail out" and all your parent callers break their loops.

This pattern is what's called depth-first search. I'm going to illustrate by creating a hypothetical simpler game. Imagine you had to choose "A", "B", or "C" at each move, and the game lasts three moves. First you'd explore A, then AA, then AAA, then if that's no good you look at AAB, then AAC, then AB, then ABA, then ABB, then ABC, then AC, then ACA, ACB, ACC, B, BAA, and so forth.

That's why it's depth-first: you go all the way to the bottom, then backtrack as little as possible. It's not easy to recursively implement breadth-first search, which would explore A, then B, then C, then AA, then AB, then BA, then BB, and so on until it finally got to the "complete-game" states with three moves. This requires using a queue instead of the implicit stack you get from recursion.

Now, because you're using recursion, you're limited in how deep you can go: you're not generally allowed to have too many frames. So in the real world you usually make an explicit stack instead, but the heart of the algorithm doesn't much change for a depth-first search.

There are entire textbook chapters on searching algorithms ("hill climbing", "heuristics", "A-star search", and the like). Some of the algorithms are very interesting.

As for your first question, on "using a lot of iteration" - it's not how much iteration you've got but how smart it is :-). That is to say, if you don't know you have a performance issue, you probably don't need to optimize, and even then, intuition about what takes time can be bad. Get something where you can say "it works, but..." before you worry about getting something you're proud of to put on your metaphorical trophy wall. Come back here if you need help with topics like pruning, or building a better heuristic for an A-star search.

Good luck with your game program!

marcus · Accepted Answer · 2012-02-02 03:56:49Z

I don't understand how you would then backtrack with recursion

Since your recursive call is the last thing your function does, it will work just like a loop.

In order to backtrack with recursion, you will need a few things:

Keep your state in local variables or parameters (so the call stack implicitely keeps your intermediate states)
Recurse in the middle of your function, probably in a loop that tries all initial moves
Use some return code to indicate whether a solution was found. If it was, then the function will simply return again (causing a long sequence of returns); else you will be back at your previous state, ready to try some other move.

Regarding step 2, every recursive call could “think” it's simply trying all first moves, but the board passed in as an argument is already modified by the previous calls.

When a function returns, the caller can choose to “accept” the solution (i.e. return again) or try something else by making another recursion with modified parameters. [← I just explained step 3 using other words]

Jason · Accepted Answer · 2012-02-02 04:05:07Z

Think of all the possible solutions that could occur in your game as a N-ary tree-structure, where each possible progressive solution is a node in the tree. Your job in the recursive algorithm will be to recursively move through the tree, starting with the root, and searching each subtree for every node. This is the same as the recursive traversal of a binary tree, only that each node may have more than two possible choices (it would have N possible choices depending on how many choices each decision presents). If you find a child node that is not a possibility (i.e., it's not progressing towards a solution you like), then you do not keep searching down the subtree of that child node, in the same manner that you wouldn't move down the child-node of a binary search tree if the node was not on the path towards the final node you were searching for.

The final "solution" will be one of the possible paths through the N-ary tree-structure ... you search for it in the same manner that you would search for a value in a binary search tree, only you have to test more than two children to see which subtree to move down. If you find that none of the children match your solution, then you move back up to the parent node, and keep testing more of the children of the parent to the current node (i.e., that is your "backtrack").

Searching a N-ary tree would look something like the following:

template<typename T>
bool search_nary_tree(const node_t<T>* node, std::stack<const node_t<T>*>& steps)
{
    if (node->current_board == ONE_PEG)
    {
        steps.push(node);
        return true;
    }

    for (int i=0; i < node->choices.size(); i++)
    {
        if (search_nary_tree(node->choices[i]))
        {
            steps.push(node);
            return true;
        }
    }

    return false;
}

After the call to search_nary_tree returns (initially pass it the root to the N-ary tree of all possibilities in the game), the steps stack will contain pointers to all the nodes that compose the steps needed to obtain the solution.

The major downside to actually implementing your game this way is you'd have to generate all possible solutions, and that may be impossible or considerably time-consuming. If you though dynamically create the steps as you search through the tree, and never test choices that will obviously never lead to a solutions then you don't have to create the entire tree ... you can basically walk down the tree dynamically, and use the stack structure to add or pop steps off in order to keep a break-crumb of where you've been.

Collectives™ on Stack Overflow

c++ recursion with arrays

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related