Question: So I've had at least two professors mention that backtracking makes an algorithm non-deterministic without giving too much explanation into why that is. I *think* I understand how this happens, but I have trouble putting it into words. Could somebody give me a concise explanation of the reason for this?

Answer: 
I'll just quote wikipedia:

> 
> A nondeterministic programming language is a language which can specify, at certain points in the program (called "choice points"), various alternatives for program flow. Unlike an if-then statement, the method of choice between these alternatives is not directly specified by the programmer; the program must decide at runtime between the alternatives, via some general method applied to all choice points. A programmer specifies a limited number of alternatives, but the program must later choose between them. ("Choose" is, in fact, a typical name for the nondeterministic operator.) A hierarchy of choice points may be formed, with higher-level choices leading to branches that contain lower-level choices within them.
> 
> 
> One method of choice is embodied in backtracking systems, in which some alternatives may "fail", causing the program to backtrack and try other alternatives. If all alternatives fail at a particular choice point, then an entire branch fails, and the program will backtrack further, to an older choice point. One complication is that, because any choice is tentative and may be remade, the system must be able to restore old program states by undoing side-effects caused by partially executing a branch that eventually failed.
> 
> 
> 

Out of the [Nondeterministic Programming](http://en.wikipedia.org/wiki/Nondeterministic_programming) article.
I like the maze analogy. Lets think of the maze, for simplicity, as a binary tree, in which there is only one path out. 

Now you want to try a depth first search to find the correct way out of the maze. 

A non deterministic computer would, at every branching point, duplicate/clone itself and run each further calculations in parallel. It is like as if the person in the maze would duplicate/clone himself (like in the movie Prestige) at each branching point and send one copy of himself into the left subbranch of the tree and the other copy of himself into the right subbranch of the tree.

The computers/persons who end up at a dead end they die (terminate without answer). 

Only one computer will survive (terminate with an answer), the one who gets out of the maze. 

The difference between backtracking and non-determinism is the following.

In the case of backtracking there is only one computer alive at any given moment, he does the traditional maze solving trick, simply marking his path with a chalk and when he gets to a dead end he just simply backtracks to a branching point whose sub branches he did not yet explore completely, just like in a depth first search. 

IN CONTRAST : 

A non deteministic computer can clone himself at every branching point and check for the way out by running paralell searches in the sub branches. 

So the backtracking algorithm simulates/emulates the cloning ability of the non-deterministic computer on a sequential/non-parallel/deterministic computer.