八皇后有关问题（回溯法）

八皇后问题（回溯法）

       记得以前c综合程序设计做过这题，记不清当时是用什么做的，总之代码没这么清晰易懂。

       思路：经过思考可以发现，恰好每行每列各放置一个皇后。设用c[x]表示第x行皇后的列编号，则问题变成了全排列生成问题。而0~7的全排列只有8！=40320个，故用枚举法的话，枚举量不会超过它。使用递归枚举法实现这个算法，也即回溯法。

法一：

#include<stdio.h>
int c[10];
void search(int cur)
{
	int i,j;
	if(cur==8) 
	{
		for(i=0;i<8;i++)
			printf("(%d,%d)",i,c[i]);
		printf("\n");
	}
	else for(i=0;i<8;i++)
	{
		int ok=1;
		c[cur]=i;
		for(j=0;j<cur;j++)
			if(c[cur]==c[j]||cur-c[cur]==j-c[j]||cur+c[cur]==j+c[j])
			{
				ok=0;
				break;
			}
			if(ok) search(cur+1);
	}
	
}
int main()
{
	search(0);
	return 0;
}

法二：（法一优化后的代码，程序的效率得到了提高）

#include<stdio.h>
int c[10];
int vis[3][30];
void search(int cur)
{
	int i;
	if(cur==8) 
	{
		for(i=0;i<8;i++)
			printf("(%d,%d)",i,c[i]);
		printf("\n");
	}
	else for(i=0;i<8;i++)
	{
		if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+8])
		{
			c[cur]=i;
			vis[0][i]=vis[1][cur+i]=vis[2][cur-i+8]=1;
			search(cur+1);
			vis[0][i]=vis[1][cur+i]=vis[2][cur-i+8]=0;
		}
	}
	
}
int main()
{
	search(0);
	return 0;
}