ALDS1 13 A 8クイーン問題 順列全探索

これの解答です。
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_13_A

8クイーン問題とは、$8 \times 8$ のマスから成るチェス盤に、どのクイーンも他のクイーンを襲撃できないように、8 つのクイーンを配置する問題です。チェスでは、クイーンは次のように８方向のマスにいるコマを襲撃することができます。
すでにクイーンが配置されている k 個のマスが指定されるので、それらを合わせて8つのクイーンを配置したチェス盤を出力するプログラムを作成してください。

##方針
解においては、各行各列に唯ひとつのクイーンが存在するのだから、そのような配置候補を総当りする。あるクイーンが斜め移動で他クイーンに到達する配置は弾いていき、生き残ったものが答え。

数列 $a[i]$ を $ (1,2,...,N)$ の permutation とすると、$ (i,a[i]), i=1,...N $ がクイーンの候補配置となる。
斜めで他クイーンに到達できるか否かは、候補クイーン同士のx座標の差の絶対値がy座標の差の絶対値と等しいかをテストすればよい。

##コード

#define rep(i, a, n) for (int i = a; i < n; ++i)
#define all(x) (x).begin(), (x).end()
using namespace std;

int main() {
    // store input
    const int N = 8;
    int k;
    cin >> k;
    vector<pair<int, int>> fixed(k);
    rep(i, 0, k) { cin >> fixed[i].first >> fixed[i].second; }

    vector<int> queen(N);
    rep(i, 0, N) queen[i] = i;

    auto is_good_pos = [&]() -> bool {
        const int size = queen.size();
        rep(q, 0, size) rep(r, q + 1, size) {
            // q = (x,y), r = (w,z)
            // not ok iff abs(x-w) = abs(y-z)
            if (abs(q - r) == abs(queen[q] - queen[r])) {
                return false;
            }
        }
        return true;
    };

    auto as_given = [&]() -> bool {
        for (auto p : fixed)
            if (queen[p.first] != p.second) return false;
        return true;
    };

    // find good permutation
    do {
        if (!as_given()) continue;
        if (is_good_pos()) break;
    } while (next_permutation(all(queen)));

    // set the answer board
    vector<string> board(N, "........");
    rep(i, 0, N) board[i][queen.at(i)] = 'Q';
    // show
    rep(y, 0, N) cout << board[y] endl;
    return 0;
}