Let's Brainstorm Backtracking 
Published: 2019-07-04 16:14:07

---
title: Let's Brainstorm Backtracking 
published: true
description:
tags:backtracking,recursion,sudokusolver,nqueens,maze
---
__Backtracking__ can be confusing at times and solving problems using backtracking can be even a tedious job. Through this post let's decode how to write backtracking algorithms.

###1. Prerequisite Knowledge###
__1. Recursion__
The most important prerequisite of backtracking is __recursion__. Though beginners usually ignore this but through this post let's change the perspective. Let's learn about recursion.

![recursion](https://media.giphy.com/media/3ov9jQX2Ow4bM5xxuM/giphy.gif)

In layman's terms, recursion is a function calling itself from itself with different parameters. Such a function that calls itself is called __recursion function__.

```python
def function(a):
    b = # perform calculations or operations on a
    function(b)
```

But we don't want it to go on forever, so we will introduce a base condition to stop recursion to go forever. This is what we call a base case. A recursion function can have multiple base cases.

```python
def function(a):
    if a == # some base value
        return #some value
    b = # perform calculations or operations on a
    function(b)
```
Let's discuss __Staircase__ problem. Here is the [link](https://leetcode.com/problems/climbing-stairs/). In this problem, we require to find the no. of ways to climb the top of the staircase and we can either climb 1 or 2 steps at a time. Let's take the top of the staircase 4 steps and solve this problem using recursion. 

![staircase](https://thepracticaldev.s3.amazonaws.com/i/z0g01h51090qji4877oi.JPG)

So we have the following ways to climb stairs:
1. __Ground__-1 step→ __A__ -1 step→ __B__ -1 step→ __C__ -1 step→ __D__
2. __Ground__-2 step→ __B__ -1 step→ __C__ -1 step→ __D__
3. __Ground__-1 step→ __A__ -2 step→ __C__ -1 step→ __D__
4. __Ground__-2 step→ __B__ -2 step→ __D__
5. __Ground__-1 step→ __A__ -1 step→ __B__ -2 step→ __D__

For this problem, we need to think of the base cases. The base cases are the cases in which we are aware of the output of the function for certain input. 

In recursion, we try to break a problem into subproblems and when we hit the base cases, we return the output to that instance of the function which called the current instance of the function. We will discuss this in the next section.

Coming back to the problem, we know that if the top of the staircases is 1, the no. of ways will always be 1 and if the top of the stack is 2, the no. of ways will always be 2. Here we get are 2 base cases and half of our job is over.

```python
# n: no. of staircase
def staircase(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    staircase()

```

The next thing is to find the new value of n with keeping in mind we need to covert this problem into sub problem. So, at a time we can either climb 1 step or 2 steps. If I climb 1 step the no. of reaming steps will be __n - 1__ and if I climb 2 step the no. of reaming steps will be __n - 2__. We can climb n - 1 and n - 2 again either taking 1 or 2 steps at a time. So if I already climbed 1 stair we will be left with n - 3 steps if I take 1 more step and n - 4 if I take 2 steps. This goes on till we n as 1 or 2.

We deduced problem into sub problems. Now the staircase function will look like this.

```python
# n: no. of staircase
def staircase(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    result = staircase(n - 1) + staircase(n - 2)
    return result

```
Each instance of the function will return the value of the result to its previous instance and when we visit the first instance the function will return the final value of result to its caller function.

__2. Call stack__


![stack](https://media.giphy.com/media/tTMhcdiREv2W4/giphy.gif)

Now, let's talk about what happens behind the scenes when recursions happen. Every program the gets executed gets converted into the process, each process looks like following in the memory
<img src="https://thepracticaldev.s3.amazonaws.com/i/o6l64fgysf677hypantb.jpg" alt="drawing" width="200"/>

We just need to focus on stack here. Every process maintains a stack in the memory that is also known as __call stack__. Every function that need to be executed or called during execution of the program is pushed in this stack and when it completes is execution, it is poped out of the call stack. for example, if we have following code.

```python
def another_function(a, b):
    return a + b

def function(a, b):
    a = b % a
    b += 1
    return another_function(a, b)

if__name__== "__main__":
    function(10, 20)
```

So, our call stack will look like this:

<img src="https://thepracticaldev.s3.amazonaws.com/i/8go5jf94wcsvxtsrcxr1.JPG" alt="drawing" width="200"/>

The main function which is called first will be in the last of the stack and the another_function which is recently called will be at the top.

Let's sneak peek into the call stack for the recursion function staircase. We know different sub-problems for the staircase problem. We have n stairs, so the stack will look like:
<img src="https://thepracticaldev.s3.amazonaws.com/i/cqinbcamdbdbpelxnn0r.JPG" alt="drawing" width="200"/>
Then we again call staircase with parameters n - 1 and the function with the parameter will subsequently call the function with parameter n - 2. When we reach the base case, the functions on the top of the stack will get executed and poped outh of the stack.
<img src="https://thepracticaldev.s3.amazonaws.com/i/5hzsnayvy7k7k1vurbx7.JPG" alt="drawing" width="200"/>
Now, each instance of recursive function in the stack can be viewed as a choice we make. `staircase(n - 2)` means we choose to take 2 steps and `staircase(n - 1) `means we choose to take 1 step. Call stack maintains all of the states or instances of function with the parameters as the choices we make before calling it. Here is an example of the call stack in between the execution of the Sudoku solver program.
![](https://thepracticaldev.s3.amazonaws.com/i/q0qzqdtpvvvh49x5kxv3.JPG)

###2. Decoding Backtracking###
__1. The Big Picture__
![](https://media.giphy.com/media/fDO2Nk0ImzvvW/giphy.gif)
In the previous section, we learned about recursion and call stack. Now let's use them to write a backtracking algorithm. We start with 3 basic rules. 
__Make the choices__
In this part, we just make a choice from the choice space without caring about it's validity. We set the choice space based on the problem we are solving. 
* For [N Queens Problem](https://leetcode.com/problems/n-queens/) where we have to place queens in n x n board such that no two queens attack each other, our choices will be every square coordinate in the chess board.
* For [Sudoku Solver](https://leetcode.com/problems/sudoku-solver/) where we have to solve a Sudoku, choices are number 1 - 9 that need to be filled in the empty cell.
* For [Maze Problem](https://leetcode.com/problems/the-maze) where we have to traverse a path to reach the goal, choices are the coordinates of the available square.

Once we make a choice, we now need to validate it. If the current instance of the recursive function runs out of the choices, then __backtracking__ will come into play. We will then backtrack to the instance of a recursive function that is at the top of the call stack which called the current one since the current one exhausted all it's choices and completed its execution. The function we backtracked then will make the next choice and try to change the fate of successive functions to be called. 

__Validate the choices__
Now, we need to validate every choice we make, if the choice is valid we recursively call the function and pass next point as the parameter for which we need to make another choice.
* For [N Queens Problem](https://leetcode.com/problems/n-queens/), a choice is valid if the queen is placed not in the same row, column or in diagonal.
* For [Sudoku Solver](https://leetcode.com/problems/sudoku-solver/), a choice is valid if the number we place in an empty cell is not found in the same row, column and 3 x 3 square.
* For [Maze Problem](https://leetcode.com/problems/the-maze) a choice is valid if the path or coordinate we choose isn't blocked.

__Setting the goals__
We need to specify the goals else the algorithm keeps on running forever. The goal tells that with current choices that fulfilled the constraints the problem is now solved. We can tell the algorithm the goal is reached by mentioning the final position of the pointers we use for iteration.
* For [N Queens Problem](https://leetcode.com/problems/n-queens/), a goal is reached when the pointer reaches the last column or n - 1 column (assuming index start from 0).
* For [Sudoku Solver](https://leetcode.com/problems/sudoku-solver/), a goal is reached when the pointer reaches the n - 1, n - 1 coordinate (assuming index start from 0).
* For [Maze Problem](https://leetcode.com/problems/the-maze), a goal is reached when the pointer reaches the n - 1, n - 1 coordinate (assuming index start from 0).

After all the 3 steps are completed, voila the backtracking algorithm is completed.
__2. Putting the pieces together__
Enough of theory let's write a Sudoku solver using backtracking.

The structure of most of the backtracking algorithm is as follows:
```python
def is_valid(n):
   # write the constraints here

def algo_util(n):
    # we set goal here

    # we make choices here

    # we validate choices by calling is_valid

    # we determine whether to recursively call algo_util with the new point as parameter.

    # we return solution to driver function

def driver_function(n):
    # calls algo_util with first basic choice.
```

Let's implement the above code structure to solve Sudoku. Starting with the driver function, we need to start Sudoku from the ​1st cell (0,0). `sudoku_util` is the `algo_util` function from above template.

````python
def driver_function(n):
     sudoku_util(0, 0)
```

We will start by setting the goals. The goal is if we reach the last cell of the sudoku (8,8).

```python
# i is iterating row and j is iterating column
def sudoku_util(i, j):
    if j > 8:
        j = 0
        i += 1

    if i == 9:
        return True
```

After setting the goal let's think of the choices, we can add 1 - 9 in each cell
```python
# check element already exist
# If entry exists the recursively calling the function with next coordinates.
if board[i][j] != '.':
    return sudoku_util(i, j + 1)

else:
    for num in ["1", "2", "3", "4", "5", "6", "7", "8", "9"]:
# Here are the choices we make from choice space.
```
Let's continue the function by validating choices.
```python
for num in ["1", "2", "3", "4", "5", "6", "7", "8", "9"]:
    if is_valid(i, j, num): # check for choice validity
        board[i][j] = num
            if sudoku_util(i, j + 1): # recursively call the function with next coordinate
                return True # inform previous function instance that the choice
            else:
                 board[i][j] = '.'

```
To put the final nail in the coffin, we need to write the is_valid function that's validates the choice we make.
```python
def is_valid(i, j, number):

            # check that row
            for col in range(n):
                if board[i][col] == number:
                    return False

            # check that column
            for row in range(m):
                if board[row][j] == number:
                    return False

            x = (i // 3) * 3
            y = (j // 3) * 3

            # check that box
            for row in range(x, x + 3):
                for column in range(y, y + 3):
                    if board[row][column] == number:
                        return False

            return True
```

And we are done. 

![](https://media.giphy.com/media/RrVzUOXldFe8M/giphy.gif)

Here is the full code:

``` python       
        board= [] # global variable

        def is_valid(i, j, number):

            # check that row
            for col in range(n):
                if board[i][col] == number:
                    return False

            # check that column
            for row in range(m):
                if board[row][j] == number:
                    return False

            x = (i // 3) * 3
            y = (j // 3) * 3

            # check that box
            for row in range(x, x + 3):
                for column in range(y, y + 3):
                    if board[row][column] == number:
                        return False

            return True

        def sudoku_util(i, j):
            if j > 8:
                j = 0
                i += 1

            if i == 9:
                return True

            # check element already exist
            if board[i][j] != '.': 
                return sudoku_util(i, j + 1)

            else:
                for num in ["1", "2", "3", "4", "5", "6", "7", "8", "9"]:
                    if is_valid(i, j, num):
                        board[i][j] = num
                        if sudoku_util(i, j + 1):
                            return True
                        else:
                            board[i][j] = '.'

        
        def driver_function(sudoku):
            # type sudoku: List[List[str]]
            board = sudoku
            sudoku_util(0, 0)
```
Here are other problems solved using backtracking.
[Maze.py](https://github.com/akarshan96/Coding-Problems/blob/master/Maze.py)
[NQueens.py](https://github.com/akarshan96/Coding-Problems/blob/master/NQueens.py)

Happy coding :)