N-Queen Algorithm

The N-Queens problem is a classic puzzle that involves placing N queens on an NxN chessboard such that no two queens can attack each other. The goal is to find all possible configurations of placing the queens on the board.The N-Queens problem can be solved using backtracking, which is a general algorithmic technique for finding all or some solutions to a computational problem by incrementally building candidates for solutions and rejecting those that cannot be completed to valid solutions.Here’s a step-by-step description of the N-Queens algorithm using backtracking:1. Define a chessboard of size NxN, where each cell represents a position on the board. Initialize the board with all cells set to 0 or empty.2. Start with the first row (row 0) and iterate through each column (col) in that row.3. Check if it is safe to place a queen at the current position (row, col) by calling the `isSafe()` function. This function checks if there is no queen in the same column, upper-left diagonal, and upper-right diagonal of the current position. If it is safe, proceed to the next step.4. Place a queen at the current position (row, col) on the board by setting `board[row][col] = 1`.5. Recursively move on to the next row (row + 1) and repeat steps 2-5 until all N rows are processed.6. If all N queens have been successfully placed (row == N), it means we have found a valid solution. Print or store the solution.7. Backtrack by removing the queen from the current position (row, col) by setting `board[row][col] = 0`.8. Move to the next column (col + 1) in the current row and repeat steps 3-8.9. Continue this process, backtracking when necessary, until all possible configurations have been explored.10. Once all possible solutions have been found, the algorithm terminates.The N-Queens algorithm uses the concept of backtracking to explore all possible configurations by incrementally placing queens on the board and checking for safety. If a queen cannot be placed in a particular position, the algorithm backtracks and explores other possibilities.By following this approach, the algorithm will find and print all valid solutions to the N-Queens problem.Note: The provided code implements the N-Queens algorithm using backtracking and prints all possible solutions for a given board size (N).

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

void printSolution(int** board, int N) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%c ", board[i][j] ? 'Q' : '-');
        }
        printf("\n");
    }
    printf("\n");
}

bool isSafe(int** board, int N, int row, int col) {
    // Check if there is a queen in the same column
    for (int i = 0; i < row; i++) {
        if (board[i][col]) {
            return false;
        }
    }

    // Check if there is a queen in the upper-left diagonal
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j]) {
            return false;
        }
    }

    // Check if there is a queen in the upper-right diagonal
    for (int i = row, j = col; i >= 0 && j < N; i--, j++) {
        if (board[i][j]) {
            return false;
        }
    }

    return true;
}

void solveNQueens(int** board, int N, int row) {
    if (row == N) {
        // All queens have been placed, print the solution
        printSolution(board, N);
        return;
    }

    // Try placing a queen in each column of the current row
    for (int col = 0; col < N; col++) {
        if (isSafe(board, N, row, col)) {
            // Place the queen in the current position
            board[row][col] = 1;

            // Recursively solve for the next row
            solveNQueens(board, N, row + 1);

            // Backtrack and remove the queen from the current position
            board[row][col] = 0;
        }
    }
}

int main() {
    int N;
    printf("Enter the board size (N): ");
    scanf("%d", &N);

    // Dynamically allocate memory for the board
    int** board = (int**)malloc(N * sizeof(int*));
    for (int i = 0; i < N; i++) {
        board[i] = (int*)malloc(N * sizeof(int));
        for (int j = 0; j < N; j++) {
            board[i][j] = 0;
        }
    }

    solveNQueens(board, N, 0);

    // Free the dynamically allocated memory
    for (int i = 0; i < N; i++) {
        free(board[i]);
    }
    free(board);

    return 0;
}

Output :

Enter the board size (N): 4

- Q - -
- - - Q
Q - - -
- - Q -
 
- - Q -
Q - - -
- - - Q
- Q - -

2 thoughts on “N-Queen Algorithm

Leave a Reply

Your email address will not be published. Required fields are marked *