9663 N-Queen

質問リンク

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

に答える

NxNチェス盤にN個の皇后を重ねないためには、行ごとに1個の皇后しか置かない.そうでなければ、横軸に女王同士の攻撃が必ずあるからだ.重要)つまり,チェス盤全体を検査するために2つのドアを回す必要はなく,1行あたり数列目に皇后を置くだけで保存できる.1 D配列ボードを使用して、皇后の列の情報を格納します.ゼロインデックスから始めればいいです.PUTQでは、繰り返しの扉を回り、n行目のi列にQueen(列が重ならず、対角線で会わない(列間の車、行間の車の絶対値が同じなら会える)を置けるかどうかをチェックし、置けるならnを1増やしてPUTQに入れて次の行に戻る.nがnに等しい場合、n個の皇后はすべて解放されるので、ans 1が増加し、関数が終了する.最後にansを出力すればいいです.

C++コード

#include <stdio.h>
#include <math.h>

using namespace std;

int N;
int board[15];
int ans = 0;

void putQ(int n){
	if(n == N){
		ans++;
		return;
	}
    for(int i=0; i<N; i++){
    	board[n] = i;
    	bool check = true;
    	for(int i=0; i<n; i++){
			if(board[i] == board[n] || n-i == abs(board[n] - board[i])){
				check = false;
				break;
			}
		}
    	if(check){
    		putQ(n+1);
		}
	}
}

int main(){
    scanf("%d", &N);
    putQ(0);
    printf("%d\n", ans);
    
    return 0;
}