nqueen print all solutions Algorithm

The n-queen print all solutions algorithm is a classic combinatorial problem that seeks to identify all possible solutions for placing n queens on an n x n chessboard in such a way that no two queens threaten each other. In other words, the algorithm aims to find all possible arrangements where no two queens share the same row, column, or diagonal. This problem is an extension of the 8-queens problem, which specifically deals with placing 8 queens on an 8x8 chessboard. The n-queen problem is often solved using backtracking, a strategy that incrementally builds candidates to the solutions and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot be extended to a valid solution. The algorithm typically starts by placing the first queen in the top-left corner of the chessboard and proceeds column by column, placing the next queen in a safe position where it is not threatened by any other queen. If a safe position cannot be found within the current column, the algorithm backtracks to the previous column and moves the queen to a new safe position. This process continues until all queens are placed on the board, at which point a solution has been found. The algorithm then backtracks, searching for additional solutions by exploring different queen placements in previous columns. The process is repeated until all possible solutions have been identified. The n-queen print all solutions algorithm not only provides a solution to the problem but also helps to enhance one's understanding of combinatorial problems and algorithm design, particularly in the areas of recursion and backtracking.
#include <iostream>
#define n 4

void PrintSol(int Board[n][n]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            std::cout << Board[i][j] << " ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

bool CanIMove(int Board[n][n], int row, int col) {
    /// check in the row
    for (int i = 0; i < col; i++) {
        if (Board[row][i] == 1)
            return false;
    }
    /// check the first diagonal
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (Board[i][j] == 1)
            return false;
    }
    /// check the second diagonal
    for (int i = row, j = col; i <= n - 1 && j >= 0; i++, j--) {
        if (Board[i][j] == 1)
            return false;
    }
    return true;
}

void NQueenSol(int Board[n][n], int col) {
    if (col >= n) {
        PrintSol(Board);
        return;
    }
    for (int i = 0; i < n; i++) {
        if (CanIMove(Board, i, col)) {
            Board[i][col] = 1;
            NQueenSol(Board, col + 1);
            Board[i][col] = 0;
        }
    }
}

int main() {
    int Board[n][n] = {0};
    NQueenSol(Board, 0);
}

LANGUAGE:

DARK MODE: