CUG-人工智能课程-N皇后问题

#include<iostream> #include<iomanip> using namespace std; #include <ctime> #define MAX 1000005 //最多皇后数 #define swap(a,b) {int t = a; a = b; b = t;} #define getSDid(row, col) (row - col + N - 1) #define getMDid(row, col) (row + col) //可解决大约几万以内的皇后问题，再多就要等好久了，40皇后以内用简单棋盘形式展示，更多皇后则直接输出皇后位置 int N; //皇后数，也是棋盘规格N*N int row[MAX]; //row行有几个皇后 int col[MAX]; //col列有几个皇后 int MDQnum[2 * MAX];//row行col列那个格子对应的主对角线上的皇后数 int SDQnum[2 * MAX];//row行col列那个格子对应的副对角线上的皇后数 int R[MAX]; //皇后位置，R[row]=col表示row行col列有一个皇后 int my_rand(int begin, int end) { //左闭右开[begin, end) return rand() % (end - begin) + begin; } 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,MDQnum,SDQnum数组 void initialization() { for (int i = 0; i < N; i++) { 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++) { MDQnum[i] = 0; SDQnum[i] = 0; } for (int i = 0; i < N; i++) { col[R[i]]++; MDQnum[getSDid(i, R[i])]++; SDQnum[getMDid(i, R[i])]++; } } //判断皇后摆放是否已经满足条件 bool OK() { for (int i = 0; i < N; i++) { if (col[R[i]] != 1 || MDQnum[getSDid(i, R[i])] != 1 || SDQnum[getMDid(i, R[i])] != 1) { return false; } } return true; } //最小冲突法调整皇后位置 bool MinimumConflictMethod(int row) { int now_col = R[row]; // 行得列 int optimal_col = now_col;// 最佳列，初始化为当前列 int min_conflict = col[optimal_col] + MDQnum[getSDid(row, optimal_col)] - 1 + SDQnum[getMDid(row, optimal_col)] - 1; for (int i = 0; i < N; i++) { //检查第row行的每个位置 if (i == now_col) continue; //重复跳过 int conflict = col[i] + MDQnum[getSDid(row, i)] + SDQnum[getMDid(row, i)]; if (conflict < min_conflict) { // 因为之前这个点还没有移动，所以到这之后肯定是还会 min_conflict = conflict; optimal_col = i; } } if (optimal_col != now_col) { //更新col,MDQnum,SDQnum col[now_col]--; MDQnum[getSDid(row, now_col)]--; SDQnum[getMDid(row, now_col)]--; col[optimal_col]++; MDQnum[getSDid(row, optimal_col)]++; SDQnum[getMDid(row, optimal_col)]++; R[row] = optimal_col; if (col[now_col] == 1 && col[optimal_col] == 1 && MDQnum[getSDid(row, optimal_col)] == 1 && SDQnum[getMDid(row, optimal_col)] == 1) { return OK(); } } return false; } void print_result1() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (j == R[i]) cout << "Q "; else cout << "x "; } cout << endl; } } void print_result2() { cout << "皇后位置为：" << endl; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (j == R[i]) cout << "第" << i + 1 << "行" << "第" << j + 1 << "列\t"; //else //cout << "x "; } if ((i + 1) % 6 == 0) cout << endl; } cout << endl; } int main(int argc, const char* argv[]) { srand((unsigned)time(NULL));// 设置好随机数种子 clock_t startTime, endTime; cin >> N; startTime = clock(); initialization(); if (!OK()) { //如果初始表不满足条件的话，往下执行 bool can_terminate = false; while (!can_terminate) { for (int i = 0; i < N; i++) { if (MinimumConflictMethod(i)) { can_terminate = true; break; } } } } endTime = clock(); //如果皇后数不多，那么以简单棋盘形式展示，如果皇后数过多，就以几行几列摆放皇后的形式展示 if (N <= 40) { print_result1(); } else { print_result2(); } cout << endl << "一共耗时：" << 1.0 * (endTime - startTime) / CLOCKS_PER_SEC << "秒" << endl; system("pause"); return 0; }