n皇后问题（回溯法-递归法和循环法，最小冲突法（较快解决10000级别问题））

阳光穿透心脏的1/2处 2022-05-11 17:36 149阅读 0赞

### 文章目录 ###

*   *  n皇后问题简单解释
     *  递归版本
     *  非递归版本-找到一个可行解版本
     *  非递归版本-找到所有可行解版本
     *  非递归版本二
     *  最小冲突算法--5000级别较快
     *  最小冲突算法改进
     *  关于更高性能的算法

## n皇后问题简单解释 ##

对于一个`n*n`的棋盘来说，皇后如果是同行同列或者是在同一斜对角上，就是会相互击杀。

所以，我们需要找到一个安全的（**使得所有皇后之间不相互击杀**）安排方式。

## 递归版本 ##

#include <iostream>
    using namespace std;
    #include <cmath>
    int n;
    bool place(int x[], int k) { 
    	for (int i = 1; i < k; ++i)
    		if (x[i] == x[k] || (abs(x[i] - x[k]) == abs(i - k))) return false;
    	return true;
    }
    
    void n_queens(int k, int x[]) { 
    	if (k > n) { 
    		for (int i = 1; i <= n; ++i) cout << x[i] << " ";
    		cout << endl;
    	}
    	else { 
    		for (int i = 1; i <= n; ++i) { 
    			x[k] = i;
    			if (place(x, k)) n_queens(k + 1, x);
    		}
    	}
    }
    int main() { 
    	cin >> n;
    	int *x = new int[n+1];
    	n_queens(1, x);
    	delete[]x;
    	system("pause");
    }

输入一个n，就可以输出对应的n皇后的安排方式。

4
    2 4 1 3
    3 1 4 2

上面的数组含义，即，在第i行皇后在第x\[i\]列。

## 非递归版本-找到一个可行解版本 ##

#include <iostream>
    using namespace std;
    #include <cmath>
    int n;
    bool place(int x[], int k) { 
    	for (int i = 1; i < k; ++i)
    		if (x[i] == x[k] || (abs(x[i] - x[k]) == abs(i - k))) return false;
    	return true;
    }
    
    void n_queens(int k, int x[]) { 
    	k = 1;
    	x[1] = 0;
    	while (k > 0) { 
    		x[k] ++;
    		while ((x[k] <= n) && (!place(x, k))) x[k]++;
    		if (x[k] <= n) { 
    			if (k == n) break; // 找到了一种解
    			else { 
    				x[++k] = 0;
    			}
    		}
    		else { 
    			x[k] = 0; k--; // 回溯 这条路走不通
    		}
    	}
    	for (int i = 1; i <= n; ++i) cout << x[i] << " ";
    	cout << endl;
    }
    int main() { 
    	cin >> n;
    	int *x = new int[n+1];
    	n_queens(1, x);
    	delete[]x;
    	system("pause");
    }

运行情况为

4
    2 4 1 3

## 非递归版本-找到所有可行解版本 ##

#include <iostream>
    using namespace std;
    #include <cmath>
    int n;
    bool place(int k, int x[]) { 
    	for (int i = 1; i < k; ++i)
    		if (x[i] == x[k] || (abs(x[i] - x[k]) == abs(i - k))) return false;
    	return true;
    }
    
    void n_queens(int x[]) { 
    	for (int m = 1; m <= n; ++m) x[m] = 0;
    	int i = 1, j;
    	while (i <= n) { 
    		j = x[i] + 1;
    		while (j <= n) { 
    			x[i] = j; //将第i行的皇后放在第j列上
    			if (place(i, x)) break; // 跳出
    			else j++; // 寻找下一个
    		}
    		if (j == n + 1) {  // 在这一行，找了所有列都不对 
    			if (i == 1) break; // 找遍了所有方法 都没有结果
    			else i--; // 回溯到上一行
    		} else if (i == n) {  // 全部找到了
    			for (int m = 1; m <= n; ++m) cout << x[m] << " ";
    			cout << endl;
    		}
    		else {  x[++i] = 0; }
    	}
    }
    int main() { 
    	cin >> n;
    	int *x = new int[n + 1];
    	n_queens(x);
    	delete[]x;
    	system("pause");
    }

