Implement N-Queen Problem
#include <stdio.h>
#include <stdbool.h>
#define N 8
void printSolution(int board[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf("%d ", board[i][j]);
printf("\n");
}
}
bool isSafe(int board[N][N], int row, int col) {
int i, j;
for (i = 0; i < col; i++)
if (board[row][i])
return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;
return true;
}
bool solveNQUtil(int board[N][N], int col) {
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1))
return true;
board[i][col] = 0;
}
}
return false;
}
bool solveNQ() {
int board[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
board[i][j] = 0;
if (solveNQUtil(board, 0) == false) {
printf("Solution does not exist");
return false;
}
printSolution(board);
return true;
}
int main() {
solveNQ();
return 0;
}
Explanation:
- The program uses the backtracking technique to solve the N-Queens problem, where N queens are to be placed on an NxN chessboard in such a way that no two queens threaten each other.
printSolution()
function prints the solution of the N-Queens problem.isSafe()
function checks if it's safe to place a queen at a given position on the chessboard.solveNQUtil()
is a recursive utility function that tries placing queens one by one in different columns.solveNQ()
initializes the chessboard and starts the solving process.- In
main()
, thesolveNQ()
function is called to solve the N-Queens problem for a chessboard of size 8x8 (N=8).