采用随机重启爬山法、最小冲突法和遗传算法求解N皇后问题。

#include <iostream> #include "climbHill.h" #include "geneticAlgorithm.h" #include <vector> #include <time.h> #include <string> #include <stdlib.h> #include "MinConflict.h" using namespace std; // 定义N皇后问题，皇后数目为N #define random(x) (rand()%x) // 定义产生随机数的函数 static int N; // 初始化棋盘 void initChessboard(vector<int>& chessboard) { for (int i = 0; i < N; i++) chessboard.push_back(i); srand((unsigned)time(0)); for (int row1 = 0; row1 < N; row1++) { int row2 = random(N); // 随机交换行，打散棋盘，但保证皇后都在不同列 swap(chessboard[row1], chessboard[row2]); } } // 打印棋盘 void printChessboard(vector<int>& chessboard) { for (int i = 0; i < N; i++) { int num = chessboard[i]; for (int j = 0; j < num; j++) { cout << " + "; } cout << " Q "; for (int k = num + 1; k < N; k++) { cout << " + "; } cout << endl; } } int main() { //定义数据结构Vector<int> 下标代表行数，值代表列数，表示一个棋盘 N = 0; cout << "输入你要解决的N皇后问题的N值" << endl; cin >> N; cout << N << "皇后问题" << endl; cout << "请选择要使用的算法 " << endl; cout << "1. 随机重启爬山法 " << endl; cout << "2. 最小冲突算法 " << endl; cout << "3. 遗传算法 " << endl; cout << "4. 结束程序 " << endl; int choose;//选择的算法 // 初始化对象 // 1. 三种算法对应三个棋盘 vector<int> temp1_chessboard; vector<int> temp3_chessboard; // 3.解决算法的对象 //调用构造函数 climbHill sol1(N); geneticAlgorithm sol3(N); MinConflict sol2(N); while (1) { cin >> choose; switch (choose) { case 1: cout <<"随机重启爬山法 " << endl; initChessboard(temp1_chessboard); // 求解部分 temp1_chessboard = *sol1.solve(&temp1_chessboard); printChessboard(temp1_chessboard); cout << endl; break; case 2: cout << "最小冲突法 " << endl; // 求解部分 sol2.solve(); cout << endl; break; case 3: cout << "遗传算法" << endl; initChessboard(temp3_chessboard); // 求解部分 temp3_chessboard = *sol3.solve(temp3_chessboard); printChessboard(temp3_chessboard); cout << endl; break; case 4: exit(0); break; default: break; } } }