main.cpp

我做的一些C语言练习题,里面一共有76道题目,主要用到一些计算机常用的算法,如:递归,分治,动态规划,回溯法,AO算法等,除此之外还用到比较多的数学知识,我做了一部分,还有一些暂时还没做出来,大家也帮

/*******************************************************************************
20. (Ｎ皇后) 在国际象棋的棋盘上放置Ｎ个皇后，使其不能互相攻击，即任意
 两个皇后不能处在棋盘的同一行，同一列，同一斜线上，试问共有多少种摆法？

  利用回溯法求解N皇后问题
********************************************************************************/
#include <stdio.h>
#include <math.h>
#include <malloc.h>

static int counter = 0;

//检查是否是合法解
int check(int k,int* v)
{
	int i;
	for(i=0;i<k;i++)
	{
		if(v[i]==v[k])
			return 0;
		if(abs(k-i)==abs(v[k]-v[i]))
			return 0;
	}
	return 1;
}

//输出一个解
void output(int *v, int n)
{
	int i,j;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(j+1==v[i])
			{
				printf("%2c",'O');
			}
			else
			{
				printf("%2c",'#');
			}
		}
		printf("\n");
	}
	printf("\n");
}

//回溯算法
int N_Queen(int* v,int n)
{
	int i;
	int flag=0;
	int k=0;

	for(i=0;i<n;i++)
		v[i]=0;
	
	while(k>=0)
	{
		while(v[k]<n)
		{
			v[k]++;
			if(check(k,v))
			{
				if(k<n-1)
				{
					k++;
				}
				else if(k==n-1)
				{
					flag=1;
                    output(v,n);
					counter ++;
					v[k]=0;
					k=k-1;
				}
			}
		}
		v[k]=0;
		k=k-1;
	}
	return flag;
}

//main
void main()
{
	int n;
	int *v;
	printf("请输入N皇后问题参数N: ");
	scanf("%d",&n);
	if(n<2)
	{
		printf("参数N不符合!\n");
		return;
	}
	v=(int*)malloc(n*sizeof(int));
	if(!N_Queen(v,n))
	{
		printf("no solve!\n");
	}
	printf("一共有%d种摆法!\n",counter);
	free(v);
}