问题描述

在n*n的棋盘上放n个皇后，每两两不同行，不同列，不同对角线。求合法方案数

思路

直接列举是不太现实的，复杂度非常的大，解决方法是采用行组合的方式。
从左到右，每一个数字是第n列的第i行占有格子，则可表示为i,i,i…,i这样总共只有n!个排列。
我们只需要根据每一个排列，内部判断是否有处于同一条对角线的情况即可
具体见《笔记》P116

解法

  1. 朴素算法（暴力法）：不考虑任何优化直接验证的方法
  1. int count = 0;
  2. void generateP(int index){
  3.     for(int x = 1; x <= n; x++){
  4.         if(hashTable[x]==false){//如果该数字还没放进排列中
  5.             P[index] = x;//就令当前位为该数字
  6.             hashTable[x] = true;//标志该数字已经放入排列
  7.             generateP(index + 1);//解决之后的数字
  8.             hashTable[x] = false;//返回后因为要进行下一轮排列，所以置回false
  9.         }
  10.     }
  11.     //排列生成完毕
  12.     if(index == n + 1){//递归边界，排列结束
  13.         bool flag = true;//默认合法标志
  14.         for(int i = 1; i <= n; i++){//i, j代表任意两个皇后
  15.             for(int j = i + 1; j <= n; j++){
  16.                 if(abs(i-j)==abs(P[i] - P[j])){//这行是判断是否处于同一对角线，需要记忆一下
  17.                     flag = false;//不符合，置false
  18.                 }
  19.             }
  20.         }
  21.         if(flag) count++;
  22.         return;
  23.     }    
  24. }
  1. 回溯法：指由于一些事实导致不需要任何一个字问题递归就可以直接返回上层的情况
  1. void generateP(int index){
  2.     if(index == n + 1){//边界返回
  3.         count++;
  4.         return;
  5.     }
  6.     for(int x = 1; x <= n; x++){//第x行
  7.         if(hashTable[x] == false){//第x行还没有皇后
  8.             bool flag == true;
  9.             for(int pre = 1; pre < index; pre++){//遍历之前的皇后
  10.                 if(abs(index - pre) == abs(x - P[pre])){
  11.                     flag = false;
  12.                     break;
  13.                 }
  14.             }
  15.             if(flag){//如果不需要回溯那么放一个皇后
  16.                 P[index] = x;
  17.                 hashTable[x] = true;
  18.                 generate(index + 1);
  19.                 hashTable[x] = false;
  20.             }
  21.         }
  22.     }
  23. }