八皇后

/***************************
# Queen 八皇后问题 ：递归实现 

1. 从第一行开始递归
2. 然后枚举当前行中的每一列，
3. 如果可以放置皇后，则递归放置下一行
4. 当放置到第8行时，说明8个皇后全部安全放置，输出
 
# time：2014-2-9 11:03:20 
# Time: MS   Memory: K
# Author: zyh
***************************/ 

#include<stdio.h>

int n,cnt; // n: 棋盘的行列数；  cnt: 可以放置的 种数 

/*
	int row : 当前行
	int col : 当前列 
	int (*chess)[8] : 当前棋盘数组 
*/
bool place(int row,int col, int (*chess)[8]){
	
	// 判断同一列是否已经有皇后 
	for(int i = 0; i < row; i++)
		if(chess[i][col]) return 0;
	
	// 判断同一斜线对角线是否已经有皇后
	for(int i = row-1,j = 1; i >= 0; i--,j++)
		if( (col-j>=0 && chess[i][col-j]) || (col+j<8 && chess[i][col+j])) return 0;
	
	return 1;
}

/*
	int r : 当前行
	int (*chess)[8] ：棋盘数组 
*/
void eightQueen(int r,int (*chess)[8] )
{		
	// 放置到第8行时输出	
	if(r == 8){
		printf("\n第%d种：\n",cnt++);
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++)
				printf("%d ",chess[i][j]);
			putchar('\n');
		}
		return;
	}
	
	//枚举当前行的每一列 
	for(int i = 0; i < n; i++){
		//如果可以放，继续递归下一行 
		if( place(r,i,chess)) {
			chess[r][i] = 1;
			eightQueen(r+1,chess);
			chess[r][i] = 0; 
		}
	}
} 
int main()
{
	int chess[8][8]={0};
	n = 8; cnt = 1;
	eightQueen(0,chess);
	return 0; 
}

/***************************
# Queen 八皇后问题 ：回溯
 
用一维数组来表示八个皇后的位置 X[8]; 
X[i] 代表第i个皇后所在的列（第i个皇后在第i行，不用考虑在同一行的约束） 
1. 第i个皇后 与 第 j 个皇后 同一列： x[i] == x[j];
2. 第i个皇后 与 第 j 个皇后 同一斜线： x[i]+i == x[j]+j || x[i]-i == x[j]-j ;  
	即 abs(i-j) == abs(x[i]-x[j]) 
# time：2014-02-09 13:25:03 
# Author: zyh
***************************/ 
#include<stdlib.h> 
#include<stdio.h>

int n,cnt; // n: 棋盘的行列数；  cnt: 可以放置的 种数 
int x[10];

//cur: 开始放置第cur个皇后 
void dfs(int cur){
	
	//得到一种解法，cnt++ 
	if(cur==8){
		cnt ++;
		return;
	}
	
	//枚举每一列 
	for(int i=0; i<n; i++){
		x[cur] = i; 
		int ok = 1;
		//与前面放置的 cur-1个皇后比较，看是否可以放置 
		for(int j=0; j<cur; j++){
			if(x[cur]==x[j] || abs(cur-j) == abs(x[cur]-x[j])) {ok = 0;break;}
		} 
		if(ok) dfs(cur+1);
	}
} 
int main()
{
	n = 8;
	cnt = 0;
	dfs(0); 
	printf("共有 %d 种解法.\n",cnt); //92种 
	return 0; 
}