[算法设计]全排列与n皇后问题

全排列

递归算法求全排

/*
递归求全排
*/
const int MaxN = 10;
const int MAXSIZE = 1000;
int P[MaxN];
bool hashTable[MAXSIZE] = { false }; //空间换取时间
int n;
void generateP(int index) {
	if (index == n + 1) {
		for (int i = 1; i <= n; ++i) {
			printf("%d", P[i]);
		}
		printf("\n");
		return;
	}
	for (int j = 1; j <= n; ++j) {
		if (hashTable[j] == false) {
			P[index] = j;
			hashTable[j] = true;
			generateP(index + 1);
			hashTable[j] = false;
		}
	}
}
int main() {
	n = 5;
	generateP(1);
}

n皇后问题

//n皇后问题,回溯法
int count = 0;
void queen(int index) {//第n列的皇后
	if (index == n + 1) {//此时每一列都有一个皇后
		count++;
		printf("%d\n",count);
		return;
	}
	for (int i = 1; i <= n; ++i) {
		if (hashTable[i] == false) {//没有被使用过
			bool flag = true; //表示当前序列与之前的皇后不冲突
			for (int pre = 1; pre <= index; ++pre) {//回溯剪枝
				//不能在同一对角线上
				if (abs(pre - index) == abs(i - P[pre])) {
					flag = false;
					break;
				}
			}
			if (flag) {
				P[index] = i;
				hashTable[i] = true;
				queen(index + 1);
				hashTable[i] = false;
			}
		}
	}

}

int main() {
	n = 8;
	queen(1);
}