2n皇后问题是8皇后问题的拓展那么我们就先讲解一下求解8皇后问题的基本思路。8皇后问题英文Eight queens是由国际棋手马克斯·贝瑟尔于1848年提出的问题。问题表述为在8×8格的国际上摆放8个皇后使其不能互相攻击即任意两个皇后都不能处于同一行、同一列或同一斜线上问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解后来有人用图论的方法解出92种结果。计算机发明后有多种计算机语言可以编程解决此问题。该文章部分文字转自百度百科官方回溯算法思路八皇后问题如果用穷举法需要尝试8的8次方16,777,216种情况。每一列放一个皇后可以放在第 1 行第 2 行……直到第8行。回溯法优于穷举法。将列A的皇后放在第一行以后列B的皇后放在第一行已经发生冲突。这时候不必继续放列C的皇后而是调整列B的皇后到第二行继续冲突放第三行不冲突了才开始进入列C。如此可依次放下列A至E的皇后如图2所示。将每个皇后往右边横向、斜向攻击的点位用叉标记发现列F的皇后无处安身。这时回溯到列E的皇后将其位置由第4行调整为第8行进入列F发现皇后依然无处安身再次回溯列E。此时列E已经枚举完所有情况回溯至列D将其由第2行移至第7行再进入列E继续。按此算法流程最终找到如图3所示的解成功在棋盘里放下了8个“和平共处”的皇后。继续找完全部的解共92个。回溯算法求解八皇后问题的原则是有冲突解决冲突没有冲突往前走无路可走往回退走到最后是答案。为了加快有无冲突的判断速度可以给每行和两个方向的每条对角线是否有皇后占据建立标志数组。放下一个新皇后做标志回溯时挪动一个旧皇后清除标志。代码bool chack(int y,int x) { for(int i0;icol;i) { for(int j0;jcol;j) { if(map[y][x]0)return false ; else if((ij)(xy)map[i][j]-1) return false ; else if(map[i][x]-1) return false; else if((y-x)(i-j)map[i][j]-1)return false; } } return true; } void queen(int row) { if(rowcol) { count; //摆放的种数加1 return; } for(int i0;icol;i) { if(chack(row,i)true) { map[row][i]-1; queen(row1); map[row][i]1; } } }问题描述给定一个n*n的棋盘棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后使任意的两个黑皇后都不在同一行、同一列或同一条对角线上任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法n小于等于8。2n皇后问题就是先摆放完一种皇后再用回溯法再摆放第二种皇后其中前面的皇后站过的位置不能再摆放了原理是一样的。代码#include stdio.h //蓝桥杯竞赛基础练习 #include iostream using namespace std; int col; //表示皇后的个数 int co0;// 表示不同的摆放种数 int map[100][100]{0}; //摆放皇后的地图 bool chack2(int y,int x) { for(int i0;icol;i) { for(int j0;jcol;j) { if(map[y][x]0||map[y][x]-1)return false ; else if((ij)(xy)map[i][j]-2) return false ; else if(map[i][x]-2) return false; else if((y-x)(i-j)map[i][j]-2)return false; } } return true; } bool chack(int y,int x) { for(int i0;icol;i) { for(int j0;jcol;j) { if(map[y][x]0)return false ; else if((ij)(xy)map[i][j]-1) return false ; else if(map[i][x]-1) return false; else if((y-x)(i-j)map[i][j]-1)return false; } } return true; } void queen2(int row) { if(rowcol) { co; return; } for(int i0;icol;i) { if(chack2(row,i)true) { map[row][i]-2; queen2(row1); map[row][i]1; } } } void queen(int row) { if(rowcol) { queen2(0); return; } for(int i0;icol;i) { if(chack(row,i)true) { map[row][i]-1; queen(row1); map[row][i]1; } } } int main() { cincol; for(int i0;icol;i) { for(int j0;jcol;j) { cinmap[i][j]; } } for(int i0;icol;i) { for(int j0;jcol;j) { map2[i][j]map[i][j]; } } queen(0); coutco; return 0; }
