Why "Choice Points" introduce non-determinism in a program?
Nondeterminism is an inherently unphysical concept. If you think about the various definitions of nondeterministic computation, they always say something like one of the following:


the computation is structured as a tree and, if any of the paths through the tree succeeds, the computation succeeds, regardless of how many failures there are on other paths;
the computer "magically" considers all the options in parallel, even though there might be exponentially many of them;
the computer only considers one option but it "magically" knows which one will lead to success, if any of them will, and chooses that one.


In principle, the "choice" operator achieves nondeterminism&nbsp;&ndash; at least, it would, if we could implement it using one of the above schemes. Unfortunately, in the real world, we don't know how to do that, so we have to pick an option, see if it works out, and backtrack if it doesn't. Maybe we could do something a bit smarter than just trying the options in order but, at the end of the day, we don't know any efficient way of implementing nondeterminism on a real, deterministic, computer (which is why we don't know that $\mathrm{P}=\mathrm{NP}$).