**BackTracking:**

Find a solution by trying one of several choices. If the choice proves incorrect, computation backtracks or restarts at the point of choice and tries another choice. It is often convenient to maintain choice points.

In an exhaustive search algorithm you search every possible choice to reach to the goal state, however, the backtracking algorithm is an extension, where you realize a bad choice by using some constraint and do not explore that choice any further. Hence, this is optimized by reducing the number of choices that you would explore in case of exhaustive search.

__Example:__

The example can help you understand the backtracking algorithm. Almost all the problems have similar structure where you have to explore various options available and the choices are in the form of tree above.

Starting at Root, your options are A and B. You choose A.

At A, your options are C and D. You choose C.

C is a bad choice and it is decided by some constraint in the real world problems. Go back to A.

At A, you have already tried option C, and it failed. Try option D.

D is bad. Go back to A.

At A, you have no options left to try. Go back to Root.

At Root, you have already tried A. Try B.

At B, your options are E and F. Try E.

E is good which is your goal. Congratulations, you have solved the backtracking problem !

Backtracking Solution Structure:

ALGORITHM Backtrack(X[1..i]) //Gives a template of a generic backtracking algorithm //Input: X[1..i] specifies first i promising components of a solution //Output: All the tuples representing the problem’s solutions if X[1..i] is a solution write X[1..i] else // for each element x ∈ Si+1 consistent with X[1..i] and the constraints do X[i + 1]←x Backtrack(X[1..i + 1])

**N Queens Problem:**

The problem is to place n queens on an nxn chessboard so that no two

queens attack each other by being in the same row or in the same column or on

the same diagonal.

**Solution:**

We start with the empty board and then place queen 1 in the first possible

position of its row, which is in column 1 of row 1. Then we place queen 2, after

trying unsuccessfully columns 1 and 2, in the first acceptable position for it, which

is square (2, 3), the square in row 2 and column 3. This proves to be a dead end

because there is no acceptable position for queen 3. So, the algorithm backtracks

and puts queen 2 in the next possible position at (2, 4). Then queen 3 is placed

at (3, 2), which proves to be another dead end. The algorithm then backtracks all

the way to queen 1 and moves it to (1, 2). Queen 2 then goes to (2, 4), queen 3 to

(3, 1), and queen 4 to (4, 3), which is a solution to the problem.

public class NQueens { List<String[]> res = new ArrayList<String[]>(); /****number of possible solutions****/ int count=0; public List<String[]> solveNQueens(int n) { int A[] = new int[n]; for(int i=0; i<n; i++){ A[i]=-1; } solve(A,0,n); return res; } public void printBoard(int[] A, int n){ String str[] = new String[n]; for(int i=0; i<n; i++){ String temp=""; for(int j=0; j<n; j++){ if(A[i]==j){ temp +="Q"; }else{ temp +="."; } } str[i]=temp; } res.add(str); } public boolean isValid(int[] A, int col){ for(int i=0; i<col; i++){ if(A[i]==A[col] || Math.abs(A[i]-A[col])== (col-i)){ return false; } } return true; } public void solve(int[] A, int col, int n){ if(col==n){ printBoard(A,n); count++; }else{ for(int i=0; i<n; i++){ A[col] =i; if(isValid(A,col)){ System.out.print(col+" "); solve(A,col+1,n); } } } } }