Backtracking is a general
algorithm for finding all (or some) solutions to some
computational problems, notably
constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons each partial candidate
c ("backtracks") as soon as it determines that
c cannot possibly be completed to a valid solution.