八皇后

r囧r小猫 2022-08-24 14:25 171阅读 0赞

/***************************
    # 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; 
    }