c语言解决8皇后问题

Question

#include<stdio.h>
int sum=0;                     //存放方案数 
int a[8][8]={0};               //棋盘，初始化0 
int take[8][2]={0};           //存放每个满足条件皇后的位置 
int test(int x,int y){        //检测是否满足条件                 
	int i,j;
	for(i=0;i<8;i++){
		for(j=0;j<8;j++){
			if(i==x||j==y||i+j==x+y||i-j==x-y){
				if(a[i][j]) return 0;                 //遍历棋盘，找出x，y坐标对应的行，列与斜线，只要其中有一个放置了皇后，就不满足，return 0。 
			}
		}
	}
	return 1;          
}                       
void try(int n);
int main(void){
	try(1);               //从第一个皇后开始尝试放置 
	return 0;
}
void try(int n){
	int i,j;
	for(i=0;i<8;i++){                  
		for(j=0;j<8;j++){           //i,j遍历整个棋盘，找出对于第n个皇后的所有可能位置 
			if(test(i,j)){          //满足条件 
				a[i][j]=1;          //棋盘上对应的坐标标记为已放置状态 
				take[n-1][0]=i;     
				take[n-1][1]=j;     //记录 
	if(n==8){                       //8个皇后都放置完毕 
    sum++;
    printf("第%d种:",sum); 
    for(i=0;i<8;i++){
	printf("(%d,%d) ",take[i][0],take[i][1]); 
	}
	printf("\n");                  //输出 
    }
    else{
    	try(n+1);                  //递归放置下一个皇后 
	}
    a[i][j]=0;                     //回溯 
		}
		}
	}
}

 

帮忙看看哪里出错了    感觉思路很清楚  但是只能打印出一组方案   

Answer 1

那是当然只会输出一个数字了。你琢磨一下自己的递归深度有多深。一直在向下递归递归……

#include<stdio.h>
#define line 8
void queen(int i, int j);
int check(int i, int j);
int chess[line][line];
int cas = 0;
int xx, yy;

int main() {
	queen(0, 0);
	printf("%d\n", cas);
	return 0;
}

void queen(int i, int j) {
	if (j >= line) {
		return;
	}
	if (check(i, j) == 1) {//如果能放
		chess[i][j] = 1;//放皇后
		if (i == line - 1) {//如果是最后一行，记录情况
			cas++;
			//下面是输出每种棋盘结果，供测试
			/*
			for (xx=0;xx<8;xx++)
				for(yy=0;yy<8;yy++){
					printf("%d",chess[xx][yy]);
					if(yy==7)
						printf("\n");
				}
			 printf("\n");
			//上面是输出结果*/
			//另一种输出方式
			 printf("第%d种解法：",cas);
			for (xx = 0; xx < 8; xx++)
				for (yy = 0; yy < 8; yy++) {
					if(chess[xx][yy])
						printf("(%d, %d) ", xx, yy);
				}
			 printf("\n");

		}
		else {
			queen(i + 1, 0);//不是最后一行就分析下一行
		}
	}

	chess[i][j] = 0;//如果此位置不能放，就置空（0），判断旁边的格子。
	 //如果此位置能放，走到这里就意味着上面的代码全部执行了，把皇后拿走（置零），再讨论其他情况，拿旁边位置试探。
	queen(i, j + 1);
}

int check(int i, int j) {
	int k;
	for (k = 0; k < line; k++) {
		if (chess[i][k] == 1) return 0;//0=不能放
	}

	for (k = 0; k < line; k++) {
		if (chess[k][j] == 1) return 0;
	}

	for (k = -line; k <= line; k++) {//两对角线
		if (i + k >= 0 && i + k < line && j + k >= 0 && j + k < line)//从左上到右下对角线
			if (chess[i + k][j + k] == 1) return 0;
		if (i - k >= 0 && i - k < line && j + k >= 0 && j + k < line)//从左下到右上对角线
			if (chess[i - k][j + k] == 1) return 0;
	}
	return 1;
}