• Register
248 points
ā—3
Hello reader, Welcome to my post :)

In this post, we shall discuss the backtracking algorithm. We would see how we can utilise the backtracking algorithm to solve the famous N queen problem. As we know, there are a number of ways in which the N queen problem can be approached. We can see how we can fit in the backtracking algorithm, which remains one of the popular algorithms, even today, in order to solve the puzzle.

 

What is a backtracking algorithm?

Backtracking algorithm can be related to a partial brute force algorithm for solving complex problems. Yes. It remains partial since it refines the actual brute force approach to some extent. Here in this approach, we try out all the possible solutions and finally arrive at a solution which remains closer to the expected output. The algorithm actually refines the brute force approach by excluding the impossible options and recursively checking only the options that are possible and the closest. We  don’t have any dedicated data structure for implementing this backtracking. one or more data structures are manipulated in such a way that they tend to implement the backtracking algorithm. We can understand more about this algorithm by seeing it in action while being utilised to solve the N queen problem.

 

Solving N queen problem:

First, we shall understand about the N queen problem. Suppose we have a chess board of size N*N. We have to place the queen in all of the rows of the chessboard such that none of the queens should be placed in the same rows or in the same column. Also we need to ensure that none of the queens are placed under the same diagonal. We can see how we can make use of the backtracking algorithm to arrive at the desired output.

The chess board can be assumed to be a N*N matrix where the location of the queen inside the board can be assigned a value of 1, the rest of the locations remain 0.Now the backtracking approach can be implemented by creating two methods -

1) To find appropriate location of the queen starting from the leftmost section 

2) Recursive method which utilises the first method to place the queens in the proper expected places. Let us see how the methods can be implemented.

First let us start by implementing the first method - 

  • This method should get the board matrix, row and column values as the input parameters.
  • There should be three for loops. The first for loop should check whether the queen is already placed under any of the columns, if found, then return false.
  • Inside the second for loop, the row and column values are decremented and at every position, the locations are checked to see whether the queen is already placed on it.
  • Inside the last for loop, the row values are incremented and column values are decremented and at every position, the locations are checked to see whether the value equals to 1.
boolean findLocation(int chessBoard[ ] [ ], int row, int col) {

	int i,j;
	
	//First for loop
	for(i=0; i<col; i++) {
		if(chessBoard[row][i] == 1)
			return false;

	}

	//Second for loop
	for(int i =row, j =col; j=0 && i=0; jā€”, iā€”){
		if(chessBoard[i][j] == 1)
			return false;

	}
	//Third for loop
	for(int i=0, j=col; j=0 && i = chessBoard.size(); i++, jā€”) {
		
		if(chessBoard[i][j] == 1)
			return false;

	}

	

}

Now we can implement the recursive method which leverages the findLocation method in order to find the desired locations for the queens inside the chess board. We can follow the below steps in order to create the method

  • Create a method which takes in the chessBoard and the column value as input parameters.
  • We can have the base case to return true when the column value becomes equal to the size of the board
  • We can create a for loop iteration which iterates for the length of the board. Inside the for loop, we can call the findLocation method, which would ensure whether the queen can be placed in the appropriate location
  • Also inside the same if condition, we can call the recursive function solveNQueen to check for the rest of the locations by incrementing the column value every time.
  • If the location is not found to be suitable for placing the queen, the location can be reset to 0. If the queen cannot be placed in any of the rows, then finally false would be returned by the method.
boolean solveNQueen(int chessBoard [ ] [ ] , int col) {

	//base case
	if(col >= chessBoard.size()) 
		return true;

	for(int i =0; i< chessBoard.size(); i++ {

		if(findLocation(chessBoard, i, col) {

			chessBoard[i][col] = 1;
			// recursive function
			if(solveNQueen(chessBoard, col + 1)) {
				return true;
			}
			
			chessBoard[i][col] = 0;


		}

	}

	return false;


}

Thus we have come to the end of this post. Hope you found this post informative.

Thanks for reading :)