N-Queens and Backtracking

1. Algorithm & Complexity

The N-Queens problem asks: “Place N queens on an N×N chessboard so that no two threaten one another.” We solve it with a backtracking (depth-first search) approach:

1. Maintain three boolean arrays of size 2*N or N each to mark columns, “main” diagonals, and “anti” diagonals under attack.
2. Recursively try to place a queen row by row:
• For row r, loop c = 0…N-1. If column c and both diagonals are free,
• — mark them occupied, record queen[r] = c, and recurse to r+1.
• — on return, undo the marks (backtrack) and try next c.
3. When r == N, you’ve placed all N queens—record or count this solution.

Time Complexity

In the worst case you explore roughly O(N!) placements: row 0 has N choices, row 1 ≤ N−1, …, so N×(N−1)×…≈N!.

Memory Complexity

You store:

• queen[0…N−1] → O(N)
• column and diagonal marker arrays → O(N) or O(2N)
• recursive call stack up to depth N → O(N)

2. 2 Easy Backtracking Examples

2.1 – Generating All Subsets (Codeforces-style “Power Set”)

Given a small array of distinct integers, output all 2ⁿ subsets.

Input:
3
1 2 3

Output:
[]
[1]
[2]
[3]
[1,2]
[1,3]
[2,3]
[1,2,3]

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> a;
vector<int> curr;

void dfs(int idx) {
    if (idx == n) {
        // print current subset
        cout << "[";
        for (int i = 0; i < curr.size(); ++i) {
            if (i) cout << ",";
            cout << curr[i];
        }
        cout << "]\n";
        return;
    }
    // 1) exclude a[idx]
    dfs(idx + 1);
    // 2) include a[idx]
    curr.push_back(a[idx]);
    dfs(idx + 1);
    curr.pop_back();
}

int main() {
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    dfs(0);
    return 0;
}

2.2 – Generating All Permutations (“Next Permutation” style)

Given 1…N, print every ordering (N! total).

Input:
3

Output:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> perm;
vector<bool> used;

void dfs() {
    if (perm.size() == n) {
        for (int x : perm) cout << x << ' ';
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (used[i]) continue;
        used[i] = true;
        perm.push_back(i);
        dfs();
        perm.pop_back();
        used[i] = false;
    }
}

int main() {
    cin >> n;
    perm.reserve(n);
    used.assign(n+1,false);
    dfs();
    return 0;
}

3. 2 Intermediate Backtracking Examples

3.1 – Sudoku Solver (9×9)

Fill a partially completed 9×9 grid so each row, column, and 3×3 box has digits 1–9 exactly once.

Input:  (0 = empty)
5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9

Output:
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

#include <iostream>
#include <vector>
using namespace std;

int grid[9][9];
bool rowUsed[9][10], colUsed[9][10], boxUsed[9][10];

int boxId(int r,int c){ return (r/3)*3 + (c/3); }

bool dfs(int r,int c){
    if (r == 9) return true;
    int nr = (c==8 ? r+1 : r);
    int nc = (c==8 ? 0   : c+1);
    if (grid[r][c] != 0) return dfs(nr,nc);
    for (int d = 1; d <= 9; ++d) {
        int b = boxId(r,c);
        if (rowUsed[r][d] || colUsed[c][d] || boxUsed[b][d]) continue;
        rowUsed[r][d]=colUsed[c][d]=boxUsed[b][d]=true;
        grid[r][c]=d;
        if (dfs(nr,nc)) return true;
        rowUsed[r][d]=colUsed[c][d]=boxUsed[b][d]=false;
    }
    grid[r][c]=0;
    return false;
}

int main(){
    for(int i=0;i<9;i++) for(int j=0;j<9;j++){
        cin>>grid[i][j];
        if(grid[i][j]){
            int d=grid[i][j], b=boxId(i,j);
            rowUsed[i][d]=colUsed[j][d]=boxUsed[b][d]=true;
        }
    }
    dfs(0,0);
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            cout<

Input:
4 2

Output:
6

#include <iostream>
#include <vector>
using namespace std;

int M, K, ans=0;
vector<vector<bool>> used;
int dr[8]={-2,-2,-1,-1,1,1,2,2}, dc[8]={-1,1,-2,2,-2,2,-1,1};

bool safe(int r,int c){
    for(int d=0;d<8;d++){
        int nr=r+dr[d], nc=c+dc[d];
        if(nr>=0&&nr<M&&nc>=0&&nc<M&&used[nr][nc]) return false;
    }
    return true;
}

void dfs(int idx,int placed){
    if (placed==K){ ans++; return; }
    if (idx>=M*M) return;
    int r=idx/M, c=idx%M;
    // skip
    dfs(idx+1, placed);
    // place if safe
    if (safe(r,c)) {
        used[r][c]=true;
        dfs(idx+1, placed+1);
        used[r][c]=false;
    }
}

int main(){
    cin>>M>>K;
    used.assign(M, vector<bool>(M,false));
    dfs(0,0);
    cout<<ans<<'\n';
    return 0;
}

Input:
8

Output:
92   (there are 92 solutions for N=8)

#include <iostream>
#include <vector>>
using namespace std;

int N, total=0;
vector<bool> col, diag1, diag2;

void dfs(int r){
    if (r==N){ total++; return; }
    for(int c=0;c<N;c++){
        if(col[c]||diag1[r-c+N]||diag2[r+c]) continue;
        col[c]=diag1[r-c+N]=diag2[r+c]=true;
        dfs(r+1);
        col[c]=diag1[r-c+N]=diag2[r+c]=false;
    }
}

int main(){
    cin>>N;
    col.assign(N,false);
    diag1.assign(2*N,false);
    diag2.assign(2*N,false);
    dfs(0);
    cout<<total<<'\n';
    return 0;
}