回溯法 n皇后

n皇后问题（C）
【习题描述】
【题目描述】
n皇后（n>=4）问题是一个以国际象棋为背景的问题：如何能够在 n×n 的国际象棋棋盘上放置n个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
【输入说明】
输入只有一个数，表示n
【输出说明】
输出所有可能的情况，若存在多个解，每种情况独立一行，并且棋子按棋盘从左到右的顺序输出多个解。棋盘的下标从1开始。每对坐标的括号之间有一个半角空格。
【输入样例】
4
【输出样例】
(1,2) (2,4) (3,1) (4,3)
(1,3) (2,1) (3,4) (4,2)

#include 
# define N 100
int main(){


    int n=4;
    scanf("%d",&n);
	int queen[N] = {0};		//用来储存皇后的位置 即queen的值就为第i行的列
							//queen[0]表示第0行
							//queen[i]表示第i行
	int cnt = 0;			//表示摆放了几个皇后，也表示摆放皇后的行数。
	int col = 0;			//表示在这一列上摆放了皇后
	int sum = 0;			//总共有几种摆法
	while(1){
		//在(cnt,col)这个坐标摆放皇后

		if(cnt == 1 && queen[0] == n-1 && col == n-2){		//表示第一行的皇后已经到了第N列且第二行的皇后到了第N-2列位置，已经摆放不下皇后了就退出循环
			break;	
		}
		int isAttack = 0;		//用来表示皇后们之间是否能够攻击的到，如果攻击的到就是1，否则就为0
		int i=0;
		for(i=0;i<cnt;i++){
			if(queen[i] == col){	//表示在同一列上
				isAttack = 1;	
			}	
			int div_row = cnt -i;		//表示斜线上的纵坐标之差
			int div_col = queen[i]-col;		//表示斜线上横坐标之差
			if(div_row == div_col ||div_row == -div_col){ 	//表示在同一斜线上
				isAttack = 1;	
			}
		}
		if(isAttack == 0){	//表示可以放置
			queen[cnt] = col;		//记录皇后当前的列数
			cnt++;					//开始摆放下一个皇后
			col = 0;				//下一个皇后从第一列开始遍历
			if(cnt == n){			//如果摆满了八个皇后就打印出他们的摆法
				for(i=0;i<n;i++){
					printf("(%d,%d) ",i+1,queen[i]+1);	
				}	
				printf("\n");	
				sum++;				//并且摆放种数+1
				do{		//越界问题	//回朔
					cnt--;		//撤回正在摆放的皇后
					col = queen[cnt]+1;		//往下一个列寻找摆放位置
				}while(col>=n);			
			}
		}else{			//表示不能摆放
			col++;
			while(col>=n){			//回朔
				cnt--;				//退一格
				col = queen[cnt]+1;	//上一个皇后往后移一格
			}
		}
	}

	return 0;	
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58