N-Queens Problem 👸

Some C++ code

#include <bits/stdc++.h>
using namespace std;

int n;
int cnt = 0;
int board[100][100];

void solve(vector<bool> &r, vector<bool> &c, vector<bool> &d1, vector<bool> &d2, int k) {

    if(k == n) {
        cnt++;
        // for(int i = 0; i < 2 * n - 1; i++) {
        //     cout << d1[i] << " ";
        // }
        // cout << endl;
        // for(int i = 0; i < 2 * n - 1; i++) {
        //     cout << d2[i] << " ";
        // }
        // cout<<endl;
        cout << "Solution " << cnt  << ":" << endl;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                cout << (board[i][j] ? "Q " : "- ");
            }
            cout << endl;
        }
        cout << endl;

        return;
    }

    for(int i = 0; i < n; i++) {
        if(!(r[k] || c[i] || d1[k + i] || d2[n - 1 + i - k])) {
            r[k] = c[i] = d1[k + i] = d2[n - 1 + i - k] = true;
            board[k][i] = 1;
            solve(r, c, d1, d2, k + 1);
            board[k][i] = 0;
            r[k] = c[i] = d1[k + i] = d2[n - 1 + i - k] = false;
        }
    }
}

int main() {

    cin >> n;

    vector<bool> c(n), r(n), d1(2 * n - 1), d2(2 * n - 1);

    solve(r, c, d1, d2, 0);

    cout << "Total number of solutions: " << cnt << endl;
}

/*

4

*/

/*

Solution 1:
- Q - - 
- - - Q 
Q - - - 
- - Q - 

Solution 2:
- - Q - 
Q - - - 
- - - Q 
- Q - - 

Total number of solutions: 2

*/