Backtracking

Backtracking is a general algorithmic technique for solving computational problems by incrementally building candidates and abandoning a candidate as soon as it is determined that the candidate cannot possibly be completed to a valid solution. In pattern matching, backtracking manifests when a regular expression engine tries one possible binding, fails, and rewinds to try another — an elegant idea that becomes pathological when the search space explodes. The technique is not limited to parsing; it underlies search algorithms in constraint satisfaction, theorem proving, and game playing. Its fundamental flaw is also its strength: backtracking is complete but rarely efficient.