backtracking backtracking is general algorithm that finds all or some solutions to any computational problem that incrementally builds candidates to the solutions at each stepwhile the valid candidates to the solution are extendedthe other candidates are discarded that iseach partial candidate is immediately abandoned after it is determined that cannot be possible and valid solution to the problem hencethe namebacktrack the concept of backtracking is applicable only to problems that support partial candidate solutions and relatively quick test to determine if the partial candidate solution can be completed to valid solution backtracking is extensively used to solve constraint satisfaction problems such as followingpuzzles like sudokueight queen' problemcrosswordsverbal arithmeticsolitaire combinational optimization problem like parsing and knapsack problem logic programming languages that internally use backtracking include iconplanner and prolog diff which is version comparing engine for the mediawiki software backtracking is said to be meta-heuristic algorithm (in contrast to specific algorithmthat is guaranteed to find all solutions to finite problem in bounded amount of time the term meta-heuristic implies that the algorithm works based on user-given procedures that define the problem to be solvedthe nature of the partial candidatesand how they are extended into complete candidates conceptualizing the backtracking process as potential search treethe partial candidates of the solution can be viewed as the nodes of the tree each partial candidate has child nodes that represent the candidates that differ from it by single extension step of coursethe leaf nodes are the partial candidates that cannot be extended further the backtracking algorithm recursively traverses the search tree in depth-first order (starting from the root nodeat each node cthe algorithm checks if can be completed to valid solution if it cannot be completedthen the entire sub-tree rooted at is pruned howeverif there is possibility that may lead to valid solution then the algorithm first checks if itself is valid solution if yesthen the algorithm declares as the valid solution otherwise it recursively enumerates all sub-trees of note the tests to determine the valid solution and children of each node are all defined by user-given procedures