运行的结果;

4
    2 4 1 3
    3 1 4 2

## 非递归版本二 ##

#include <iostream>
    using namespace std;
    #include <cmath>
    int n;
    int *x;
    bool place(int x[], int k) { 
    	for (int i = 1; i < k; ++i)
    		if (x[i] == x[k] || (abs(x[i] - x[k]) == abs(i - k))) return false;
    	return true;
    }
    
    void iterativeBacktrack() { 
    	int t = 1;
    	int *f = new int[n + 1];
    	for (int i = 1; i <= n; ++i) f[i] = 1;
    	while (t > 0) { 
    		if (f[t] <= n) { 
    			while (f[t] <= n){ 
    				x[t] = f[t];
    				if (place(x, t)) {  // 第k位放的没有问题
    					f[t]++;
    					if (t == n) {  // output
    						for (int m = 1; m <= n; ++m) cout << x[m] << " ";
    						cout << endl;
    					}
    					else {  
    						t++; // 考虑下一行的皇后位置
    						break;
    					}
    				} else f[t]++; 
    			}
    		}
    		else {  
    			f[t] = 1; 
    			t--;
    		}
    	}
    	delete[] f;
    }
    
    int main() { 
    	cin >> n;
    	x = new int[n + 1];
    	iterativeBacktrack();
    	delete[]x;
    	system("pause");
    }

## 最小冲突算法–5000级别较快 ##

（只能找到一个解）

