[Crowz]

http://en.wikipedia....king#Pseudocode
I am using this pseudocode as a reference for the rest of my program.
However, I cannot seem to translate the first and next things. All the other functions are made and functioning.
Could I have some help?
Right now, all I really have is

int guess=1;
int start=0;
for(int i =0; i<9; i++) {
   for(int j=0;j<9;j++) {
      start++;
   }
}

By the way, this uses a 2 dimensional [9][9] integer array.

[blackcompe]

Backtracking is a very general concept that basically means your exploring all possible solutions to a problem, creating a solution tree (some of which may actual be correct). As soon as you hit a wall in your path, you go back to the last branch and you try another path. If all the paths in that branch fail, go back to the next higher branch in the tree and try all of its paths.

This is the easiest way to visualize backtracking.

To answer your question, there's really no need to actually define a first and next function, they're are implicit in your backtracking algorithm. The Wiki example is an abstract explanation, with no practical use really. Their psuedocode never is. If you were to actually write those functions, they would depend on the problem at hand. If anything, you should start by giving a description of your problem first. When you understand your backtracking algorithm on a conceptual level, the code will follow.

A common backtracking problem is permutation generation. E.g.

All perms for {a,b,c}

0. Start the root of the tree. I can choose a, b, or c.
1. I choose to start at a. Then, I can go to b or c.
2. I choose b. Now the only other letter left is c.
3. My first perm is "abc".

4. Now I'm at c. Lets go back up the path to b.
5. I chose c already, so there's nothing else left to try. Lets go back up the path again to a.
6. Now my options are again b and c. Let's choose c first this time.
7. I'm at c and the only other letter left is b.
8. My second perm is "acb"

9. I'm at b, no more letters to pick, go back up the tree to c. No more letters to pick since I've already done b. Go back up the tree to a. I've already generated "abc" and "acb" and there's no others to generate, so go back up the tree to the root.
10. Since I've done all perms starting with "a", I choose another path starting with b. And the whole process repeats starting at step 1 again.

There are many problems that can be solved that way, albeit slowly, but surely. TSP, Knapsack, permutations: basically any optimization problem.

If at any time you find yourself solving the same sub-problems in your algorithm, you can use memoization (a cache) to speed things up significantly.

This post has been edited by blackcompe: 10 February 2012 - 02:03 AM

[macosxnerd101]

I really like blackcompe's explanation with Trees. Tree traversals are always involved with backtracking. However, usually recursion is used, which relies on the Java call stack. My tutorial Data Structures: Recursion, Stacks, and Trees. I have a tutorial on backtracking as well. Hope this helps some.