Solving the N Queen Problem with C - GangForCode (2024)

Solving the N-Queen Problem with C. The N-Queen Problem is a classic algorithmic challenge that involves placing N queens on an N*N chessboard so that no two queens can threaten each other. This means two queens can be in the same row, column, or diagonal. This article provides a step-by-step guide to solving the n queen problem with C language, focusing on a backtracking approach, which is a form of recursive algorithm.

Understanding the N Queen Problem

Before jumping into coding, it is crucial to thoroughly understand what the n queen problem is and what it entails. the goal is to find all the problem arrangments of n queen on an n*n chessboard where no two queens attack each other.

Solving N Queen Problem with C

Defining the Chessboard

The chessboard can be represented as a 2D array of integers, where 0 indicates a space and 1 represents a queen.

int board[n][n];

Initializing the Chessboard

Before starting ensure that the chessboard is empty. this can be done with the simple nested loop

void initalizeBoard(int board[n][n]){ for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { board[i][j] = 0; } }}

Check if the Queen can be Placed

We need a function to check if a queen can be placed on the board at the [row][col] position without being attacked by another queen.

int isSafe(int board[n][n], int row, int column){ int i, j; // Check this row on left side for (i = 0; i < column; i++) { if (board[row][i]) { return 0; } } // Check upper diagonal on upper side for (i = row, j = column; i >= 0 && j >= 0; i--, j--) { if (board[i][j]) { return 0; } } // Check lower diagonal on left side for (i = row, j = column; j >= 0 && i < n; i++, j--) { if (board[i][j]) { return 0; } } return 1;}

Solve the N Queen Problem

Use backtracking to solve the problem recursively. the function tries to place a queen on every row. if placing a queen in a certain column leads to the solution, it proceeds to place another queen in the next row. If it does not lead to a solution, it backtracks and tries a different column.

 int solvenqueen(int board[n][n], int column){ // Base case: If all queens are placed if (column >= n) { return 1; } // Consider this column and try placing this queen in all rows one by one for (int i = 0; i < n; i++) { // Chcek if queen can be placed on board[i][column] if (isSafe(board, i, column)) { // Place this queen on board[i][column] board[i][column] = 1; // Recur to place rest of the queens if (solvenqueen(board, column + 1)) { return 1; } // If placing queens in board[i][column] does not need to a solution, board[i][column] = 0; } } // if the queen can't be placed in any row in this column then return false return 0;}

Implement the Main Function

This function initializes the board and calls the utility function to solve the problem.

void main(){ printf("Enter the value of n "); scanf("%d", &n); int board[n][n]; initalizeBoard(board); if (!solvenqueen(board, 0)) { printf("Solution does not exist"); } else { printSolution(board); }}

Print the Solution

Implement a function to print the chessboard with a Queen place.

void printSolution(int board[n][n]){ printf("\n\n"); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { printf(" %d ", board[i][j]); } printf("\n"); } printf("\n\n");}

Compelet C Program for N Queen Problem

#include <stdio.h>#include <stdlib.h>int n;void printSolution(int board[n][n]){ printf("\n\n"); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { printf(" %d ", board[i][j]); } printf("\n"); } printf("\n\n");}int isSafe(int board[n][n], int row, int column){ int i, j; // Check this row on left side for (i = 0; i < column; i++) { if (board[row][i]) { return 0; } } // Check upper diagonal on upper side for (i = row, j = column; i >= 0 && j >= 0; i--, j--) { if (board[i][j]) { return 0; } } // Check lower diagonal on left side for (i = row, j = column; j >= 0 && i < n; i++, j--) { if (board[i][j]) { return 0; } } return 1;}int solvenqueen(int board[n][n], int column){ // Base case: If all queens are placed if (column >= n) { return 1; } // Consider this column and try placing this queen in all rows one by one for (int i = 0; i < n; i++) { // Chcek if queen can be placed on board[i][column] if (isSafe(board, i, column)) { // Place this queen on board[i][column] board[i][column] = 1; // Recur to place rest of the queens if (solvenqueen(board, column + 1)) { return 1; } // If placing queens in board[i][column] does not need to a solution, board[i][column] = 0; } } // if the queen can't be placed in any row in this column then return false return 0;}void initalizeBoard(int board[n][n]){ for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { board[i][j] = 0; } }}void main(){ printf("Enter the value of n "); scanf("%d", &n); int board[n][n]; initalizeBoard(board); if (!solvenqueen(board, 0)) { printf("Solution does not exist"); } else { printSolution(board); }}

Output of N Queen Solution

n = 8

n=12

N Queen Problem Time Complexity

The backtracking approach for solving the n queen problem, as demonstrated in this article by using C language, does not have a straightforward time complexity due to its recursive nature and the fact that it explores multiple branches of execution, backtracking when a potential solution does not lead to success. The worst-case time complexity for the n queen problem using backtracking can be roughly estimated as O(n!) where n is the number of queens(or the size of the chessboard). This factorail time complexity arises because, in the worst case, the algorithm might need to try all possible arrangements of n queens on the board.

Happy Coding & Learning

See Also

• C Program for Structure of Students Details
• Circular Queue Implementation in C

Related