皇后问题最快的解法（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  徐波