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.

## 3 comments

Comments feed for this article

January 27, 2011 at 12:26 am

кран козловойuseful information. It’s really good

February 4, 2011 at 6:34 pm

ucancodethank you for appreciating my work.

February 11, 2011 at 9:16 am

RhaniteVery useful indeed – thank you very much for providing it. It was a great help in understanding how to solve the program