Beginner's guide to Solving the N-Queens problem using backtracking method

This post serves as a good introduction to the backtracking method which is used widely in various types of problems to find a possible solution. Here we'll be seeing how to solve the classical N-Queens problem using backtracking method.

Backtracking:

The Wikipedia page for Backtracking defines it as "a general algorithm in which, we try to incrementally build candidates to the solutions, and discard a candidate as soon as we get to know that the candidate cannot possibly be completed to a valid solution". If that sounds complicated and confusing, don't worry! Let us understand it by running through a small example.

• Consider you are trapped in a haunted house with five rooms named A, B, C, D and E.
• Initially, you are in room A and you need to reach room E to exit the house.
• Below is an image of the rooms in the house.

• The arrows in the image indicate the directions in which you can move. For example, you can move to rooms B and C from A but, you cannot move back to room A from B.
• So, now let us build solutions for the above problem using the Backtracking algorithm.
1. Initially we are at room A and that's the only candidate we have
2. From A we can get two candidates B and C
3. First, Let us select B and continue building our solution
4. From B, we can move to either D or E
5. Let us select D
6. Now after going to D, we can no longer reach E! So with candidate D we can never find a possible solution.
7. So we discard candidate D and we go back to its parent candidate B. This is exactly what we call as backtracking. When we can no longer proceed from a point, we go back and select some other option.
8. From B we select the remaining option E and thus we found a solution!
9. We can stop at this point as we have found a solution or we can find all solutions by going through each and every candidate exhaustively.
10. As there is no point in continuing our search from E, we backtrack to its parent B
11. From B as we have no other options to select, so we once again backtrack to A
12. From A, we select the only remaining option C
13. From C we go to E and thus we have found all the solutions!
14. Below is the image of the process in which we built the solutions. The arrows 3, 5 and 6 indicate the steps where we backtracked and went back to previous candidate to select other option.

• This was a simple example for understanding the backtracking algorithm. Now let us see how we can use backtracking to solve the N-Queens problem.

N-Queens problem:

Before building an algorithm, let us solve the problem pictorially, Here's  a picture of a solution to 4 queens problem using backtracking:

• First, we place queen at (1,1)
  
• Now the second queen cannot be placed in columns 1 and 2 as those positions can be attacked by the first queen.
• So we place queen two initially at (2,3)
  
• Now when we try to place a queen in the third row, No possible location is present as all locations can be attacked by either first queen or second queen.
• So we backtrack and change the second queen's positon to (2,4)
  
• Now while placing the third queen there is only one possible location which is (3,2) so we place the third queen at (3,2)
  
• Once again we end up with no possible locations for placing the next queen. So we backtrack, but there are no alternative positions even for the third and second queens. So we backtrack and change the position of the first queen as (1,2)
  
• Now for placing the second queen, we have only on choice which is (2,4)
  
• Similarly, for placing the third queen, we have only one possible location (3,1)
  
• Finally, we have one possible location for placing the fourth queen which is (4,3)
  
• Thus a possible solution to the N-Queens problem is obtained and the algorithm terminates
• We can continue our algorithm to find all possible solutions. But I'll only be explaining here how to find a single possible solution.

Now let's build an algorithm to solve N-Queens problem. In order to build an algorithm to solve N-Queens problem, we'll be using two functions:

1. isAttacked(): to check whether the newly placed queen on the board can be attacked or not. Here's algorithm for it:

	//if any cell in the 2D array is 1, it means
	// that a queen is present in that cell
	isAttacked ( x, y, board[][], N)
	//checking for row and column
	if any cell in xth row is 1
	return true
	if any cell in yth column is 1
	return true
	//checking for diagonals
	if any cell (i, j) having i+j = x+y is 1
	return true
	if any cell (i, j) having i-j = x-y is 1
	return true
	return false

view raw algorithm for isAttacked() hosted with ❤ by GitHub
2. nQueens(): To solve the nQueens problem. This function uses isAttacked() method and backtracking to find a solution. The algorithm:

	nQueens( board[][], level, N )
	//base case:
	if level = N //Queens successfully placed at all levels
	return true
	for j = 1 to N {
	if is_attacked(level, j, board, N) is true
	skip it and move to next cell
	board[level][j] = 1 //Place current queen at cell (level,j)
	//recursion and subdividing problem:
	if N-Queens( board, level+1, N) is true //Move to next level
	return true //If solution is found return true
	board[level][j] = 0 /*If solution is not found undo whatever changes
	were made i.e., remove current queen from (level,j)*/
	}
	return false

view raw algorithm for nQueens() hosted with ❤ by GitHub

Now finally, here's the implementation of the above algorithm in java:

	import java.util.*;
	class NQueens {
	//function which checks whether the queen at given position can be attacked or not
	public static boolean isAttacked (int x, int y, int board[][], int N) {
	//checking in the particular row and column
	for (int i = 0; i < N; i++) {
	//row check
	if ((board[x][i] == 1) && (i != y)) {
	return true;
	}
	//column check
	if ((board[i][y] == 1) && (i != x)) {
	return true;
	}
	}
	//diagonals check
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
	if ( ((i + j) == (x + y)) || ((i - j) == (x - y)) ) {
	if (((i != x) || (j != y)) && (board[i][j] == 1)) {
	return true;
	}
	}
	}
	}
	return false;
	}
	public static boolean nQueens (int board[][], int level, int N) {
	if (level == N) {
	return true;
	}
	for (int j = 0; j < N; j++) {
	if (isAttacked(level, j, board, N)) {
	continue;
	}
	board[level][j] = 1;
	if(nQueens(board, level+1, N)) {
	return true;
	}
	board[level][j] = 0;
	}
	return false;
	}
	public static void displayBoard (int[][] board, int N) {
	System.out.println("\n");
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
	System.out.print(" " + board[i][j] + " ");
	}
	System.out.println();
	}
	System.out.println("\n");
	}
	public static void main (String args[]) {
	Scanner s = new Scanner(System.in);
	int size = s.nextInt();
	int board[][] = new int[size][size];
	if (nQueens(board, 0, size)) {
	System.out.println("Solution found!");
	displayBoard(board, size);
	}
	else {
	System.out.println("No solution.");
	}
	}
	}

view raw NQueens.java hosted with ❤ by GitHub

Check out the solutions for 8, 15, 20 queens problem obtained using the above implementation:

Hope this post has helped you understand what is backtracking and how to use it to solve the classical N-Queens problem.

Using the method of backtracking you can develop a simple program to solve any given Sudoku puzzle! I'd recommend you check out the following article Developing Sudoku solver! You can even add it as a project on your resume :-)