1.八皇后问题
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。
2.要点及思路
通过思考发现，暴力算法可以进行优化，当已经放置了一部分皇后时，可能剩余的皇后无论如何放置都不可能合法，此时也没必要递归下去了，直接返回上层即可。
比如在5×5的皇后中：（1，3）（2，5）（3，1）已经放置了皇后，剩下的两个无论如何放置都不可能合法。
代码如下
1 #include<cstdio> 2 #include<cstdlib> 3 using namespace std; 4 int n, P[20+1], hashTable[20+1]; 5 int count = 0; 6 void generateP(int index){ 7 if(index == n+1) { 8 count++; 9 return ; 10 } 11 for(int x = 1; x <= n; x++) { 12 if(hashTable[x] == false) { 13 bool flag = true; 14 for(int pre = 1; pre < index; pre++) { 15 if(abs(index - pre) == abs(x - P[pre])) { 16 flag = false; 17 break; 18 } 19 } 20 if(flag) { 21 P[index] = x; 22 hashTable[x] = true; 23 generateP(index + 1); 24 hashTable[x] = false; 25 } 26 } 27 } 28 } 29 int main() 30 { 31 scanf("%d", &n); 32 generateP(1); 33 printf("%d\n", count); 34 return 0; 35 }
原文：https://www.cnblogs.com/really41/p/10537363.html