Introduction to Backtracking Algorithm:

Backtracking is an efficient technique for solving an algorithmic problem. In backtracking, we search depth-first for solutions, backtracking is to the last valid path as soon as we hit a dead end.

Backtracking reduces the search space since we no longer have to follow down any paths, we know are invalid. This is called pruning. We must be able to test partial solutions: for example, we can’t find a global optimum using backtracking, since we have no idea if the solution, we’re currently on can lead to it or not. But we can, for example, solve Sudoku using backtracking. We can know immediately if our solution so far is invalid by testing if two of the same number appear in the same row, column, or square.

Backtracking is finding a solution for a problem whereby the solution depends on the previous steps taken. In backtracking, we first take the step and then we see if this step taken is correct or not i.e., whether it will give a correct answer or not. In general, this is accomplished by recursion.

Thus, the general steps of backtracking are:

• start with a sub-solution.
• check if this sub-solution will lead to the solution or not.
• If not, then come back and change the sub-solution and continue again.

Now let’s see several examples of problems that can be nicely solved with backtracking to drill this concept down.

1.      N- Queens Problem:

 Objective: In chess, a queen can move as far as she pleases, horizontally, vertically, or  diagonally. A chess board has 8 rows and 8 columns. The standard 8 by 8 Queen’s problem asks how to place 8 queens on an ordinary chess board so that none of them can hit any other in one move.

Approach:

·       Create a solution matrix of the same structure as chess board.

·       Whenever place a queen in the chess board, mark that particular cell in solution matrix.

·       At the end print the solution matrix, the marked cells will show the positions of the queens in the chess board.

Algorithm:

1.      Place the queen’s column wise, start from the left most column
2. If all queens are placed.
1. return true and print the solution matrix.
3. Else
1. Try all the rows in the current column.
2. Check if queen can be placed here safely if yes mark the current cell in solution matrix as 1 and try to solve the rest of the problem recursively.
3. If placing the queen in above step leads to the solution return true.
4. If placing the queen in above step does not lead to the solution, BACKTRACK, mark the current cell in solution matrix as 0 and return false.
4. If all the rows are tried and nothing worked, return false and print NO SOLUTION.

  

2.      Knight’s Tour Problem:

Objective: A knight’s tour is the sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is one knight’s move from the beginning square, the tour is closed, otherwise it is open.

Approach:

• Create a solution matrix of the same structure as chessboard.
• Start from 0,0 and index = 0.
• Check current cell is not already used if not then mark that cell .
• Check if index = N*N-1, means Knight has covered all the cells. return true and print the solution matrix.
•  Now try to solve rest of the problem recursively by making index +1. Check all 8 directions.    
•  Check the boundary conditions as well
•   If none of the 8 recursive calls return true, BACKTRACK and undo the changes and return false.

 

3.      Search a Word in a Matrix

Objective: We have a 2D matrix of characters. Check whether the word exist in the matrix or not. If it exists then print its path. All movements are allowed i.e. right, left, up, down and diagonally.

Approach:

• Create a solution matrix of the same structure as Matrix.
• Try each cell a starting point.
• Check current cell is not already used and character in it matches with the character in the word at index will start at 0.
• Check if index = length of the word, means we have found the word. return true and print the solution matrix.
• If above criteria match, mark that cell with a number Whenever any cell matches with the criteria, put a number corresponding to it in solution matrix.
•   Now try to solve rest of the problem recursively by making index +1. Check all 8 directions i.e. up, down, left right, diagonally up-left, diagonally up-right, diagonally down-left, diagonally down-right.
•  Check the boundary conditions as well.
•  If none of the 8 recursive calls return true, BACKTRACK and undo the changes and return false.
• Choose different starting point.
• If all the starting points tried and solution not found, return false.

4.      Rat in a Maze

Objective: We have a maze i.e. N x N matrix. A rat has to find a path from source to destination. maze [0][0] (left top corner) is the source and maze[N-1] [N-1] (right bottom corner) is destination. There are few cells which are blocked, means rat cannot enter into those cells. Rat can move in any direction i.e. left, right, up and down.

Approach:

• Create a solution matrix of the same structure as a maze.
• Whenever rat moves to cell in a maze, mark that particular cell in solution matrix.
• At end print the solution matrix, follow that 1’s from the top left corner, it will be that path for the rat.

Algorithm:

1.      If rat reaches the destination

§  print the solution matrix.

§  Else

§  Mark the current cell in solution matrix as 1

§  If previous step is not in vertical direction (upwards) then move forward in the vertical direction(downwards) and recursively check if this movement leads to solution.

§  If movement in above step doesn’t lead to the solution and If previous step is not in horizontal direction (towards left) then move forward in the horizontal direction (towards right) and recursively check if this movement leads to solution.

2.      If movement in above step doesn’t lead to the solution and If previous step is not in vertical direction (downwards) then move forward in the horizontal direction (upwards) and recursively check if this movement leads to solution.

3.      If movement in above step doesn’t lead to the solution and If previous step is not in horizontal direction (towards right) then move forward in the horizontal direction (towards left) and recursively check if this movement leads to solution.

4.      If none of the above solution works then BACKTRACK and mark the current cell as 0.

5.      The Word Break Problem:

Objective: Having a string and a dictionary of words, find out if the input string can be broken into a space-separated sequence of one or more dictionary words.

Approach: 

•          Navigate the given input string.
•          Take a blank string and keep adding one character at a time to it.
•          Keep checking if the word exists in the dictionary.
•          If word exist in the dictionary then add that word to the answer string and make recursive call to the rest of the string.
•        If any of the recursive call returns false then backtrack and remove the word from the answer string and again keep adding the characters to string.
•       If all the recursive calls return true that means string has been broken successfully.

This article is contributed by Anuj Pachauri & Anant Thombare.

This is the end of the blog.
Thanks for refering, keep supporting us! :)