• Table of Contents

Introduction

Backtracking algorithm is a problem-solving algorithm that uses a brute-force approach for finding the desired output. The term backtracking suggests that if the current solution is not suitable, then backtrack and try other solutions. Thus, recursion is used in this approach.

Figure 4.1 State space tree.

It can be represented as a tree structure.

• The search tree is traversed from root down in depth-first order.
• At each node, we check if the node leads us to the path giving us a complete valid solution. If not, then the whole subtree rooted at that node is skipped.

We will cover some of the most common backtracking problems.

N Queens Problem

In a chess game, a queen can move along 3 axes — horizontal, vertical and diagonal.

Figure 4.1 The queen’s movement set

In this problem, we have an $N \times N$ chess board. Place $N$ queens on this board in such a way that no two queens can kill each other.

Consider one of the following solutions to the $8$ queens problem.

Figure 4.2 One solution to $8$ queens problem.

The output is usually represented as a matrix or list of $N$ positions, where each position indicating the row and column number of a queen. For example, the output of Figure 4.2 can be represented as:

{0, 0, 0, 1, 0, 0, 0, 0}
{0, 0, 0, 0, 0, 0, 1, 0}
{0, 0, 1, 0, 0, 0, 0, 0}
{0, 0, 0, 0, 0, 0, 0, 1}
{0, 1, 0, 0, 0, 0, 0, 0}
{0, 0, 0, 0, 1, 0, 0, 0}
{1, 0, 0, 0, 0, 0, 0, 0}
{0, 0, 0, 0, 0, 1, 0, 0}

The value 1 represents the presence of a queen in that row and column, while 0 represents an empty cell. Now let’s look at how the algorithm work.

1) Start in the leftmost column
2) If all queens are placed
		return true
3) Try all rows in the current column. Do following for every tried row.
		a) If the queen can be placed safely in this row then mark 
			 this [row, column] as part of the solution and recursively 
			 check if placing queen here leads to a solution.
    b) If placing the queen in [row, column] leads to a solution 
			 then return true.
    c) If placing queen doesn't lead to a solution then unmark 
			 this [row, column] (Backtrack) and go to step (a) to try 
			 other rows.
4) If all rows have been tried and nothing worked,
   return false to trigger backtracking.

Refer to the animation below as an example: