Backtracking

CORE DEFINITION

Backtracking is a type of brute-force search. For certain computational problems, backtracking is a general algorithm that can find all (or some) solutions, especially suitable for constraint satisfaction problems (in solving constraint satisfaction problems, we gradually construct more candidate solutions, and after determining that a certain partial candidate solution cannot be completed into a correct solution, we abandon continuing to search this partial candidate solution itself and its sub-candidate solutions, and instead test other partial candidate solutions). In classic textbooks, the eight queens problem demonstrates the use of backtracking. (The eight queens problem is to find all distributions of eight queens on a standard chessboard such that no queen can attack another.) Backtracking adopts the idea of trial and error, attempting to solve a problem step by step. In the process of solving step by step, when it finds through attempts that the current partial answer cannot yield an effective correct solution, it will cancel the previous step or even several steps, and then try again through other possible partial answers. Backtracking is usually implemented with the simplest recursive method. After repeating the above steps, two situations may occur: