queen.cpp

一个通过皇后算法构造稀疏矩阵的c++代码 矩阵以数组形式存储

//queen.cpp

#include "queen.h"



Queen::Queen(int n,int *QueenArray)
{
	int i;
    difpi=new int[n];//分配相应的堆内存
    dp=new int[2*n-1];
    pi=new int[n];
    sumpi=new int[n];
    dn=new int[2*n-1];
    clock_t start,end;
	Myrandom=new Random();
    if(n<8){cout<<"Illegal input!"; }//保证输入的皇后数在8-60000之间
    else
        if(n>65535){n=60000;cout<<"Auto fall to 60000!\n";}
    start=clock();//记录开始时间
    do{
        generate_permutation(pi,n);//随机产生一组N 个皇后的棋盘排列
        find_a_solution(pi,sumpi,difpi,dn,dp,n);//寻找正确的皇后棋盘排列
    }
    while(is_collision(dn,dp,n));//如果N个皇后在棋盘上的排列仍有冲突继续执行循环体
    end=clock();//记录结束时间
//(end-start)/CLK_TCK 表示寻找一个正确的N个皇后棋盘排列所需要的时间
    //result_saved((end-start)/CLK_TCK);
	for(i=0;i<n;i++)
	QueenArray[i]=pi[i];
}

Queen::~Queen(){
    delete[]pi;
    delete[]sumpi;
    delete[]difpi;
    delete[]dn;
    delete[]dp;
}


int Queen::test_collision(const int&ia,int n){
    for( int m=0;m<n;m++)//测试任意两个位置是否存在冲突
    if((ia!=m)&&((sumpi[ia]==sumpi[m])||(difpi[ia]==difpi[m])))
        return 1;
    return 0;
}
int Queen::test_collision_down(const int&ib,const int&jb,int n){
    int dnx=0,dpx=0,dny=0,dpy=0;
    for(int i=0;i<n;i++)//测试i所在负对角线上是否有皇后放置
        if(jb+pi[ib]==sumpi[i]) {dnx=1;break;}
    for( i=0;i<n;i++)//测试i所在正对角线上是否有皇后放置
        if(jb-pi[ib]==difpi[i]) {dpx=1;break;}
    for(i=0;i<n;i++)//测试j所在负对角线上是否有皇后放置
        if(ib+pi[jb]==sumpi[i]) {dny=1;break;}
    for(i=0;i<n;i++)//测试j所在正对角线上是否有皇后放置
        if(ib-pi[jb]==difpi[i]){ dny=1;break;} //交换后i，j所在位置的正负对角线上的冲突数
int after_swap=dn[jb+pi[ib]]+dp[jb-pi[ib]+n-1]+dn[ib+pi[jb]]+dp[ib-pi[jb]+n-1]+dnx+dpx+dny+dpy;

//交换前i，j所在位置的正负对角线上的冲突数
int before_swap=dn[sumpi[ib]]+dp[difpi[ib]+n-1]+dn[sumpi[jb]]+dp[difpi[jb]+n-1];
return after_swap<before_swap?1:0;//如果交换后冲突数减少返回1否则为0

}
void Queen::perform_swap(const int&ic,const int&jc,int n){
    int p=pi[ic]; //交换i，j皇后位置后需重新计算相应的正负对角线上的特征值
    pi[ic]=pi[jc];
    pi[jc]=p;
    sumpi[ic]=ic+pi[ic];
    difpi[ic]=ic-pi[ic];
    sumpi[jc]=jc+pi[jc];
    difpi[jc]=jc-pi[jc];
    sum_all_n_diagonals(pi,sumpi,n);
    sum_all_p_diagonals(pi,difpi,n);
}
void Queen::sum_all_n_diagonals(int*pi,int*sumpi,int n){
    int sum=0;
    for(int m=0;m<(2*n-1);m++)//统计每条负对角线上存在的冲突数
    {    int k=1;
        for(int i=0;i<n;i++)
            if(sumpi[i]==sum)k++;
        sum=m+1;
        dn[m]=k-1;
        if(dn[m]>0) dn[m]=dn[m]-1;
    }
}
void Queen::sum_all_p_diagonals(int*pi,int*difpi,int n){
    int dif;
    for(int m=0;m<(2*n-1);m++)//统计每条正对角线上存在的冲突数
    {        int k=1;
        dif=m-(n-1);
        for(int i=0;i<n;i++)
        if(difpi[i]==dif)k++;
        dp[m]=k-1;
        if(dp[m]>0) dp[m]=dp[m]-1;
    }
}

void Queen::sum_each_n_diagonal(int*dn,int*sumpi,int n){
    for(int i=0;i<n;i++)//计算每个皇后所在位置负对角线的特征值
        sumpi[i]=i+pi[i];
}
void Queen::sum_each_p_diagonal(int*dp,int*difpi,int n){
    for(int i=0;i<n;i++)////计算每个皇后所在位置正对角线的特征值
        difpi[i]=i-pi[i];
}
int Queen::is_collision(int*dn,int*dp,int n){
    int sumdn=0,sumdp=0;
    for(int m=0;m<(2*n-1);m++)//计算正负对角线上的冲突数
    {
    sumdn=sumdn+dn[m];
        sumdp=sumdp+dp[m];
    }
return (sumdp+sumdn)!=0?1:0;//如果冲突数不为零就返回1否则为0
}
void Queen::generate_permutation(int* pi,int n){
    srand(1);
    for(int i=0;i<n;i++)//随机产生n个位置不同的皇后
    {
        pi[i]=(*Myrandom).uniform(0, n);
        for(int j=0;j<i;j++)
            while(pi[j]==pi[i])
            {
                j=0;
                pi[i]=(*Myrandom).uniform(0, n);
            }
    }
}
void Queen::find_a_solution(int*pi,int*sumpi,int*difpi,int*dn,int*dp,int n){
    int swaps_performed=0;
    sum_each_n_diagonal(pi,sumpi,n);
    sum_each_p_diagonal(pi,difpi,n);
    sum_all_n_diagonals(dn,sumpi,n);
    sum_all_p_diagonals(dp,difpi,n);
    do
    {
    swaps_performed=0;
    for(int i=0;i<n;i++)//向减少N个皇后冲突的趋势排列皇后位置
    for(int j=i+1;j<n;j++)
        if(test_collision(i,n)||test_collision(j,n))
        if(test_collision_down(i,j,n))
        {
        perform_swap(i,j,n);
        swaps_performed=swaps_performed+1;
        }
    }
    while( swaps_performed!=0);
}