> 学习了下面这个链接的代码，做了很详细的笔记  
> [https://www.cnblogs.com/fstang/archive/2013/05/12/3073598.html][https_www.cnblogs.com_fstang_archive_2013_05_12_3073598.html]

*  解决n=5000的数据 20s
 *  解决n=6000的数据 80s

#include <iostream>
    using namespace std;
    #include <ctime>
    #define MAX 6000 //最多可能皇后数
    #define swap(a,b) {int t = a; a = b; b = t;}
    //row[i]表示当前摆放方式下第i行的皇后数，col[i]表示当前摆放方式下第i列的皇后数
    int row[MAX];
    int col[MAX];
    
    int N; //放置N个皇后在N*N棋盘上
    
    					//从左上到右下的对角线上row-col值是相同的，但是这个值有可能是负值，最小为-(N-1)，
    					//所以可以做个偏移，统一加上N-1，这样这个值就在[0,2*N-2]范围内，将这个值作为该对角线的编号
    					//pdiag[i]表示当前摆放方式下编号为i的对角线上的皇后数
    int pdiag[2 * MAX];//principal diagonal,主对角线，左上到右下（表示和主对角线平行的2N-1条对角线）
    
    				   //从右上到左下的对角线row+col的值相同，取值范围为[0, 2 * MAX - 2]，作为对角线编号
    				   //cdiag[i]表示编号为i的对角线上的皇后数
    int cdiag[2 * MAX];//counter diagonal,副对角线
    
    				   //R[]用来存储皇后放置位置，R[row] = col表示(row,col)处,即“第row行第col列”有个皇后
    int R[MAX];
    
    //给定二维矩阵的一个点坐标，返回其对应的左上到右下的对角线编号
    int getP(int row, int col) { 
    	return row - col + N - 1;
    }
    
    //给定二维矩阵的一个点坐标，返回其对应的右上到左下的对角线编号
    int getC(int row, int col) { 
    	return row + col;
    }
    
    //返回begin, begin + 1, ... , end - 1 这end - begin个数中的随机的一个
    int my_rand(int begin, int end) { //左闭右开[begin, end)
    	return rand() % (end - begin) + begin;
    }
    
    //原地shuffle算法，算法导论中的randomize in place算法
    void randomize(int a[], int begin, int end)// 左闭右开
    { 
    	for (int i = begin; i <= end - 2; i++) { 
    		int x = my_rand(i, end);
    		swap(a[i], a[x]);
    	}
    }
    
    //初始化皇后的摆放，同时初始化row,col,pdiag,cdiag数组
    void init()
    { 
    	for (int i = 0; i < N; i++) { //N queens
    		R[i] = i;
    	}
    	randomize(R, 0, N);//初始化N个皇后对应的R数组为0~N-1的一个排列，即没有任意皇后同列，也没有任何皇后同行
    	for (int i = 0; i < N; i++) { 
    		row[i] = 1;//每行恰好一个皇后
    		col[i] = 0;//下面再做初始化的
    	}
    	for (int i = 0; i < 2 * N - 1; i++) { //N queens
    		pdiag[i] = 0;
    		cdiag[i] = 0;
    	}
    	for (int i = 0; i < N; i++) { //N queens
    		col[R[i]]++;
    		pdiag[getP(i, R[i])]++;
    		cdiag[getC(i, R[i])]++;
    	}
    }
    
    bool adjust_row(int row); // 调整下第row行的皇后的位置
    void print_result(); // 输出结果
    bool qualify(); //验证是否正确
    
    int main(int argc, const char *argv[])
    { 
    	srand((unsigned)time(NULL));// 设置好随机数种子
    	cin >> N;
    	init();
    	if (!qualify()) {  // 如果初始表不满足的话
    		bool can_terminate = false;
    		while (!can_terminate) { 
    			for (int i = 0; i < N; i++) { 
    				if (adjust_row(i)) { 
    					can_terminate = true;
    					break;
    				}
    			}
    		}
    	}
    	print_result();
    	system("pause");
    	return 0;
    }
    //用最小冲突算法调整第row行的皇后的位置（初始化时每行都有一个皇后，调整后仍然在第row行）
    //调整过后check一下看看是否已经没有冲突，如果没有冲突（达到终止状态），返回true
    bool adjust_row(int row) { 
    	int cur_col = R[row]; // 通过行得到列
    	int optimal_col = cur_col;// 最佳列号，设置为当前列，然后更新
    	int min_conflict = col[optimal_col]      // col不减一的原因是交换任然保证每行每列都有一个而已
    		+ pdiag[getP(row, optimal_col)] - 1  // 现在还没移过去
    		+ cdiag[getC(row, optimal_col)] - 1; // 对角线冲突数为当前对角线皇后数减一
    	for (int i = 0; i < N; i++) { //逐个检查第row行的每个位置
    		if (i == cur_col) continue; // 重复就跳过了
    		int conflict = col[i] + pdiag[getP(row, i)] + cdiag[getC(row, i)];
    		if (conflict < min_conflict) {  // 因为之前这个点还没有移动，所以到这之后肯定是还会
    			min_conflict = conflict;
    			optimal_col = i;
    		}
    	}
    	if (optimal_col != cur_col) { //要更新col,pdiag,cdiag
    		col[cur_col]--;
    		pdiag[getP(row, cur_col)]--;
    		cdiag[getC(row, cur_col)]--;
    
    		col[optimal_col]++;
    		pdiag[getP(row, optimal_col)]++;
    		cdiag[getC(row, optimal_col)]++;
    		R[row] = optimal_col;// 注意，这里我们没有移动 在这个列上的之前的那个行上的皇后
    		if (col[cur_col] == 1 && col[optimal_col] == 1
    			&& pdiag[getP(row, optimal_col)] == 1 && cdiag[getC(row, optimal_col)] == 1) { 
    			return qualify();//qualify相对更耗时，所以只在满足上面基本条件后才检查
    		}
    	}
    	//当前点就是最佳点，一切都保持不变
    	return false;//如果都没变的话，肯定不满足终止条件，否则上一次就应该返回true并终止了
    }
    bool qualify() { 
    	for (int i = 0; i < N; i++) { //N queens
    		if (col[R[i]] != 1 ||
    			pdiag[getP(i, R[i])] != 1 ||
    			cdiag[getC(i, R[i])] != 1) { 
    			return false;
    		}
    	}
    	return true;
    }
    void print_result()
    { 
    	cout << "the result is like this:\n";
    	for (int i = 0; i < N; i++) { 
    		cout << R[i] << " ";
    	}
    	cout << endl;
    	/*for (int j = 0; j < N; j++) { for (int k = 0; k < N; k++) { if (R[j] == k) cout << "*"; else cout << "-"; } cout << endl; }*/
    }

## 最小冲突算法改进 ##

根据观测，有两个函数经常调用，但是非常短。由于函数调用本身设计到压栈一直都

*  解决1w的数据需要6秒

#include <iostream>
    using namespace std;
    #include <ctime>
    #define MAX 1000005 //最多可能皇后数
    #define swap(a,b) {int t = a; a = b; b = t;}
    #define getP(row, col) (row - col + N - 1)
    #define getC(row, col) (row + col)
    //row[i]表示当前摆放方式下第i行的皇后数，col[i]表示当前摆放方式下第i列的皇后数
    int row[MAX];
    int col[MAX];
    
    int N; //放置N个皇后在N*N棋盘上
    
    					//从左上到右下的对角线上row-col值是相同的，但是这个值有可能是负值，最小为-(N-1)，
    					//所以可以做个偏移，统一加上N-1，这样这个值就在[0,2*N-2]范围内，将这个值作为该对角线的编号
    					//pdiag[i]表示当前摆放方式下编号为i的对角线上的皇后数
    int pdiag[2 * MAX];//principal diagonal,主对角线，左上到右下（表示和主对角线平行的2N-1条对角线）
    
    				   //从右上到左下的对角线row+col的值相同，取值范围为[0, 2 * MAX - 2]，作为对角线编号
    				   //cdiag[i]表示编号为i的对角线上的皇后数
    int cdiag[2 * MAX];//counter diagonal,副对角线
    
    				   //R[]用来存储皇后放置位置，R[row] = col表示(row,col)处,即“第row行第col列”有个皇后
    int R[MAX];
    
    给定二维矩阵的一个点坐标，返回其对应的左上到右下的对角线编号
    //int getP(int row, int col) { 
    // return row - col + N - 1;
    //}
    //
    给定二维矩阵的一个点坐标，返回其对应的右上到左下的对角线编号
    //int getC(int row, int col) { 
    // return row + col;
    //}
    
    //返回begin, begin + 1, ... , end - 1 这end - begin个数中的随机的一个
    int my_rand(int begin, int end) { //左闭右开[begin, end)
    	return rand() % (end - begin) + begin;
    }
    
    //原地shuffle算法，算法导论中的randomize in place算法
    void randomize(int a[], int begin, int end)// 左闭右开
    { 
    	for (int i = begin; i <= end - 2; i++) { 
    		int x = my_rand(i, end);
    		swap(a[i], a[x]);
    	}
    }
    
    //初始化皇后的摆放，同时初始化row,col,pdiag,cdiag数组
    void init()
    { 
    	for (int i = 0; i < N; i++) { //N queens
    		R[i] = i;
    	}
    	randomize(R, 0, N);//初始化N个皇后对应的R数组为0~N-1的一个排列，即没有任意皇后同列，也没有任何皇后同行
    	for (int i = 0; i < N; i++) { 
    		row[i] = 1;//每行恰好一个皇后
    		col[i] = 0;//下面再做初始化的
    	}
    	for (int i = 0; i < 2 * N - 1; i++) { //N queens
    		pdiag[i] = 0;
    		cdiag[i] = 0;
    	}
    	for (int i = 0; i < N; i++) { //N queens
    		col[R[i]]++;
    		pdiag[getP(i, R[i])]++;
    		cdiag[getC(i, R[i])]++;
    	}
    }
    
    bool adjust_row(int row); // 调整下第row行的皇后的位置
    void print_result(); // 输出结果
    bool qualify(); //验证是否正确
    
    int main(int argc, const char *argv[])
    { 
    	srand((unsigned)time(NULL));// 设置好随机数种子
    	clock_t startTime, endTime;
    	cin >> N;
    	
    	startTime = clock();
    	init();
    	if (!qualify()) {  // 如果初始表不满足的话
    		bool can_terminate = false;
    		while (!can_terminate) { 
    			for (int i = 0; i < N; i++) { 
    				if (adjust_row(i)) { 
    					can_terminate = true;
    					break;
    				}
    			}
    		}
    	}
    	endTime = clock();
    	print_result();
    	cout << "用时：" << 1.0*(endTime - startTime) / CLOCKS_PER_SEC <<"秒"<< endl;
    	system("pause");
    	return 0;
    }
    //用最小冲突算法调整第row行的皇后的位置（初始化时每行都有一个皇后，调整后仍然在第row行）
    //调整过后check一下看看是否已经没有冲突，如果没有冲突（达到终止状态），返回true
    bool adjust_row(int row) { 
    	int cur_col = R[row]; // 通过行得到列
    	int optimal_col = cur_col;// 最佳列号，设置为当前列，然后更新
    	int min_conflict = col[optimal_col]      // col不减一的原因是交换任然保证每行每列都有一个而已
    		+ pdiag[getP(row, optimal_col)] - 1  // 现在还没移过去
    		+ cdiag[getC(row, optimal_col)] - 1; // 对角线冲突数为当前对角线皇后数减一
    	for (int i = 0; i < N; i++) { //逐个检查第row行的每个位置
    		if (i == cur_col) continue; // 重复就跳过了
    		int conflict = col[i] + pdiag[getP(row, i)] + cdiag[getC(row, i)];
    		if (conflict < min_conflict) {  // 因为之前这个点还没有移动，所以到这之后肯定是还会
    			min_conflict = conflict;
    			optimal_col = i;
    		}
    	}
    	if (optimal_col != cur_col) { //要更新col,pdiag,cdiag
    		col[cur_col]--;
    		pdiag[getP(row, cur_col)]--;
    		cdiag[getC(row, cur_col)]--;
    
    		col[optimal_col]++;
    		pdiag[getP(row, optimal_col)]++;
    		cdiag[getC(row, optimal_col)]++;
    		R[row] = optimal_col;// 注意，这里我们没有移动 在这个列上的之前的那个行上的皇后
    		if (col[cur_col] == 1 && col[optimal_col] == 1
    			&& pdiag[getP(row, optimal_col)] == 1 && cdiag[getC(row, optimal_col)] == 1) { 
    			return qualify();//qualify相对更耗时，所以只在满足上面基本条件后才检查
    		}
    	}
    	//当前点就是最佳点，一切都保持不变
    	return false;//如果都没变的话，肯定不满足终止条件，否则上一次就应该返回true并终止了
    }
    bool qualify() { 
    	for (int i = 0; i < N; i++) { //N queens
    		if (col[R[i]] != 1 ||
    			pdiag[getP(i, R[i])] != 1 ||
    			cdiag[getC(i, R[i])] != 1) { 
    			return false;
    		}
    	}
    	return true;
    }
    void print_result()
    { 
    	cout << "the result is like this:\n";
    	for (int i = 0; i < N; i++) { 
    		cout << R[i] << " ";
    	}
    	cout << endl;
    	/*for (int j = 0; j < N; j++) { for (int k = 0; k < N; k++) { if (R[j] == k) cout << "*"; else cout << "-"; } cout << endl; }*/
    }

## 关于更高性能的算法 ##

下面的这个算法，是可以在20s内接触10w的数据规模的。  
[https://blog.csdn.net/yongnuzhibu/article/details/7178112][https_blog.csdn.net_yongnuzhibu_article_details_7178112]

[https_www.cnblogs.com_fstang_archive_2013_05_12_3073598.html]: https://www.cnblogs.com/fstang/archive/2013/05/12/3073598.html
[https_blog.csdn.net_yongnuzhibu_article_details_7178112]: https://blog.csdn.net/yongnuzhibu/article/details/7178112