Backtracking

In some problems as we search for a solution, we may reach a dead end and have to go back and try something else.

Sounds easy enough right! In theory, it is, but when it comes to implementing it in code it can get quite tricky. Backtracking is most often associated with recursion but as that is a little more complex to wrap ones head around, let’s start by examining a non recursive solution.

HOW DO WE FIND A PATH THROUGH A MAZE and how do we define a maze in code?

Thinking of the numbers above as points in the maze. We can create a list of points to which each point connects to .

Our function will maintain a “path” i.e. list of numbers of the points from the start to the current position. E.g.

We will also keep track of a set of points already visited

keeping track of the visited points is necessary because otherwise, the search could end up in an endless loop. At each step we look at the last point in the path list and see if there is a connection to an unvisited point.If there is we will add that number to the path list and the visited set and move on