1128. N Queens Puzzle (20)

解题思路：重点掌握n皇后的判断，注意这道题是按列给出的数据，所以只用判断是否在同行或者同一对角线，同行的话就是纵坐标相等，对角线的话就是斜率为正负1，但是直接除的话会出现向下取整，所以把分母上的数乘到右边，比较两者是相等还是，呈相反数。

#include<cstdio>
#define N 1005
int pos[N];
int main(){
	int k,n;
	scanf("%d",&k);
	while(k--){
		scanf("%d",&n);
		for(int i = 0; i < n; i++){
			scanf("%d",&pos[i]);
		}
		bool tag = true; 
		for(int i=1;i<n && tag;i++){
			for(int j=0;j<i;j++){
				if(pos[i] == pos[j] ||pos[i] - pos[j] == i-j||pos[i] - pos[j] == j-i){
				tag = false;
				break; 
			    }
		    }
	   }
	   printf("%s\n",tag?"YES":"NO");
   }
	return 0;
}

N皇后

参考中国MOOC网郭炜老师的课程。
N皇后问题是经典的递归问题。
给出一个N阶的皇后，输出所有可能摆放的位置。
例如：
4
3 4 1 2
3 1 4 2
关于判断对角线是否冲突的问题，对角线满足斜率为正负1，不管坐标原点在何处， $y / x = \pm 1$
这里把x拿到右边 $y = \pm x$ ，但是无法保证y一定为正，所以两边同时加绝对值，abs(y) =abs(x)
而此处的 y = queePos[j] - i，之前的纵坐标与当前纵坐标之差
此处的 x = i - k，之前横坐标与当前横坐标之差

#include<iostream>
#include<cmath>
using namespace std;
int N;
int queenPos[100];
void NQueen(int k);
int main(){
	cin>>N;
	NQueen(0);
	return 0;
}

void NQueen(int k){  //在0~k-1行皇后已经摆好的情况下，摆第k行及其后的皇后 
	int i;
	if(k == N){ //如果N个皇后已经摆好，直接输出 
		for(i=0;i <N;i++)
			cout<<queenPos[i]+1<<" ";
		cout<<endl;
		return; 
	}
	for(i=0;i<N;i++){ //逐个尝试第k个皇后的位置 
		int j;
		for(j=0;j<k;j++){
			if(queenPos[j]==i || abs(queenPos[j]-i) == abs(j-k)) //斜率为正负1 
				break;
		}
		if(j==k){
			queenPos[k]=i;
			NQueen(k+1);
		}
	}	
}