C Program For N Queens Problem Algorithm
Let us learn how to solve N Queens Problem Algorithm in C programming language. The Queens Algorithm can be solved either by Backtracking Algorithm or by Brute Force method. This C program focuses on solving N Queen’s Algorithm using Backtracking Algorithm.
What is Queens Problem?
The N Queens Problem is a puzzle of placing N Queens on a N * N Chessboard in such a way that no two queens can attack each other i.e., no two queens should be placed horizontally, vertically or diagonally. In other words, any queen should not be in the same row, column or diagonal of any other queen.
In other words, any queen should not be in the same row, column or diagonal of any other queen.
N represents the number of queens. So, when N = 1, it’s a trivial case. For N = 2 and N = 3, the solution is not possible.Therefore, we start with
Therefore, we start with N = 4. Normally, 4 Queen’s Problem and 8 Queen’s Problem are famous questions for its applicability.
Must Read: C Program To Solve Banker’s Algorithm
C Program To Solve N Queens Problem using Backtracking Algorithm
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 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | #include<stdio.h> #include<stdlib.h> #include<math.h> int chess_board[20], count; int display(int); void queen_function(int, int); int placeholder(int, int); void queen_function(int row_value, int limit) { int column_value; for(column_value = 1; column_value <= limit; column_value++) { if(placeholder(row_value, column_value)) { chess_board[row_value] = column_value; if(row_value == limit) { display(limit); } else { queen_function(row_value + 1, limit); } } } } int placeholder(int row_value, int column_value) { int count; for(count = 1; count <= row_value - 1; count++) { if(chess_board[count] == column_value) { return 0; } else { if(abs(chess_board[count] - column_value) == abs(count - row_value)) { return 0; } } } return 1; } int display(int limit) { int m, n; printf("\n\n\tPossible Solution %d:\n\n", ++count); for(m = 1; m <= limit; m++) { printf("\t[%d]", m); } for(m = 1; m <= limit; m++) { printf("\n\n[%d]", m); for(n = 1; n <= limit; n++) { if(chess_board[m] == n) { printf("\tQ"); } else { printf("\t*"); } } } } void main() { int limit; printf("\nEnter Number of Queens:\t"); scanf("%d", &limit); if(limit <= 3) { printf("\nNumber should be greater than 3 to form a Matrix\n"); } else { queen_function(1, limit); } printf("\n\n"); } |
Must Read: C Program For Producer-Consumer Problem
Output
If you have any compilation errors or doubts in this C program for N Queens Algorithm using Backtracking, let us know about in the comment section below.
I am getting an error in this C Program. First, it worked fine but on compiling it the second time, it showed some error with the abs() function. Please help.
You may be getting this error due to the inclusion of math.h header file. This is common. You can use this compilation command to overcome the error:
gcc filename.c -lm
I hope the above solution helps you to run this C Program successfully.
This N Queens Problem Explanation is just too good. Thanks for this Queens C Program.
Will this code work for 4 Queens problem using Backtracking algorithm in C programming?
Yes. It will definitely work.
It is interesting that the queens problem algorithm does not work when N = 2 and N = 3. Therefore, we need to start with N = 4.
Thanks. Finally I solved 8 queens problem in c programming.
When we have a 1X1 chess board, it is a trivial case when N = 1. Since, I am a beginner I find the code a bit difficult to grasp but it’s okay as long as the output is perfect.
for what this loop is used for(count = 1; count <= row_value – 1; count++)