八皇后问题_7-28 八皇后问题(*)

八皇后问题

八皇后问题(英文:Eight queens)，是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。

问题表述为:在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。

八皇后问题就有有一个8*8的棋盘，每一行都可以放置一个皇后，但是放置的皇后不可以在同一列，这一行和前一行以及后一行的皇后不能出现在同一条对角线上，我们就可以使用穷举法来实现这个问题的编程解决。

穷举法是一种针对于密码的破译方法。这种方法很像数学上的"完全归纳法"并在密码破译方面得到了广泛的应用。简单来说就是将密码进行逐个推算直到找出真正的密码为止。比如一个四位并且全部由数字组成其密码共有10000种组合，也就是说最多我们会尝试9999次才能找到真正的密码。利用这种方法我们可以运用计算机来进行逐个推算，也就是说用我们破解任何一个密码也都只是一个时间问题。

当然如果破译一个有8位而且有可能拥有大小写字母、数字、以及符号的密码用普通的家用电脑可能会用掉几个月甚至更多的时间去计算，其组合方法可能有几千万亿种组合。这样长的时间显然是不能接受的。其解决办法就是运用字典，所谓"字典"就是给密码锁定某个范围，比如英文单词以及生日的数字组合等，所有的英文单词不过10万个左右这样可以大大缩小密码范围，很大程度上缩短了破译时间。

通俗来讲就是一个问题的所有解决方案全部列举出来，然后剔除其中不符合要求的方案，剩下的就是符合要求的，放到八皇后问题中，根据要求剔除即可

#include <stdio.h>
#include <assert.h>
 
 
int  solution = 0;//多少种解法
void  DrawingQueue(int* arr, int len)
{
	printf("第%d种解法如下:\n", ++solution);
	printf("***********************************\n");
	int count1 = 0;//每行皇后前面的空格
	int count2 = 0;//后面的空格
	for (int i = 0; i < 8; i++)
	{
		count1 = arr[i];
		while (count1 != 0)
		{
			printf("X   ");//X表示空格
			count1--;
		}
		printf("M   ");//M表示皇后
		count2 = 8 - 1 - arr[i];
		while (count2 != 0)
		{
			printf("X   ");
			count2--;
		}
		printf("\n");
	}
	printf("***********************************\n");
}
 
int GetQueen()
{
	int count = 0;
	int arr[8];
	int x = 0;//arr的下标
	for (int i = 0; i < 8; i++)
	{
		for (int j = 0; j < 8; j++)
		{
			if (j == i || j - i == 1 || j - i == -1)
			{
				continue;
			}
			for (int k = 0; k < 8; k++)
			{
				if (k == j || k - j == 1 || k - j == -1 ||
					k == i || k - i == 2 || k - i == -2)
				{
					continue;
				}
				for (int s = 0; s < 8; s++)
				{
					if (s == k || s - k == 1 || s - k == -1 ||
						s == j || s - j == 2 || s - j == -2 ||
						s == i || s - i == 3 || s - i == -3)
					{
						continue;
					}
					for (int m = 0; m < 8; m++)
					{
						if (m == s || m - s == 1 || m - s == -1 ||
							m == k || m - k == 2 || m - k == -2 ||
							m == j || m - j == 3 || m - j == -3 ||
							m == i || m - i == 4 || m - i == -4)
						{
							continue;
						}
						for (int n = 0; n < 8; n++)
						{
							if (n == m || n - m == 1 || n - m == -1 ||
								n == s || n - s == 2 || n - s == -2 ||
								n == k || n - k == 3 || n - k == -3 ||
								n == j || n - j == 4 || n - j == -4 ||
								n == i || n - i == 5 || n - i == -5)
							{
								continue;
							}
							for (int p = 0; p < 8; p++)
							{
								if (p == n || p - n == 1 || p - n == -1 ||
									p == m || p - m == 2 || p - m == -2 ||
									p == s || p - s == 3 || p - s == -3 ||
									p == k || p - k == 4 || p - k == -4 ||
									p == j || p - j == 5 || p - j == -5 ||
									p == i || p - i == 6 || p - i == -6)
								{
									continue;
								}
								for (int q = 0; q < 8; q++)
								{
									if (q == p || q - p == 1 || q - p == -1 ||
										q == n || q - n == 2 || q - n == -2 ||
										q == m || q - m == 3 || q - m == -3 ||
										q == s || q - s == 4 || q - s == -4 ||
										q == k || q - k == 5 || q - k == -5 ||
										q == j || q - j == 6 || q - j == -6 ||
										q == i || q - i == 7 || q - i == -7)
									{
										continue;
									}
									count++;
									//printf("i==%d,j==%d,k==%d,s==%d,m==%d,n==%d,p==%d,q==%d\n",
									//	i, j, k, s, m, n, p, q);
 
								
									arr[x++] = i;
									arr[x++] = j;
									arr[x++] = k;
									arr[x++] = s;
									arr[x++] = m;
									arr[x++] = n;
									arr[x++] = p;
									arr[x++] = q;
									DrawingQueue(arr, 8);
									x = 0;
								}
							}
						}
					}
				}
			}
		}
	}
	return count;
}
 
 
 
int main()
{
	int count = GetQueen();
	printf("count=%d\n", count);
	return 0;
}

 这样就可以得到每一种解法的具体分布位置

这就是穷举法的典型示例

硬币问题

在一个陌生的国度,有5种不同的硬币单位:15,23,29,41和67分.寻找所有组成18元8分(即1808分)的可能组合,有多少种可能?
假定对于所有面值的硬币你都有足够的硬币.

这道题目说leetcode上的题目

我们也可以通过穷举法实现

int  GetCoin()
{
	int count = 0;
	for (int i = 0; i < 1808/15; i++)
	{
		for (int j = 0; j < 1808 / 23; j++)
		{
			for (int k = 0; k < 1808 / 29; k++)
			{
				for (int m = 0; m < 1808 / 41; m++)
				{
					for (int n = 0; n < 1808 / 67; n++)
					{
						if (i * 15 + j * 23 + k * 29 + m * 41 + n * 67 == 1808)
						{
							count++;
						}
					}
				}
			}
 
		}
	}
	return count;
}

还有一道35美分的题目，和这个题目的解决方法是相同的，但是值得注意的是为什么把18元8角换成1808，这个主要是因为double类型的数据在输入时的零的个数会影响最终的结果

所以类似题目我们一般都采用转换为int类型直接使用

其次我们可以看到这个代码的时间复杂度是很高的，所以我们要对他进行优化，可以采用和八皇后问题类似的方法进行优化

int  GetCoin1()//优化版本
{
	int count = 0;
	for (int i = 0; i < 1808 / 15; i++)
	{
		for (int j = 0; j < 1808 / 23; j++)
		{
			if (i * 15 + j * 23 > 1808)
			{
				continue;
			}
 
			for (int k = 0; k < 1808 / 29; k++)
			{
				if (i * 15 + j * 23+k*29 > 1808)
				{
					continue;
				}
				for (int m = 0; m < 1808 / 41; m++)
				{
					if (i * 15 + j * 23 + k * 29 + m * 41 > 1808)
					{
						continue;
					}
					for (int n = 0; n < 1808 / 67; n++)
					{
						if (i * 15 + j * 23 + k * 29 + m * 41 + n * 67 == 1808)
						{
							count++;
						}
					}
				}
			}
 
		}
	}
	return count;
}
int main()
{
	int count = GetCoin1();
	printf("count=%d\n", count);
	return 0;
}

这样就一定程度降低了他的时间复杂度，得到了一个相对来说优化效果比较好的实现方式。