Backtracking

 Introduction:

Is this the first time you are learning about backtracking? If your answer is Yes then you are wrong. As a kid we have solved many maze puzzles. For solving all those mazes the idea which we used is Backtracking.

For example consider below image, the person need to come out of maze so he chooses a path and goes in that direction. If he sees a dead-end then he comes back one step and moves in another direction. He continues to do it until he comes out of the maze. This is nothing but Backtracking.
Here the person chooses a path, if its a dead-end, he eliminates it, backtrack and check for other paths and it continues until he gets out of it.

What does the name Backtracking mean?

Backtracking is an algorithmic technique to solve computational problems. It searches in all possible ways then removes dead-end or step that does not lead to a solution and backtracks and continues to explore other branches. Backtracking is  like a refined brute force algorithm that chooses the best of all possible solutions.

Types of Backtracking :

Decision Problems –To find feasible solution of a problem. Eg: Sodoku solver

Optimization Problems – To find the best solution Eg: minimum path sum

Enumeration Problems – To find set of all possible solutions.
Eg: phone number combination. , n queens

Application:

Backtracking can be used to solve many real life problems, one of such application is Sudoku solver.

In childhood we have solved many sudoku puzzles, using backtracking algorithm it can be done in no time.

Problem Statement:

Write a program to solve a Sudoku puzzle by filling the empty cells(empty cells are denoted with "0".

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur only once in each row.
2. Each of the digits 1-9 must occur only once in each column.
3. Each of the digits 1-9 must occur only once in each of the 9 3x3 sub-grids.

Input:

output:

        

Algorithm:

• Write a recursive function i.e solveSoduko that accepts the sudoku as parameter.
• Create a function to check whether the sudoku is completely filled or not. If atleast one character in sudoku is "0" return false else return true.
• Write getUnFilledRowCol function to get the next box to be filled.
• Write isSafe function which checks whether a particular value between 1 to 9 can be placed at the particular location returned by getUnFilledRowCol. If it return true fill it with the value and recursively call solveSoduko function. If any recursive call returns false then un-assign the value.

Code:

 To get the source code click here

Conclusion:

I hope you enjoyed it and learned something new today. More than 50% interview questions involve recursion, so backtracking is definitely a handy tool which will be helpful during your interviews. To learn more about backtracking solve questions on leetcode backtracking. While solving don't forget the phrase First solve the problem then write the code.