## [ Bài toán N quân hậu ](https://marisaoj.com/problem/53)
#### Lời giải
Xét tại hàng $i$, ta có thể đặt quân hậu tại cột $j$ nếu như không có quân hậu nào được đặt trước đó nằm trên cột j hoặc nằm trên đường chéo chính hoặc nằm trên đường chéo phụ
- Hai quân hậu nằm trên đường chéo chính có tọa độ lần lượt là $(i_1, j_1)$ và $(i_2, j_2)$ sẽ có hiệu tọa độ $i_1 - j_1 = i_2 - j_2$ không đổi
- Hai quân hậu nằm trên đường chéo phụ có tọa độ lần lượt là $(i_1, j_1)$ và $(i_2, j_2)$ sẽ có tổng tọa độ $i_1 + j_1 = i_2 + j_2$ không đổi
- Do vậy để kiểm tra các quân hậu có cùng nằm trên đường chéo chính hoặc đường chéo phụ không ta kiểm tra hiệu tọa độ hoặc tổng tọa độ của chúng

Để dễ dàng kiểm soát ô $(i, j)$ thỏa mãn hay không ta có thể duy trì 3 mảng như sau:
- $col(j)$ nhận giá trị $true$ nếu đã có quân hậu nằm trên cột $j$
- $main\_diagonal(k)$ nhận giá trị $true$ nếu đã có quân hậu nằm trên đường chéo chính có hiệu tọa độ $i$ và $j$ là $k$ (các vị trí nằm trên đường chéo chính đều có hiệu tọa độ không đổi)
- $anti\_diagonal(k)$ nhận giá trị $true$ nếu đã có quân hậu nằm trên đường chéo phụ có tổng tọa độ $i$ và $j$ là $k$ (các vị trí nằm trên đường chéo phụ đều có tổng tọa độ không đổi)

Nếu đã xếp được quân hậu đến hàng $n$ ta nhận thêm một cách đặt $n$ quân hậu thỏa mãn
#### Cài đặt
:::spoiler Chi tiết

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

const int N = 27;
int n, res = 0;
bool col[N], main_diagonal[N], anti_diagonal[N];

void backtracking(int i){
    if(i > n){
        res++;
        return;
    }
    for(int j = 1; j <= n; j++){
        if(!col[j] && !main_diagonal[i + n - j] && !anti_diagonal[i + j]){
            col[j] = main_diagonal[i + n - j] = anti_diagonal[i + j] = true;
            backtracking(i + 1);
            col[j] = main_diagonal[i + n - j] = anti_diagonal[i + j] = false;
        }
    }
}

void solve(){
    cin >> n;
    backtracking(1);
    cout << res;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
}

:::