Backtracking : Eight Queens problem

Backtracking : Eight Queens problem

Given N x N chessboard, find a way to place N queens such that none of the queen can attack other. A queen can move along the column, row and diagonal of the chess board.

This is typical example of backtracking algorithm. What we need to do is that start with the first queen at the bottom left position and check all other queens can be place satisfying the constraints of the game. If at nay point we can not go forward, we try to replace the previous queen on next safe location and try again. If we are stuck at dead end, then we might need to replace more than one queen from their position so that we can move forward.
Let’s take this example, you have a 4 x 4 chessboard and you need to place four queens on it.
We place the queen at the left most bottom corner. Once we place queen there, our available options are for placing queen 2 are shown.

Looking at the figure below we can infer that there is no way possible to place Q3 and Q4 both with current configuration. Hence we back track and select another available position for Q2

Again we can’t place Q3 and Q4, and we try all other available positions for Q2, but none of those work .(exercise). Hence we change the position of the Q1.
After changing the position of Q1, we can reach the solution as shown in figure below, with couple of more backtracks of course.

Next step to figure out that if the queens is safe at a particular position. We need to check the column, row and diagonal, to make sure no other queen is placed in those places.

8 queens (1)

8 queens (2)

8 Queen solution implementation

#include <stdio.h>
#define N 8

int isColumnSafe(int chessBoard[N][N], int col){
	
	for(int i=0; i<N; i++){
		if(chessBoard[i][col]) return 0;
	}
	return 1;
}

int isRowSafe(int chessBoard[N][N], int row){
	
	for(int i=0; i<N; i++){
		if(chessBoard[row][i]) return 0;
	}
	return 1;
}

int isDiagonalSafe(int chessBoard[N][N], int row, int col){

	int j;

	/* Check the left upper diagonal */

	for(int i=row, j = col; i>=0 && j>=0; i--, j--){
		if(chessBoard[i][j]) return 0;
	}

	/*check left lower diagonal */
	for(int i=row, j = col; i<N && j>=0; i++, j--){
		if(chessBoard[i][j]) return 0;
	}
	
	return 1;
}

int isSafe(int chessBoard[N][N], int row, int col){

	int columnSafe = isColumnSafe(chessBoard, col);
	int rowSafe = isRowSafe(chessBoard, row);
	int diagonalSafe  = isDiagonalSafe(chessBoard, row, col);

	return columnSafe && rowSafe && diagonalSafe;
}

void placeQueen(int chessBoard[N][N], int i, int j){
	chessBoard[i][j] =1;
}
void removeQueen(int chessBoard[N][N], int i, int j){
	chessBoard[i][j] =0;
}

int solveQueens(int chessBoard[N][N], int col){
	
	if(col >= N) return 1;

	for(int i=0; i<N; i++){
		if(isSafe(chessBoard, i, col)){
			placeQueen(chessBoard, i, col);
			if(solveQueens(chessBoard,col+1)) return 1;
			removeQueen(chessBoard,i,col);
		}
	}
	
	return 0;
}  

int main(void) {
	int chessBoard[8][8];
	solveQueens(chessBoard, 0);
	
	return 0;
}

Complexity of backtracking algorithm for 8 queens problem will be O(N*N).>  : http://www-isl.ece.arizona.edu/ece175/assignments275/assignment4a/Solving%208%20queen%20problem.pdf

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s