八皇后问题（N皇后问题）

2019-11-08 03:08:01

字体：大中小

来源：转载

供稿：网友

问题：在一个N*N的棋盘上摆放N个“皇后”，且两两不在同一直线和斜线上，求有多少种摆法

解法：使用递归和回溯的思想求解

代码：

#include <iostream>using namespace std;const int N = 8;// N皇后问题int map[N][N];// 棋盘数组，存储可直达该点的皇后个数static int methods = 0;// 遍历的方法数bool put(int pi, int pj){ if (pi == N-1){ //return true;// 若需输出其中一种解法，取消本行注释即可 methods++; return false; } map[pi][pj] = N; for (int i = 0; i < N; i++){ for (int j = 0; j < N; j++){ if (i == pi || j == pj || i + j == pi + pj || i - j == pi - pj){// 横纵斜线 map[i][j]++;// 可直达该点的皇后个数加1 } } } for (int j = 0; j < N; j++){ if (map[pi + 1][j] == 0){ if (put(pi + 1, j) == true){ return true; }// 下一行放置新的棋子 } } for (int i = 0; i < N; i++){ for (int j = 0; j < N; j++){ if (i == pi || j == pj || i + j == pi + pj || i - j == pi - pj){// 横纵斜线 map[i][j]--;// 撤销“可直达该点的皇后个数加1” } } } map[pi][pj] = 0; return false;}int main(){ for (int j = 0; j < N; j++){ if (put(0, j) == true){ for (int i = 0; i < N; i++){ for (int j = 0; j < N; j++){ if (map[i][j] == N + 1)// “自增1”过1次 cout << "●";// 此处放棋子 else cout << "○";// 此处为空 } cout << endl; } return 1; } } cout << "Kinds of handgrasp:" << methods << endl; return 0;}

上一篇：数据结构实验之栈六：下一较大值（二）

下一篇：图结构练习——最短路径（Dijkstra算法）