Nov 15, 2020


Backtracing is an algorithmic-technique for solving problems incrementally by building the solution incrementally. The system is implemented by removing solutions that don't satisfy the constraints at any point. This means that rather than checking everything you can check everything up to a point and move one if it doesn't work or stops if everything is satisfied.

There are two main parts of this algorithmic-technique checking if a value is valid to be put into the solution and running the solver to add each input one value at a time and being able to reverse course if needed.

Their implementations are easiest seen in use so we will talk about how to solve a sudoku board:

Check Valid Function:

This function checks the rows, columns, and the section to see if the number can be put into that spot. This is the most important step of using backtracking because it is the underpinning of if the solution will work. You need to know the constraints that you are working with if you want to use backtracking.

Solve Utility Function

This is the recursive portion of the code. Once called you to continue to call this function within itself until there are no more inputs to try or solve the sudoku. It is recursive because if you hit a spot that doesn't work it will reverse the inputs till it finds what it needs.

What backtracking allows us to do is speed up code. Instead of trying to check everything, it allows us to take diverging paths and just check until we know that the current path will fail.