Backtracking with Pruning: N-Queens

Stop early when it can't work

Pruning means giving up on a path as soon as you know it can't succeed.

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

vector<int> nums = {2, 3, 6, 7};      // sorted
vector<int> cur;

void combos(int start, int remaining) {
    if (remaining == 0) {
        for (size_t i = 0; i < cur.size(); i++) cout << cur[i] << (i + 1 < cur.size() ? "+" : "\n");
        return;
    }
    for (int i = start; i < (int)nums.size(); i++) {
        if (nums[i] > remaining) break;     // prune: the rest are even bigger
        cur.push_back(nums[i]);
        combos(i, remaining - nums[i]);     // i again: numbers may repeat
        cur.pop_back();
    }
}

int main() {
    combos(0, 7);
    return 0;
}

Output

2+2+3
7

N-Queens

Place N queens on an N × N board so none attack each other. One queen per row; skip attacked columns and diagonals:

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

int n = 6, solutions = 0;
vector<bool> col(6), diag1(11), diag2(11);
vector<int> board;

void place(int row) {
    if (row == n) {
        if (++solutions == 1)
            for (int c : board) cout << string(c, '.') << 'Q' << string(n - c - 1, '.') << endl;
        return;
    }
    for (int c = 0; c < n; c++) {
        if (col[c] || diag1[row - c + n - 1] || diag2[row + c]) continue;   // attacked: prune
        col[c] = diag1[row - c + n - 1] = diag2[row + c] = true;
        board.push_back(c);
        place(row + 1);
        board.pop_back();
        col[c] = diag1[row - c + n - 1] = diag2[row + c] = false;
    }
}

int main() {
    place(0);
    cout << solutions << " solutions for 6 queens" << endl;
    return 0;
}

Output

.Q....
...Q..
.....Q
Q.....
..Q...
....Q.
4 solutions for 6 queens

Tip: Squares on one “\” diagonal share row − col; on one “/” diagonal they share row + col. Adding n − 1 keeps the index from going negative.