N-Queens Problem Solution using Backtracking in C++

// Using a one-dimensional array to represent the chessboard, where the index of the array represents the row number and the value represents the column number. This way, the position of each queen can be represented by a single array. #include #include

using namespace std;

int totalSolutions = 0;

// Backtracking algorithm, recursively try each column in each row, and find the queen positions that satisfy the conditions. When placing a queen in each row, we need to check if there is any conflict with the previous queens, i.e., if they are in the same column or on the same diagonal. bool isSafe(vector<vector>& board, int row, int col, int N) { // Check if safe in the top left direction for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) { if (board[i][j] == 1) return false; }

// Check if safe in the top right direction
for (int i = row, j = col; i >= 0 && j < N; i--, j++) {
    if (board[i][j] == 1)
        return false;
}

// Check if safe in the current column
for (int i = 0; i < row; i++) {
    if (board[i][col] == 1)
        return false;
}

return true;

}

void solveNQueensUtil(vector<vector>& board, int row, int N) { // All the queens have been placed if (row == N) { totalSolutions++; return; }

for (int col = 0; col < N; col++) {
    if (isSafe(board, row, col, N)) {
        board[row][col] = 1;  // Place the queen

        solveNQueensUtil(board, row + 1, N);

        board[row][col] = 0;  // Backtrack, remove the queen
    }
}

}

int solveNQueens(int N) { totalSolutions = 0; vector<vector> board(N, vector(N, 0)); solveNQueensUtil(board, 0, N); return totalSolutions; }

int main() { int N = 12; // Set the value of N, change 8 to 4 to run 4-Queens problem int solutions = solveNQueens(N); cout << "The number of solutions for the 12-Queens problem is: " << solutions << endl; return 0; }

// Explanation: To determine whether it satisfies the 8-Queens problem, the following two conditions need to be met: // Let d[n] = m represent the queen in the n-th row is placed at column m, denoted as C // Let row be the row number that is being tried, and col be the column number.

// 1. d[n] != col, for (i < row) ------ The column numbers are different, ensuring that queens on different rows are not in the same column.

// 2. n - d[n] != row - col ------ No queens on the anti-diagonal path where C lies. // and n + d[n] != row + col ------ No queens on the main diagonal path where C lies.

// Backtracking is used to reduce the number of iterations. The number of attempts is < 8 ** 8.

// For the N-Queens problem, when N is less than or equal to 3, there are no possible solutions because any two queens will attack each other. // When N is greater than or equal to 4, there exist solutions, but the specific existence of a solution depends on the value of N and the specific placement rules. // For example, there are two different solutions for N=4, while there are 10 solutions for N=5.