马鞍山建站,金融网站建设成功案例,企业模板,鞍山网络顾问有限公司#includeiostream using namespace std; #define N 8 //N代表皇后数 void queen() { int Count0; //计算总共的解的数量 int column[N1]; //column[m]n表示第m行#xff0c;第n行放置了皇后,这里下表并从0开始 int row[N1]; //row[m]1表示第m行没有皇后#xff0c;0表… #includeiostream using namespace std; #define N 8 //N代表皇后数 void queen() { int Count0; //计算总共的解的数量 int column[N1]; //column[m]n表示第m行第n行放置了皇后,这里下表并从0开始 int row[N1]; //row[m]1表示第m行没有皇后0表示有皇后 int b[2*N1]; //b[m]1表示第m条主对角线没有皇后 int c[2*N1]; //c[m]1表示第m条次对角线没有皇后0表示有皇后 int numQueen1; //计数已经放置的皇后数目当numQueenN时候则表示已经完成探测 int good1; //good1表示没有发生冲突,good0表示发生冲突 //初始化这些标记 for(int j0;jN1;j) { row[j]1; } for(int j0;j2*N1;j) { b[j]c[j]1; } column[1]1; column[0]0; //初始化第一行第一列第二行第二列放置皇后 do { //没有发生冲突则继续向下探测增加皇后或者判断当前是否是解 if(good) { //当前皇后数是解打印继续向下探测 if(numQueenN) { Count; cout找到解endl; for(int j1;jN1;j) { coutj列column[j]行endl; } //最后一个棋子向下移动,移动到本列最后一个 while(column[numQueen]N) { numQueen--; //皇后数减1即列数减1回溯 //回溯后将该列以及该列最后一行状态位修改 //第numQueen列column[numQueen]行处状态位置修改 row[column[numQueen]]1; b[numQueencolumn[numQueen]]1; c[NnumQueen-column[numQueen]]1; } column[numQueen]; //回溯至上一行向上一行的下一列继续探测 } //当前不是解那么继续向下探测 else { //改变该位置对应标志 row[column[numQueen]]0; b[numQueencolumn[numQueen]]0; c[NnumQueen-column[numQueen]]0; //本次位置没有发生冲突也不是正确解那么就应该向下探测下一列的第一行 column[numQueen]1; } } //如果当前发生了冲突就在本列继续向下如果到了本列最后一行则回溯到上一列 else { while(column[numQueen]N) //到了本列最后一行还是冲突那么回溯到上一列 { numQueen--; row[column[numQueen]]1; b[numQueencolumn[numQueen]]1; c[NnumQueen-column[numQueen]]1; } column[numQueen]; //发生冲突了又没有到本列的最后一行那么在本列继续向下一行探测 } //检测放置了这个位置后是否冲突 goodrow[column[numQueen]]b[numQueencolumn[numQueen]]c[NnumQueen-column[numQueen]]; }while(numQueen); coutN皇后总共找到解Count个endl; } void main() { queen(); system(pause); } 这种非递归方法还是比较容易理解的 另外还有递归方法先来看一下递归算法的伪代码 void trial(int row) { //递归时候我们从第0行开始然后每次递归时候都向下一行一直到棋盘的最后一行 //这时候就表示已经是正确的解了所有进入该函数首先判断是否是正确的解 if(rowN) { //输出此时的棋盘 } else { for(int i0;iN;i) { //不是解这时候需要在本行的每一列开始试探放旗子如果可以的话继续向下递归 #修改记录冲突的数组 if(放在这个位置不会冲突) { trial(row1); } 放在这里冲突那么修改回记录的数组继续下一列 } } } 下面给出递归的 void EightQueen (int row) { if(rowN) { PrintMap(); //打印棋盘 } else { int column; for (column 0; column N; column) { A[row] column; //代表第row行的第column列放皇后 if (IsCorrect (row, column)) //判断在第row行的第column列放皇后是否可行 { EightQueen (row 1); } //将标记数组修改回原来 } } } 查看源代码示例 查看源代码示例 转载于:https://blog.51cto.com/seanyxie/1375902
