Design and implement C/C++ Program for N Queen's problem using Backtracking.
#include<stdio.h>
#include<stdlib.h>
#define MAX 50 // Define a constant MAX to be used for the maximum size of the board
// Function to check if a queen can be placed at a particular position
int can_place(int c[], int r) {
int i;
// Check all previous rows for conflicts
for (i = 0; i < r; i++) {
// Check if there's a queen in the same column or on the same diagonal
if (c[i] == c[r] || (abs(c[i] - c[r]) == abs(i - r))) {
return 0; // Conflict found, cannot place queen
}
}
return 1; // No conflict, queen can be placed
}
// Function to display the board
void display(int c[], int n) {
int i, j;
char cb[10][10];
// Initialize the board with '-' indicating empty spaces
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
cb[i][j] = '-';
}
}
// Place queens ('Q') on the board according to array c[]
for (i = 0; i < n; i++) {
cb[i][c[i]] = 'Q';
}
// Print the board
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
printf("%c", cb[i][j]);
}
printf("\n");
}
}
// Function to solve the N-Queens problem
void n_queens(int n) {
int r;
int c[MAX];
c[0] = -1; // Initialize the first column of the first row
r = 0;
// Backtracking algorithm
while (r >= 0) {
c[r]++; // Move to the next column
// Find a valid position for the queen in the current row
while (c[r] < n && !can_place(c, r)) {
c[r]++;
}
if (c[r] < n) {
if (r == n - 1) { // If all queens are placed
display(c, n); // Display the solution
printf("\n\n");
} else {
r++; // Move to the next row
c[r] = -1; // Initialize the column for the new row
}
} else {
r--; // Backtrack to the previous row
}
}
}
// Main function
void main()
{
int n;
printf("\nEnter the number of queens:");
scanf("%d", &n); // Input the number of queens
n_queens(n); // Solve the N-Queens problem
}
OUTPUT:
Enter the number of queens:4
- Q - -
- - - Q
Q - - -
- - Q -
- - Q -
Q - - -
- - - Q
- Q - -