🎡 N-Queen

( https://www.acmicpc.net/problem/9663 )

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
10 초	128 MB	55113	27793	18185	49.896%

質問する
N-Queen問題の大きさはN× これは,N個のチェス盤上のN個の皇后が互いに攻撃し合うことができない問題である.
Nが与えられた場合,解放後の方法の数を計算するプログラムを作成してください.
入力
1行目はNです.(1 ≤ N < 15)
しゅつりょく
1行目でN個の皇后が互いに攻撃できない場合は、数字を出力します.
入力例1
8
サンプル出力1
92

🙄に答える

Queenはチェス盤のn行目に置くことができ、N-Queenを満たすことができます!

Queen 1行目のi(1-n)2列目から2、3、4……n行目に入るか否かを判断する.

重要なのは、アクセスできるかどうかをどのように決定するかです.

単純に言えば、皇后が(x,y)にいる場合、皇后が攻撃範囲内にあるかどうかをチェックし続けることができますが、これは時間がかかり、実施が面倒です.(リリースごとにチェックが必要です)

クイーンを(row,col)の上に置くと、確認する必要があります.

A:Queenと同じ列に新しいQueenを配置することはできません.
-> bool isused_col[]

B:皇后を含む右対角線に新しい皇后を置くことはできません.
-> bool isused_Increasing_Diagonal[]

C:皇后を含む左下の対角線に新しい皇后を置くことはできません.
-> bool isused_Decreasing_Diagonal[]
(変数名は好きじゃないけど…)

Queenは(0,0)~(0,n)に入れ、A,B,Cを見て、新しいQueenが(1,0)~(1,n)に入れられることを確認することができる.

このプロセスでは、最終的にn行にQueen,count+

を配置できます.
しかし、A B Cインデックスはどうすればいいのでしょうか.
皇后が(x,y)にあると仮定する.

A:皇后と同じ列に新しい皇后はいられない.
-> bool isused_col[]
条件などの場合はisused col[y]を確認すればOKです.

B:皇后を含むアイドルの対角線に新しい皇后を置くことはできません.
-> bool isused_Increasing_Diagonal[]

上の図に示すように、0行0列を通る右対角線のindexを0と呼び、この対角線を基準として、下段の対角線indexを1,2,3とします.そう言えばいいです.
この場合、Queenが(x,y)にある場合、isused increating Diagonal[x+y]はすべてtrueとなる.

C:皇后を含む左下の対角線に新しい皇后を置くことはできません.
-> bool isused_Decreasing_Diagonal[]
この場合も同じですが、ちょっと面倒かもしれません.

0行15列を通る対角線のindexを0、下段の対角線のindexを1.2.3…に表示されます.
この場合、Queenが(x,y)にある場合、true処理が必要なインデックスはx-y+n-1となる.
(なぜ-1はindexを0から始めるためなのか)
isused_Decreasing_Diagonal[x-y+n-1]

コード#コード#

/*
BOJ : https://www.acmicpc.net/problem/9663
backtracking N-Queen
Versatile0010
*/

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

int n;
int cnt = 0;

bool isused_col[30];
bool isused_Increasing_diagonal[30];
bool isused_Decreasing_diagonal[30];

void func(int cur) // cur 번째 행에 퀸을 배치함
{
	if (cur == n)
	{
		cnt++;
		return;
	}

	for (int i = 0; i < n; i++) // cur 행 i 열을 순회
	{
		if (isused_col[i] || isused_Increasing_diagonal[cur+i] || isused_Decreasing_diagonal[cur-i+n-1])
			continue; // 퀸을 놓을 수 없는 경우
		else // 퀸을 놓을 수 있는 경우
		{
			isused_col[i] = true; // 해당 칸 세로에 true
			isused_Increasing_diagonal[cur + i] = true; //해당 칸 우상향 대각선에 true
			isused_Decreasing_diagonal[cur - i + n - 1] = true; //해당 칸 좌하향 대각선에 true 처리
			func(cur + 1);
			isused_col[i] = false; 
			isused_Increasing_diagonal[cur + i] = false;
			isused_Decreasing_diagonal[cur - i + n - 1] = false;
		}
	}


}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	func(0);
	cout << cnt;
	return 0;
}

GIT : https://github.com/versatile0010/PS/blob/main/Backtracking/BOJ%209663.cpp