Implement N Queens Problem using Backtracking
Here you will learn to implement n queens problem using backtracking in C programming.
Define n queens problem
In the n Queens problem, N chess queens have to be placed on an NxN chessboard so they cannot attack each other. This n Queens problem can be solved by the backtracking algorithm.
The backtracking algorithm works by starting with an empty chessboard and then trying to place a queen on each row. For each row, it tries each of the N columns in turn.
- If the column is valid (It cannot be attacked by another queen.), then the queen is placed and the algorithm moves to the next row.
- If the column is invalid, the algorithm returns to the previous row and attempts the next column. This process repeated until a solution is not found.
When the solution found, the algorithm states out the positions of the n queens on the chessboard.
C program to Implement N Queens Problem using Backtracking
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include<stdio.h> #include<math.h> int chess_board[20],count; void n_Queen(int row,int n); /* print solution of n Queen problem */ void print_board(int n) { int i,j; printf("\n\n N-Queen Solution %d : \n\n",++count); for(i=1;i<=n;i++) { printf("\t%d",i); } for(i=1;i<=n;i++) { printf("\n\n%d\t",i); for(j=1;j<=n;j++) { if(chess_board[i]==j) printf("Q\t"); else printf("-\t"); } } } /* for checking conflicts*/ int check_place(int row,int col) { int i; for(i=1;i<=row-1;i++) { //checking for column and diagonal conflicts if(chess_board[i] == col) return 0; else if(abs(chess_board[i] - col) == abs(i - row)) return 0; } return 1; } /* for proper positioning of n_Queen*/ void n_Queen(int row,int n) { int col; for(col=1;col<=n;col++) { if(check_place(row,col)) { chess_board[row] = col; if(row==n) print_board(n); else n_Queen(row+1,n); } } } int main() { int n; printf("\nEnter Number of n_Queens : "); scanf("%d",&n); n_Queen(1,n);//trace using backtrack return 0; } |
Output
Read Also
Perform Travelling Salesman Problem
1/2 Knapsack Problem Using Dynamic Programming in C
Knapsack Problem Using Greedy Solution