[boj] (g5) N-Queen

質問リンク
クイーン:わあ、対角線で移動できる馬

チェス馬が移動できる木の構造は以下の通りです.

問題条件の下で、皇后は私たちにお互いに攻撃することができないので、(2,1)(2,2)は位置決めできない位置です.
dfsを使用してチェスの位置を完全にナビゲートし、可能な位置を見つけることができます.
効率が低いため,可能な位置のみ探索,すなわち木を剪定して効率を向上させる.
1行あたり

に1つのQueenが構成され、総構成列数がN(N個のQueenがすべて構成されている)であれば、1行あたり1つのQueenが追加されるようにバックグラウンド追跡が行われる.
したがって、再帰関数のパラメータには、何番目の列が埋め込まれているかを記録するパラメータが必要になります.

皇后を構成する際にチェックする必要があるのは、「任意の構成の皇后は他の皇后と同じ行ですか、それとも同じ列ですか?」または「対角線に位置しています」

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int chess[15][15];
int N, cnt = 0;

bool isPossible(int row, int col) // 다른 퀸과 같은 행, 대각선에 있는지 판별
{
    // 열
    int x = row - 1, y = col;
    while (x >= 0)
    {
        if (chess[x][y] == 1)
            return false;
        x--;
    }

    // 위-왼쪽 대각선
    x = row - 1;
    y = col - 1;
    while (x >= 0 && y >= 0)
    {
        if (chess[x][y] == 1)
            return false;
        x--;
        y--;
    }

    // 위-오른쪽 대각선
    x = row - 1;
    y = col + 1;
    while (x >= 0 && y < N)
    {
        if (chess[x][y] == 1)
            return false;
        x--;
        y++;
    }

    return true;
}

void dfs(int row)
{
    if (row == N)
    {          // N개를 모두 채스판 위에 놓았으므로
        cnt++; // 경우의 수를 하나 증가시키고 함수 종료
    }
    else
    {
        for (int col = 0; col < N; col++)
        {
            if (isPossible(row, col) && chess[row][col] == 0)
            {
                chess[row][col] = 1; // 퀸 배치
                dfs(row + 1);        // 가능하면 다음 열로 이동
                chess[row][col] = 0; // 초기화
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    dfs(0);

    cout << cnt;

    return 0;
}