皇后问题最快的解法（C语言）八皇后、十六皇后时间在毫秒级
//皇后问题最快的解法（C语言）八皇后、十六皇后时间在毫秒级
#include <windows.h># include<stdio.h># include<stdlib.h># include<time.h>#define O 134775813// TODO (xubo18056052430#1#): PB10210016 徐波LARGE_INTEGER lv,lv1,lv2,lv3,lv4;double totaltime,secondsPerTick;int step;/***********************************************************************************************/int dn(int n) //分组，根据经验值产生，网搜得到--取下列值是比较好，返回不同的值对实验结果影响很大{ if (n < 100)return n;else if (n < 1000)return 40;else if (n < 10000)return 60;else if (n < 100000)return 90;elsereturn 150;}/***********************************************************************************************//***********************************************************************************************/int rand1 = (unsigned)time(NULL); //rand1产生随机数int rand2(int range) //rand1线性同余随机数产生器{unsigned int x = 0x7fffffff, m, c = 1, a =O;m = x + 1;rand1 = (rand1 * a + 1)%m;double r =(double) rand1 / x;int r2 = (int)(r * range);return r2;}/***********************************************************************************************//***********************************************************************************************/void swap(int &a, int &b){ //交换两值int c;c = a;a = b;b = c;}/***********************************************************************************************//***********************************************************************************************/int chongtu(int n, int line1[], int line2[]){ //冲突int xubo = 0;for(int i = 0; i < n + n; i ++){if(line1[i] > 1){xubo = xubo + (line1[i] * (line1[i] - 1)) / 2;}if(line2[i] > 1){xubo = xubo + (line2[i] * (line2[i] - 1)) / 2;}}return xubo;}/***********************************************************************************************//***********************************************************************************************/int improve(int i, int j, int n, int q[], int line1[], int line2[]) //判断q[i]和q[j])交换后冲突的个数是否会减少{int xubo = 0;xubo = xubo + (1 - line1[i + q[i]]);xubo = xubo + (1 - line2[i - q[i] + n - 1]);xubo = xubo + (1 - line1[j + q[j]]);xubo = xubo + (1 - line2[j - q[j] + n - 1]);xubo = xubo + line1[i + q[j]];xubo = xubo + line2[i - q[j] + n - 1];xubo = xubo + line1[j + q[i]];xubo = xubo + line2[j - q[i] + n - 1];if(i + q[i] == j + q[j] || i - q[i] == j - q[j])xubo = xubo + 2;return xubo;}/***********************************************************************************************//***********************************************************************************************/void csh(int n, int m, int q[], int line1[], int line2[]){int i, end, rand3;bool *l1 = (bool *)malloc((n + n) * sizeof(bool));bool *l2 = (bool *)malloc((n + n) * sizeof(bool));for(i = 0; i < n; i ++){q[i] = i;line1[i] = 0;line2[i] = 0;l1[i] = false;l2[i] = false;}for(i = n; i < n + n; i ++){line1[i] = 0;line2[i] = 0;l1[i] = false;l2[i] = false;}for(i = 0, end = n; i < m; i ++, end --) //初始化（0 ~ m - 1）；前m行不会此时不会产生冲突{ //初始化后横竖无冲突，只要保证两斜线无冲突即可do{rand3 = i + rand2(end);}while(l1[i + q[rand3]] || l2[i - q[rand3] + n - 1]);swap(q[i], q[rand3]);line1[i + q[i]] ++;line2[i - q[i] + n - 1] ++;l1[i + q[i]] = true;l2[i - q[i] + n - 1] = true;}for(i = m, end = n - m; i < n; i ++, end--) //初始化line{rand3 = i + rand2(end);swap(q[i], q[rand3]);line1[i + q[i]] ++;line2[i - q[i] + n - 1] ++;}free(l1);free(l2);}/***********************************************************************************************//***********************************************************************************************/void work(int n, int m, int q[]){ QueryPerformanceFrequency( &lv ); secondsPerTick = 1000000.0 / lv.QuadPart;int temp, reduce, i, j;step = 0;int *line1 = (int *)malloc((n + n) * sizeof(int)); int *line2 = (int *)malloc((n + n) * sizeof(int)); QueryPerformanceCounter( &lv3 );csh(n, m, q, line1, line2);QueryPerformanceCounter( &lv4 );totaltime = secondsPerTick * (lv4.QuadPart-lv3.QuadPart);printf("\n初始化时间为：%e s ", totaltime/1000000); //初始化时间temp = chongtu(n, line1, line2);//printf("冲突次数= %d\n", temp);while(temp > 0){reduce = 0;for(i = m; i < n; i ++){if(line1[i + q[i]] == 1 && line2[i - q[i] + n - 1] == 1)continue;else{for(j = 0; j < n; j ++){if(i != j){reduce = improve(i, j, n, q, line1, line2);if(reduce < 0)break;}}if(reduce < 0) //可交换q[i]和q[j]，使总的冲突减少break;}}if(reduce < 0){step ++;line1[i + q[i]] --;line2[i - q[i] + n - 1] --;line1[j + q[j]] --;line2[j - q[j] + n - 1] --;swap(q[i], q[j]);line1[i + q[i]] ++;line2[i - q[i] + n - 1] ++;line1[j + q[j]] ++;line2[j - q[j] + n - 1] ++;temp = temp + reduce;}else{ csh(n, m, q, line1, line2); temp = chongtu(n, line1, line2);}}}/***********************************************************************************************//***********************************************************************************************/size_t **NQueen(size_t q_xubober) //实验要求size_t **NQueen(size_t Queen_xubober){ LARGE_INTEGER lv,lv1,lv2; double totaltime,secondsPerTick; QueryPerformanceFrequency( &lv ); secondsPerTick = 1000000.0 / lv.QuadPart;unsigned int **ee = (unsigned int **)malloc(4 * sizeof(unsigned int *)), loop = 3, i, j;for(i = 1; i < 4; i ++)ee[i] = (unsigned int *)malloc((q_xubober + 1) * sizeof(unsigned int));int *q = (int *)malloc(q_xubober * sizeof(int));int m = q_xubober - dn(q_xubober);printf("\n问题大小N= %d m= %d\n*************************************************************************\n", q_xubober, m); for(i = 1; i < 4; i ++){ QueryPerformanceCounter( &lv1 );work(q_xubober, m, q);QueryPerformanceCounter( &lv2 );totaltime = secondsPerTick * (lv2.QuadPart-lv1.QuadPart); printf("第%d次成功运行时间= %e s \n", i, totaltime/1000000); printf("\n*************************************************************************\n");for(j = 0; j < q_xubober; j ++)ee[i][j + 1] = q[j] + 1;}return ee;}/***********************************************************************************************//***********************************************************************************************/int main(){unsigned int i, j, k = 0, **ee = NULL;int n;printf("请输入皇后问题N的大小:\n");scanf("%d", &n);printf("\n————————————————运行结果————————————————\n");if(n<=3){ printf("\错误！没有解！"); exit(1); //输入小于4的数报错跳出}if(n>=1000000000003){ printf("\错误！没有解！"); exit(1); //输入大于的数报错跳出}ee = NQueen(n); if(n<=100){ //如果输入的n小于等于100，者输出皇后摆放位置序列，否者不输出，因为n大序列长 for(i = 1; i <=3; i++) //输出三个满足问题要求的皇后摆放位置序列try[1..3][1…n]。{ printf("\n\n第%d组解皇后摆放的位置序列位：\n",i);for(int j = 1; j < n + 1; j ++){for(k = 1; k < n + 1; k ++){if(k ==ee[i][j]){//printf("%d ",k); //只输出列printf("（%d，%d） ",j,k);} //输出行和列，第i个皇后摆放在(i,try[i])} } }} printf("\n\n————————————————运行结果————————————————\n\n\n");system("pause");return 0;}/***********************************************************************************************/// TODO (xubo18056052430#1#): PB10210016 徐波