3. Write program to implement backtracking algorithm for solving problems like N queens || DAA

#include <stdio.h> 

#include <stdbool.h> 

#define MAX_N 10 // Adjust MAX_N for different board sizes  

void printSolution(int board[MAX_N][MAX_N], int N) { 

printf("Solution for N-Queens Problem:\n"); 

for (int i = 0; i < N; i++) { 

for (int j = 0; j < N; j++) { 

printf("%c ", board[i][j] ? 'Q' : '-'); 

} 

printf("\n"); 

} 

} 

bool isSafe(int board[MAX_N][MAX_N], int row, int col, int N)  

{ 

// Check this row on the left side for (int i = 0; i < col; i++) 

if (board[row][i]) 

return false; 

// Check upper diagonal on the left side 

for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) 

if (board[i][j]) 

return false; 

// Check lower diagonal on the left side

for (int i = row, j = col; i < N && j >= 0; i++, j--) 

if (board[i][j]) 

return false; 

return true; 

} 

bool solveNQueensUtil(int board[MAX_N][MAX_N], int col, int N) { 

if (col >= N) 

return true; 

for (int i = 0; i < N; i++) { 

if (isSafe(board, i, col, N)) { 

board[i][col] = 1; 

if (solveNQueensUtil(board, col + 1, N)) 

return true; 

board[i][col] = 0; // Backtrack if placing a queen at (i, col) doesn't lead to a solution 

} 

} 

return false; // No safe place found for this queen's column 

} 

void solveNQueens(int N) { 

int board[MAX_N][MAX_N] = {{0}}; 

if (!solveNQueensUtil(board, 0, N)) 

printf("Solution does not exist.\n"); 

else 

printSolution(board, N); 

} 

int main() { 

int N;

printf("Enter the value of N for N-Queens: "); 

scanf("%d", &N); 

solveNQueens(N); 

return 0; 

}