🧠 Quay lui, cắt nhánh và CSP

vector<int> a;
int limitValue;
vector<int> chosen;

void generate(int index, int currentSum) {
    if (currentSum > limitValue) {
        return; // Pruning.
    }

    if (index == (int)a.size()) {
        // Ghi nhận cấu hình hợp lệ.
        return;
    }

    // Không chọn a[index].
    generate(index + 1, currentSum);

    // Chọn a[index].
    chosen.push_back(a[index]);

    generate(
        index + 1,
        currentSum + a[index]
    );

    chosen.pop_back();
}

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

int n;
vector<int> queenColumn;
vector<bool> usedColumn;
vector<bool> usedDiagonal1;
vector<bool> usedDiagonal2;

bool solve(int row) {
    if (row == n) {
        return true;
    }

    for (int column = 0;
         column < n;
         column++) {
        int diagonal1 = row - column + n - 1;
        int diagonal2 = row + column;

        if (usedColumn[column]
            || usedDiagonal1[diagonal1]
            || usedDiagonal2[diagonal2]) {
            continue;
        }

        queenColumn[row] = column;
        usedColumn[column] = true;
        usedDiagonal1[diagonal1] = true;
        usedDiagonal2[diagonal2] = true;

        if (solve(row + 1)) {
            return true;
        }

        usedColumn[column] = false;
        usedDiagonal1[diagonal1] = false;
        usedDiagonal2[diagonal2] = false;
    }

    return false;
}

sort(a.begin(), a.end());

for (int i = 0; i < (int)a.size(); i++) {
    if (used[i]) continue;

    if (i > 0
        && a[i] == a[i - 1]
        && !used[i - 1]) {
        continue;
    }

    used[i] = true;
    current.push_back(a[i]);

    backtrack();

    current.pop_back();
    used[i] = false;
}

bool solveSudoku() {
    int bestRow = -1;
    int bestColumn = -1;
    vector<int> bestCandidates;

    for (int row = 0; row < 9; row++) {
        for (int column = 0; column < 9; column++) {
            if (board[row][column] != 0) continue;

            vector<int> candidates
                = getCandidates(row, column);

            if (candidates.empty()) {
                return false;
            }

            if (bestRow == -1
                || candidates.size()
                   < bestCandidates.size()) {
                bestRow = row;
                bestColumn = column;
                bestCandidates = candidates;
            }
        }
    }

    if (bestRow == -1) {
        return true;
    }

    for (int value : bestCandidates) {
        board[bestRow][bestColumn] = value;

        if (solveSudoku()) {
            return true;
        }

        board[bestRow][bestColumn] = 0;
    }

    return false;
}