n皇后问题

n皇后问题

1.题意

不再叙述。

2. 源码

如下：

#include<cstdio>
#include<cstring>
#define maxn 1000
 
double array[maxn];//全局变量  保存皇后的位置 
int n;//n*n 
int count = 0;

//是否是符合条件的点  currentRow当前行 
bool isRight(int currentRow){
	int i ; 
	for(i = 1;i< currentRow;i++){
		if( array[i] == -1) break;//不符合条件的数 
		if(array[currentRow] == array[i]){
			break;//列相同 
		}
		if( ( (array[currentRow]- array[i])/(currentRow - i) == -1 ) ){
			break;//在斜对脚线上
		}
		if( ((array[currentRow]- array[i])/(currentRow - i) == 1 ) ){
			break;//在斜对脚线上
			
		}
	}
	if(i == currentRow)	return true;
	else
	 return false;
}

void dfs(int currentRow){
	if(currentRow == n+1){//如果已经到了最后一行的下一行 
		for(int j = 1;j <= n;j++){
			printf("%.0lf ",array[j]);//输出 
		} 
		printf("\n");
		count++;
		return ;//返回 
	} 
	for(int i = 1;i<= n;i++){
		array[currentRow] = i;
		if(isRight(currentRow)){//如果符合条件--->则继续 
			dfs(currentRow+1);//往下一行搜索	
		}
	}
} 
  
int main(){	
	scanf("%d",&n);
	dfs(1); 
	//printf("count = %d\n",count);
}
/**
4/3 == 1 
*/

3.更新日志

== update on 20200203== ============

对于深搜的代码应该注意如下几点：

• 尽量先判断是否符合条件，再深搜。（而不是深搜之后再判断条件。否则有的样例是过不了的，比如络谷里的p1219 8皇后问题）
• 如果可以剪枝，则应尽量剪枝