Given an n × n chessboard, place n queens so that no two attack each other. A valid placement guarantees exactly one queen per row and per column, and at most one queen on every diagonal (both positive and negative slopes). The task is to enumerate every valid configuration, print the first three in lexicographical order, and finally output the total count.

Input

13

Output

1 3 5 2 9 12 10 13 4 6 8 11 7
1 3 5 7 2 10 8 11 13 6 4 12 9
1 3 5 7 9 11 2 6 12 10 13 4 8
73712

Observations

• Each row must host exactly one queen, so we can index placements by row.
• For every column c chosen in row r, the diagonals can be identified by:
  • Positive slope: r − c is constant.
  • Negative slope: r + c is constant.
• Because r − c can be negative, we shift it by n to obtain a non-neagtive index.

Algorithm

Depth-first search with pruning:

1. Proceed row by row.
2. For each row, try every column that is not yet blocked by a queen in the same column or on either diagonal.
3. Mark the chosen column and diagonals as occupied, recurse to the next row, then backtrack.
4. Collect solutions until the search space is exhausted.

Implementation

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

const int MAXN = 15;

int n, total = 0, printed = 0;
int pos[MAXN];                // pos[row] = column
bool usedCol[MAXN];           // columns already taken
bool usedDiag[2 * MAXN];      // r + c
bool usedAnti[2 * MAXN];      // r - c + n

void dfs(int row) {
    if (row == n) {
        ++total;
        if (printed < 3) {
            for (int i = 0; i < n; ++i)
                cout << pos[i] + 1 << (i == n - 1 ? '\n' : ' ');
            ++printed;
        }
        return;
    }

    for (int col = 0; col < n; ++col) {
        if (usedCol[col]) continue;
        int d1 = row + col;
        int d2 = row - col + n;
        if (usedDiag[d1] || usedAnti[d2]) continue;

        pos[row] = col;
        usedCol[col] = usedDiag[d1] = usedAnti[d2] = true;
        dfs(row + 1);
        usedCol[col] = usedDiag[d1] = usedAnti[d2] = false;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n)) return 0;
    dfs(0);
    cout << total << '\n';
    return 0;
}

Complexity

The algorithm explores O(n!) states in the worst case, but pruning reduces the effective search space dramatically. For n = 13 the program finishes in well under a second on modern hardware.