1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Function to check if it is safe to place a queen at the given position
6bool isSafe(vector<vector<int>>& board, int row, int col) {
7  // Check if there is a queen in the same column
8  for (int i = 0; i < row; i++) {
9    if (board[i][col] == 1) {
10      return false;
11    }
12  }
13
14  // Check if there is a queen in the upper left diagonal
15  for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
16    if (board[i][j] == 1) {
17      return false;
18    }
19  }
20
21  // Check if there is a queen in the upper right diagonal
22  for (int i = row, j = col; i >= 0 && j < board.size(); i--, j++) {
23    if (board[i][j] == 1) {
24      return false;
25    }
26  }
27
28  return true;
29}
30
31// Function to solve the N-Queens problem using backtracking
32bool solveNQueens(vector<vector<int>>& board, int row) {
33  int n = board.size();
34
35  // All queens are placed, the board is a valid solution
36  if (row == n) {
37    return true;
38  }
39
40  for (int col = 0; col < n; col++) {
41    if (isSafe(board, row, col)) {
42      // Place the queen
43      board[row][col] = 1;
44
45      // Recurse for the next row
46      if (solveNQueens(board, row + 1)) {
47        return true;
48      }
49
50      // Backtrack by removing the queen
51      board[row][col] = 0;
52    }
53  }
54
55  // No valid solution
56  return false;
57}
58
59int main() {
60  int n;
61  cout << "Enter the size of the chessboard: ";
62  cin >> n;
63
64  vector<vector<int>> board(n, vector<int>(n, 0));
65
66  if (solveNQueens(board, 0)) {
67    cout << "A solution exists.\n";
68    cout << "The board representation is:\n";
69    for (int i = 0; i < n; i++) {
70      for (int j = 0; j < n; j++) {
71        cout << board[i][j] << " ";
72      }
73      cout << "\n";
74    }
75  } else {
76    cout << "No solution exists.";
77  }
78
79  return 0;
80}