1. 問(wèn)題描述

在$n\times n$的棋盤上擺放$n$個(gè)皇后，使任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上

2. 問(wèn)題分析

下以求解4皇后問(wèn)題為例，分析4皇后問(wèn)題的排列樹以及回溯過(guò)程：

搜索及回溯過(guò)程：

解空間樹：

3. 算法設(shè)計(jì)

1. 算法思想

①用數(shù)組x[]存放皇后的位置，x[k]表示第k個(gè)皇后放置的位置
②先在第一行放置第1個(gè)皇后，然后依2、3、…、n的次序放置其他皇后，當(dāng)?shù)趎個(gè)皇后放置好后產(chǎn)生一個(gè)可行解（為得到所有解，還需要繼續(xù)試探第n個(gè)皇后的下一個(gè)位置）
③試探每個(gè)皇后的位置都是從第1列開始的
④當(dāng)?shù)趉個(gè)皇后試探了所有列都不能放置時(shí)，則回溯到第k-1個(gè)皇后，試探第k-1個(gè)皇后的下一個(gè)位置：如果第k-1個(gè)皇后的列號(hào)x[k-1]<n，則將其移到下一列，繼續(xù)試探；否則，再回溯到第k-2個(gè)皇后，依次類推
⑤放置第k個(gè)皇后應(yīng)與前面已經(jīng)放置的k-1個(gè)皇后不發(fā)生沖突
⑥若第1個(gè)皇后的所有位置回溯完畢，則算法結(jié)束

2. 代碼實(shí)現(xiàn)

#include<stdio.h>
#include<math.h>
#include<string>
//考察皇后k放置在x[k]列是否發(fā)生沖突
int Place(int k, int x[]) {											
	for (int i = 1; i < k; i++)
		/* 
           x[k] == x[i]：是否在同列
           Math.abs(k - i) == Math.abs(x[k] - x[i])：是否在同一斜線
         */
		if (x[k] == x[i] || fabs(k - i) == fabs(x[k] - x[i]))
			return 1;										//沖突則返回1
	return 0;
}
/*
	求解n皇后問(wèn)題
*/
//非遞歸算法
void Queens(int n, int x[]) {							
	int i = 1;												//i表示當(dāng)前行，也表示放置第i個(gè)皇后
	x[i] = 0;												//x[i]是當(dāng)前列，每個(gè)新考慮的皇后初始位置置為0列
	while (i >= 1) {										//尚未回溯到頭，循環(huán)
		x[i]++;												//原位置后移動(dòng)一列
		while (x[i] <= n && Place(i, x) == 1)				//發(fā)生沖突，試探下一個(gè)位置(i, x[i])
			x[i]++;
		if (x[i] <= n) {									//為第i個(gè)皇后找到了一個(gè)合適位置(i, x[i])
			if (i == n) {									//若放置了所有皇后，輸出一個(gè)解
				for (int k = 1; k <= n; k++)
					printf("%d ", x[k]);
				printf("\n");
			}
			else {											//若皇后沒(méi)有放置完
				i++;										//轉(zhuǎn)向下一行，即開始下一個(gè)新皇后的放置
				x[i] = 0;									//每個(gè)新考慮的皇后初始位置置為0列
			}
		}
		else i--;											//若第i個(gè)皇后找不到合適的位置，則回溯到上一個(gè)皇后
	}
}

//遞歸算法
void Queens(int i, int x[]， int n){
if(i > n){
	for (int k = 1; k <= n; k++)							//n個(gè)皇后都放置好，輸出
		printf("%d ", x[k]);
	printf("\n");
}else
	for(int j = 1; j <= n; j++){							//每層均有n種放法
		x[i] = j;											//放置皇后t在第i列即x[t]
		if(Place(i, x) == 0)								//不沖突，考察皇后t放置在x[t]列是否發(fā)生沖突
			Queens(i+1, x, n);								//繼續(xù)遞歸放置下一個(gè)皇后
	}		
}

void main() {
	int n;
	printf("請(qǐng)輸入皇后個(gè)數(shù)：");
	scanf_s("%d", &n);
	int *x = (int *)malloc(sizeof(int)*(n+1));
	//非遞歸調(diào)用
	Queens(n, x);
	//遞歸調(diào)用
	//Queens(1, x, n);
}

4. 復(fù)雜度分析

該算法中每個(gè)皇后都要試探n列，共n個(gè)皇后，其解空間是一棵子集樹，每個(gè)結(jié)點(diǎn)可能有n棵子樹，對(duì)應(yīng)的算法時(shí)間復(fù)雜度為$O(n^n)$
利用顯示約束排除兩個(gè)皇后在同一行或同一列的方法，解空間樹就是一棵排列樹，因此共有$n!$個(gè)葉子結(jié)點(diǎn)，所以算法的時(shí)間復(fù)雜度可以降為$O(n!)$文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-441916.html

到了這里，關(guān)于3.2 回溯法—N皇后問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！