Solution to N-Queens problem

N-queens problem is the generalization of classic 8-queens puzzle (or problem). In N-queens problem, ‘N’ number of queens are to be placed onto a NxN square board (or chessboard), such that no two queens are attacking each other.The solution presented here uses the backtracking approach to solve the N-queens problem.

The solution contains a recursive function, backtrack( ) which i have used to implement the backtracking approach. In the below program, i have specified the size of the board as eight so the solution is specialized to 8-queens problem. To find the solution for some other value of ‘N’, edit line no.3  to required N value.

#include <stdio.h>

#define BSIZE 8

void initBoard();
int placeQueen(const int , const int );
int checkCross(const int , const int );
void backtrack(int);
void printBoard();

//Chessboard array
char board[BSIZE][BSIZE];
//Row,column iteration variables
int row,col;
//Count for total number of solutions
int count;
int stop;

int main()
{
	int i,j;
	//Initializing count
	count =1;
	stop = 0;
	//Intializing Chessboard
	initBoard();
	//Finding first solution by placing queens in order of column 1,2,...BSIZE.
	for(i=0;i<BSIZE;++i)
	{	
		if(placeQueen(0,i) == -1)
		{
			//If not positioned then backtracking
			backtrack(i);
			if(stop)
			{
				count = 0;
				break;
			}
		}
	}
	//If there is no solution found
	if(!stop)
	{
		printf("%d)",1);
		//Printing the solution obtained
		printBoard();
		//Obtainig remaining solutions
		while(1)
		{
			backtrack(BSIZE);
			if(stop)
			{
				break;
			}
			printf("%d)",++count);
			printBoard();
		}
	}
	printf("\nTotal number of solutions for %d-Queens problem: %d\n",BSIZE,count);
	return 0;
}

//Initializes Chessboard array with blanks specified with 'X' character
void initBoard()
{
	//Row iteration
	for(row = 0;row < BSIZE;++row)
	{
		//Column iteration
		for(col = 0;col < BSIZE;++col)
		{
			board[row][col] = 'X';
		}
	}
}

//This functions trys to place queen in column 'colnum' and after row 'rownum'
//It returns row number on success, and '-1' on failure
int placeQueen(const int rownum, const int colnum)
{
	int flag;
	int temp = 0;
	for(row = rownum;row < BSIZE;++row)
	{
		flag = 0;
		for(col = 0;col < colnum;++col)
		{
			//check column
			if(board[row][col] == 'Q')
			{
				flag = -1;
				break;
			}
		}
		if(flag != -1)
		{
			//Checking diagonal squares
			if(checkCross(row,colnum) != -1)
			{
				//Placing queen
				board[row][colnum] = 'Q';
				return row;
			}
		}
	}
	//backtrack
	return -1;
}

//This function checks for queens diagonal to specified row 'rownum' and column 'colnum' values
//It return 0 if no queens are there in its diagonal squares, otherwise it returns -1
int checkCross(const int rownum,const int colnum)
{
	int rowtmp = rownum;
	int coltmp = colnum;
	//Checking upper diagonal squares
	while(--rowtmp >= 0 && --coltmp >= 0)
	{
		if(board[rowtmp][coltmp] == 'Q')
		{
			return -1;			
		}
	}
	rowtmp = rownum;
	coltmp = colnum;
	//Checking lower diagonal squares
	while(++rowtmp < BSIZE && --coltmp >= 0)
	{	
		if(board[rowtmp][coltmp] == 'Q')
		{
			return -1;			
		}
	}
	return 0;
}

//Uses recursive backtracking to place the queens
void backtrack(int coltmp)
{
	int rowtmp;
	//Exhaustive condition check
	if(coltmp <= 0)
	{
		stop = 1;
		return;
	}
	coltmp-=1;
	//Finding the position of already placed queen
	for(rowtmp = 0;rowtmp < BSIZE;++rowtmp)
	{
		if(board[rowtmp][coltmp] == 'Q')
		{
			board[rowtmp][coltmp] = 'X';
			break;
		}
	}
	//Repositioning the queen in the column 'coltmp' after row 'rowtmp+1'
	if(placeQueen(rowtmp+1,coltmp) == -1)
	{
		//If not positioned then backtracking
		backtrack(coltmp);
	}
	//Checking boundary conditions
	if(coltmp+1 < BSIZE && coltmp+1 >=0)
	{
		//Backtracking until the queen is placed in column 'coltmp+1'
		while(placeQueen(0,coltmp+1) == -1)
		{
			backtrack(coltmp+1);
		}
	}
}

//Prints the Chessboard onto console 
void printBoard()
{
	printf("\n\n");
	//Row iteration
	for(row = 0;row < BSIZE;++row)
	{
		//Column iteration
		for(col = 0;col < BSIZE;++col)
		{
			printf("%3c",board[row][col]);
		}
		printf("\n\n");
	}
}

If there are any bugs or modifications to be done, just leave your comments below.

Advertisement