Backtracking: Constraint satisfaction problems (CSPs) are mathematical problems in which a set of objects must satisfy a certain number of constraints.
These problems, widely studied in operations research and artificial intelligence, require specific solution methods such as backtracking or constraint propagation algorithms. Examples of famous problems that can be modeled by a CSP are the backpack problem, the eight ladies problem or sudoku.
What is backtracking?
Backtracking is a search technique for solving complex problems by recursively exploring combinations of possible choices to arrive at a solution.
It is commonly used to solve search, optimization, planning and gaming problems. Backtracking is based on an in-depth search that explores options until a solution is found or all possibilities have been exhausted.
Tree-like data structure
Backtracking is based on a tree-like data structure, where each node represents a decision step in the problem-solving process. The branches of the tree represent the different options or decisions possible at each stage.
As the algorithm progresses, it performs an in-depth traversal of the different branches of the tree to assess whether or not they lead to a solution.
Algorithm sequence
Backtracking follows a recursive approach to solving a problem. Here are the different stages in the execution of this algorithm:
- Step 1 – Choice: The algorithm begins by making a choice among all possible options. This choice is based on the current state of the problem.
- Step 2 – Validation: After making a choice, the algorithm checks that the problem’s constraints are still respected. If this is the case, it returns to step 1 to continue the in-depth path. If not, it backtracks to try another alternative. This is one of the differences with basic brute-force solving algorithms: backtracking can eliminate branches without having to explore them all the way.
- Step 3 – Backtracking: If at any point the algorithm realizes that none of the choices in a branch will lead to a solution, or that it has explored all possible options without arriving at a valid final state, it goes back to explore other alternatives. This involves going back up the decision tree to explore other, as yet unexplored, branches.
- Step 4 – Solution: The algorithm continues to traverse the tree branch and make choices, repeating steps 1 to 3 until it reaches a valid solution. A solution is generally defined as a final state of the problem that satisfies the constraints or objectives set.
Example of backtracking application
To illustrate the concept of backtracking, let’s take a concrete example: solving a sudoku grid. In a sudoku game, the aim is to fill in a 9×9 grid in such a way that each row, column and 3×3 sub-grid contains all the numbers from 1 to 9 without repetition. Here we’ll use a 4×4 grid to simplify the illustration.
Backtracking can be used to solve a sudoku as follows:
Step 1 – Choice: Start by choosing an empty square in the grid. Fill this square with a possible number (from 1 to 4).
Step 2 – Validation: Check whether the grid is still valid after making this choice. If so, return to step 1. If not, go back and try another number in the box.
Here, the noted 1 doesn’t comply with the rules, so we try a 2 instead.
Step 3 – Backtracking: If at any point you can’t find a valid number for a square, go back and try another value in the previous square, and so on.
In this case, you can’t place any numbers within the rules, so you have to change the number just before it, and those before it if necessary.
Step 4 – Solution: Repeat steps 1 to 3 until all squares are filled in and meet the game’s constraints, which means you’ve found a valid sudoku solution.
Advantages of backtracking
Backtracking offers several advantages as a problem-solving approach:
- Completeness: It ensures that all possible valid solutions are explored, making it useful for the search for optimal solutions.
- Efficiency: Backtracking can be very effective, especially in problems with strong constraints, enabling certain options to be quickly eliminated.
- Adaptability: It can be applied to a variety of problems, as it is based on a general tree structure.
The limits of backtracking
Despite its advantages, backtracking has certain limitations:
- Combinatorial explosion: In some problems, the number of combinations to be explored can increase exponentially, as in the case of the travelling salesman problem, where if a path is calculated in 1 microsecond, it takes almost two millennia to calculate all the paths passing through 20 points.
- Complexity: The implementation of backtracking can be complex, especially in problems where the definition of choices, constraints and stopping criteria is complicated.
- No guarantee of convergence: Backtracking may not converge to a solution in some cases, for example when the solution doesn’t exist, or get stuck in infinite loops if the problem is poorly defined.
Optimizing backtracking
There are several techniques for optimizing the backtracking process, including :
- Heuristics: The use of intelligent rules and heuristics to guide the search to the most promising branches of the decision tree.
- Pruning: The identification and early elimination of certain branches of the tree that cannot lead to a solution, thus reducing combinatorial explosion.
- Memory: Caching of explored states to avoid recalculating the same configurations several times when they can be obtained in several different ways.
Backtracking applications in AI
Backtracking is widely used in various fields of artificial intelligence and operations research. Here are a few examples of applications:
- Logic games: Solving logic games, such as Sudoku, is a classic example of backtracking.
- Pathfinding: In pathfinding problems, such as finding optimal paths in a graph, backtracking can be used to explore different path options.
- Chess and other board games: In board games such as chess, backtracking can be used to evaluate possible sequences of actions and choose the best strategy.
Conclusion
Backtracking is a powerful technique in artificial intelligence for solving complex problems by systematically exploring different combinations of possible actions or choices. It is based on a decision tree structure and follows an iterative process of choice, validation and backtracking.
Although it has its advantages, backtracking can face problems of combinatorial explosion, and often requires optimization techniques to be effective. It is widely used in areas such as games, planning, pathfinding and puzzle solving, demonstrating its versatility in solving complex artificial intelligence problems.
If you’d like to learn more about Data Science and Artificial Intelligence, take a look at our Data Scientist training course.
