求类幻方算法?高手请进!

问题是这样的:(有些类似幻方算法)
有1到39的自然数,分3组(各不相同),每组13个自然数,如下:
x1,x2,.......x12,x13;
Y1,Y2,.......Y12,Y13;
N1,N2,.......N12,N13;
条件一:让每组各数和为260,即x1+x2+.......+x11+x12+X13=260;其他两组同;
条件二:每组对应的位相加的和相等为60,即X1+Y1+N1=60;X2+Y2+N2=60;.....X13+Y13+N13=60;
输出满足上述条件的组合X,Y,N;

我的算法不行,我的机器要跑300多年,
那位大侠帮帮忙!!有没有效率高一些的算法code,谢谢!!

53 个解决方案

#1

好难解，用了前向检验方法，但还是花时间太多，看来需要好的启发式方法

#2

楼主的题目真的很难，我目前的算法在我的机器上也需要11天左右才能跑出所有结果
我的机器的CPU Dothan 1.6 GHz (32位)

首先看我跑的一些结果

 1  2  3  4  5 25 27 28 36 33 35 30 31
20 21 19 22 32 29 26 24  9 10 14 18 16
39 37 38 34 23  6  7  8 15 17 11 12 13

 1  2  3  4  5 25 27 28 36 33 35 30 31
20 21 19 22 32 29 26 24 15 10 11 18 13
39 37 38 34 23  6  7  8  9 17 14 12 16

... ...

 1  2 19  4 23 29 26 24 15 33 35 18 31
20 37 38 22  5 25 27 28  9 10 14 12 13
39 21  3 34 32  6  7  8 36 17 11 30 16

... ...

 1  2 18 31 19  6 30 37 38 10 33 21 14
24 32 39  4 36 20  7 15  9 22 11 12 29
35 26  3 25  5 34 23  8 13 28 16 27 17

... ...

我的程序计算的是组合数，也就是说，对于我程序计算时的任两个结果X和Y
不能对X经过交换行及交换列的操作得到Y
如果要得列排列数，那只用将每一个计算结果，进行行排列和列排列获得
从而，对任一个结果，行排列有3!种，列排列有13!种，则对每一结果有 3! * 13! 种排列

经过初步估算，组合数估计有 1600多亿 种。
估计的依据介绍完算法原理后给出。

我的程序分为以下几个步骤：
第一步：计算所有1..39之间三个互不相同的数相加等于60的三元组（结果有181种）
第二步：对于181种组合，取13个不包括相同数的三元组的组合，此步计算所有这种组合（结果有703722种）
第三步：对于每二步计算的703722种组合的每一种，能够满足楼主题目要求的所有组合，即满足每行13个数之和为260

在我的电脑上
第一步：耗时在毫秒级
第二步：耗时在30分种左右
第三步：估计耗时 1277.24 * 703722 毫秒，约为10天半

下面是第三步的统计输出，据此可以估计耗时及结果数量：
Record Count: 703722, Error Count: 0
RecNo:      1, Time: 1242/1242 ms, Count: 220568/220568
RecNo:      2, Time: 1202/2444 ms, Count: 221403/441971
RecNo:      3, Time: 1311/3755 ms, Count: 221737/663708
RecNo:      4, Time: 1242/4997 ms, Count: 215003/878711
RecNo:      5, Time: 1272/6269 ms, Count: 219477/1098188
RecNo:      6, Time: 1272/7541 ms, Count: 223962/1322150
RecNo:      7, Time: 1272/8813 ms, Count: 227101/1549251
RecNo:      8, Time: 1272/10085 ms, Count: 226082/1775333
RecNo:      9, Time: 1251/11336 ms, Count: 227152/2002485
RecNo:     10, Time: 1232/12568 ms, Count: 230511/2232996
RecNo:     11, Time: 1272/13840 ms, Count: 239601/2472597
... ...
RecNo:    100, Time: 1292/127724 ms, Count: 250419/23920729
... ...

#3

代码如下:

// CSDN10.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <windows.h>

/*
http://community.csdn.net/Expert/topic/5150/5150907.xml?temp=.2919123
问题是这样的:(有些类似幻方算法)
有1到39的自然数,分3组(各不相同),每组13个自然数,如下:
x1,x2,.......x12,x13;
Y1,Y2,.......Y12,Y13;
N1,N2,.......N12,N13;
条件一:让每组各数和为260,即x1+x2+.......+x11+x12+X13=260;其他两组同;
条件二:每组对应的位相加的和相等为60,即X1+Y1+N1=60;X2+Y2+N2=60;.....X13+Y13+N13=60;
输出满足上述条件的组合X,Y,N;

我的算法不行,我的机器要跑300多年,
那位大侠帮帮忙!!有没有效率高一些的算法code,谢谢!!

*/

__int64 Masks[39]; // 使用各个位对应一个元数
const int N=181;
__int64 Sum60[N];

void InitMasks()
{
__int64 x = 1;
for (int i=0; i<39; i++)
{
Masks[i] = x;
x <<=1;
}
}

int GetSum60Count()
{
int iRes=0;
for (int i=0; i<39; i++)
for (int j=i+1; j<39; j++)
{
int x = 60 - 3 - i - j;
if ((x>j) && (x<39))
iRes ++;
}
return iRes;
// The Result is 181
}


void CalcSum60()
{
int iRes=0;
for (int i=0; i<39; i++)
for (int j=i+1; j<39; j++)
{
int x = 60 - 3 - i - j;
if ((x>j) && (x<39))
{
Sum60[iRes] = Masks[i] | Masks[j] | Masks[x];
iRes ++;
}
}
}

void PrintSum60()
{
for (int i=0; i<N; i++)
printf("%3d is %010I64X\n", i, Sum60[i]);
}

int GetSetCount(__int64 s[], int SN, int M)
{
if (M<0) return 0;
if (M==0) return 1;
if (SN<=0) return 0;

int iCount=0;
__int64 a[14];
int indexes[14];
indexes[0] = -1;
a[0] = 0;
int level=1;
int nextIndex = 0;
while (true)
{
__int64 x = a[level-1];
while ((nextIndex < SN) && (x & s[nextIndex]))
nextIndex ++;
if (nextIndex < SN)
{
if (level == M)
{
iCount ++;
nextIndex ++;
}
else
{
a[level] = x | s[nextIndex];
indexes[level] = nextIndex;
level ++;
nextIndex ++;
}
}
else
{
// 退一级
level--;
nextIndex = indexes[level] + 1;
if (!level) break;
// if (level == 2)
//   printf("i1: %d, i2: %d, count: %d\n", indexes[1], indexes[2], iCount);
}

}

return iCount;
// 703722 种 // 703722 种, 计算用时 19分左右
}

const char * DATA_FILE_NAME = "E:\\M39.DAT";

void CalcSets(__int64 s[], int SN, int M)
{
if (SN <= 0) return;
if (M != 13) return;

const BUFF_SIZE = 1024;
unsigned char IndexBuff[BUFF_SIZE][13];
FILE * fFile = fopen(DATA_FILE_NAME, "wb");

int iCount=0;
int iTotalCount=0;
__int64 a[14];
int indexes[14];
indexes[0] = -1;
a[0] = 0;
int level=1;
int nextIndex = 0;
while (true)
{
__int64 x = a[level-1];
while ((nextIndex < SN) && (x & s[nextIndex]))
nextIndex ++;
if (nextIndex < SN)
{
if (level == M)
{
indexes[level] = nextIndex;
for (int i=0; i<13; i++)
IndexBuff[iCount][i] = indexes[i+1];
iCount ++;
iTotalCount ++;
nextIndex ++;
if (iCount == BUFF_SIZE)
{
fwrite(IndexBuff, 13, iCount, fFile);
iCount = 0;
}
}
else
{
a[level] = x | s[nextIndex];
indexes[level] = nextIndex;
level ++;
nextIndex ++;
}
}
else
{
// 退一级
level--;
nextIndex = indexes[level] + 1;
if (!level) break;
//if ((level== 2) && (a[1] & 1 == 0)) break;
if (level == 2)
   printf("i1: %d, i2: %d, count: %d\n", indexes[1], indexes[2], iTotalCount);
}

}
if (iCount>0)
{
fwrite(IndexBuff, 13, iCount, fFile);
iCount = 0;
}
fclose(fFile);

printf("Write finished\n");

// 703722 种 // 703722 种, 计算用时 19分左右
}

void CheckSetFile()
{
FILE * fFile = fopen(DATA_FILE_NAME, "rb");
int iTotalCount = 0;
int iErrorCount = 0;
const BUFF_SIZE = 1024;
unsigned char IndexBuff[BUFF_SIZE][13];
while (true)
{
int iRes = fread(IndexBuff, 13, BUFF_SIZE, fFile);
if (iRes > 0) 
{
iTotalCount += iRes;
for (int i=0; i<iRes; i++)
{
__int64 x=0;
for (int j=0; j<13; j++)
x |= Sum60[IndexBuff[i][j]];
if (x != 0x7FFFFFFFFF)
iErrorCount ++;
}
}
if (iRes < BUFF_SIZE) break;
}

fclose(fFile);

printf("Record Count: %d, Error Count: %d\n\n", iTotalCount, iErrorCount);
}

// char Buff[]

__int64 iMatchCount;

void CalcOneSet(unsigned char * p, int iRecNo)
{
int a[13][3];
for (int i=0; i<13; i++)
{
int iPos = 0;
__int64 x = Sum60[p[i]];
for (int j=0; j<39; j++)
if (x & Masks[j])
{
a[i][iPos] = j+1;
iPos++;
}
}
int i1[13];
for (i=0; i<13; i++) i1[i] = 0;
while (true) 
{
int sum=0;
for (i=0; i<13; i++)
sum += a[i][i1[i]];
if (sum == 260) 
{
int b[13][2];
for (int j=0; j<13; j++)
{
int iPos=0;
for (int k=0;k<3;k++)
if (k!=i1[j]) 
b[j][iPos++] = a[j][k];
}
// iMatchCount ++;
int i2[13];
for (j=0; j<13; j++) i2[j]=0;
while (true)
{
int sum2=0;
for (j=0; j<13; j++)
sum2 += b[j][i2[j]];
if (sum2 == 260)
{
iMatchCount ++;
// 输出
/*
printf("\n");
for (j=0; j<13; j++)
printf("%2d ", a[j][i1[j]]);
printf("\n");
for (j=0; j<13; j++)
printf("%2d ", b[j][i2[j]]);
printf("\n");
for (j=0; j<13; j++)
printf("%2d ", b[j][1-i2[j]]);
printf("\n");
*/
}
for (j=12;j>=0;j--){if(i2[j]==1)i2[j]=0; else break;}
if (j<1)
break;
i2[j]++;
}
}

    //Now goto next visiting item
   for(i=12;i>=0;i--){if(i1[i]==2)i1[i]=0;else break;}
   if(i<1)
   break;//Finished
   i1[i]++;
}

}

void CalcAllSet()
{
FILE * fFile = fopen(DATA_FILE_NAME, "rb");
int iRecNo = 0;
const BUFF_SIZE = 16;
unsigned char IndexBuff[BUFF_SIZE][13];
iMatchCount = 0;
DWORD dwStartTick = ::GetTickCount();
DWORD dwLastTick = dwStartTick;
while (true)
{
int iRes = fread(IndexBuff, 13, BUFF_SIZE, fFile);
if (iRes > 0) 
{
for (int i=0; i<iRes; i++)
{
iRecNo++;
__int64 lastCount = iMatchCount;
CalcOneSet(IndexBuff[i], iRecNo);
DWORD dwCurTick = ::GetTickCount();
DWORD dwThis = dwCurTick - dwLastTick;
DWORD dwTotal = dwCurTick - dwStartTick;
dwLastTick = dwCurTick;
__int64 thisCount = iMatchCount - lastCount;
    printf("RecNo: %6d, Time: %u/%u ms, Count: %I64d/%I64d\n", 
iRecNo, dwThis, dwTotal, thisCount, iMatchCount);
}
}
if (iRes < BUFF_SIZE) break;
}

fclose(fFile);

printf("Match count %d\n", iMatchCount);

}

void CalcRecordAndWriteToFile()
{
InitMasks();
// printf("GetSum60Count=%d\n", GetSum60Count());
CalcSum60();
// PrintSum60();
// printf("GetSetCount = %d\n", GetSetCount(Sum60, N, 13));
CalcSets(Sum60, N, 13);
}

void ReadRecordAndCalcResult()
{
InitMasks();
CalcSum60();
CheckSetFile();
CalcAllSet();
}

int main(int argc, char* argv[])
{
// CalcRecordAndWriteToFile();
ReadRecordAndCalcResult();
return 0;
}

#4

To spirit_sheng(老盛) 

非常谢谢!
在你的算法中，我在我的机子上把第三步和第二步了一下交换一下,因为组合数太多,加了一些极限条件,比如斜向三个数相加也是60,即X1+Y2+N3=60....
这样下来,还是耗时间太多,

这几天在看幻方的算法,不知道能不能解决这个问题,关键是效率;

非常感谢,如果还有更好的算法思路,十分感激提供!!

#5

>> 在你的算法中，我在我的机子上把第三步和第二步了一下交换一下
不懂, 请解释

#6

我的意思是说
先求条件二的组合数,
即每组对应的位相加的和相等为60,即X1+Y1+N1=60;X2+Y2+N2=60;.....X13+Y13+N13=60;
这样的三元组合数

#7

/*
有1到39的自然数,分3组(各不相同),每组13个自然数,如下:
x1,x2,.......x12,x13;
Y1,Y2,.......Y12,Y13;
N1,N2,.......N12,N13;
条件一:让每组各数和为260,即x1+x2+.......+x11+x12+X13=260;其他两组同;
条件二:每组对应的位相加的和相等为60,即X1+Y1+N1=60;X2+Y2+N2=60;.....X13+Y13+N13=60;
输出满足上述条件的组合X,Y,N;
*/

#include <iostream>
#include <set>
#include <cstdlib>
#include <algorithm>
#include <cassert>
#include <windows.h>
using namespace std;
//////////////////////////////////////////////////////////////////////////
//计时器，用于计算代码执行花费的时间
//使用了windows系统函数(仅此一处涉及操作系统)
class MyTimer
{
public:
MyTimer(){reset();}
DWORD end(){return GetTickCount() - count;}
void reset(){count=GetTickCount();}
private:
DWORD count;
};

//////////////////////////////////////////////////////////////////////////
struct TupleType         //记录一列共3个数据
{ 
int d[3];
};
//为STL容器比较元素准备的
inline bool operator<(TupleType a,TupleType b)
{
return a.d[0]==b.d[0]?
a.d[1]==b.d[1]?a.d[2]<b.d[2]:a.d[1]<b.d[1]
:a.d[0]<b.d[0];
}
inline bool operator==(TupleType a, TupleType b)
{
return a.d[0]==b.d[0]&&a.d[1]==b.d[1]&&a.d[2]==b.d[2];
}
//////////////////////////////////////////////////////////////////////////
//输出数组N
void output(int N[3][13])
{
ostream& out = cout;

for(int i=0; i<3;i++)
{
for(int j=0; j<13;j++)
{
out.width(2);
out<<N[i][j]<<' ';
}
out<<endl;
}
out<<endl;
return;
}

//////////////////////////////////////////////////////////////////////////
//功能：调整N中的一列，使得行的和更接近目标260
//输入：N中所有元素为1－39的一个排列，并且每个列满足和为60的条件
//  ：sum为N的每行之和
//      这个条件由调用函数负责维护
//输出：返回值为真，表示调整了列，假表示未调整
bool adjust(int N[3][13],int sum[3])
{

int idx;
//随机选择一列，可以使用更好的策略
idx = 1.0*rand()/RAND_MAX*11+1;
assert(idx>0 && idx<13); //第0列不用移动，只移动1～12列

//备份列，用于最后修正求和结果
int c[3];
c[0] = N[0][idx];c[1] = N[1][idx];c[2] = N[2][idx];

//排序，使列的顺序与和的顺序相反
while(1)
{
if((sum[0]-sum[1])*(N[0][idx]-N[1][idx])>0)
swap(N[0][idx],N[1][idx]);
else if((sum[1]-sum[2])*(N[1][idx]-N[2][idx])>0)
swap(N[1][idx],N[2][idx]);
else if((sum[0]-sum[2])*(N[0][idx]-N[2][idx])>0)
swap(N[0][idx],N[2][idx]);
else
break;
}

//修正求和的结果sum
sum[0]=sum[0]+N[0][idx]-c[0];
sum[1]=sum[1]+N[1][idx]-c[1];
sum[2]=sum[2]+N[2][idx]-c[2];
return true;
}
//////////////////////////////////////////////////////////////////////////
//功能: 求出N的一个解，
//输入: 数组N，要求N的每一列之和为60，且N的所有元素互不相等，均属于集合1..39
// 这个条件由调用函数负责维护
//输出: 真, 则表示N中的排列已经满足约束条件
//      假, 表示在尝试了一定次数后，未发现可行解

bool find (int N[3][13])
{
int sum[3]={0,0,0};
for(int i=0; i<13;i++)
{
sum[0]+=N[0][i];
sum[1]+=N[1][i];
sum[2]+=N[2][i];
}
//反复调整N中的数字排列，寻找满足方程的解
const int MAX_COUNT = 100; //最大尝试次数,100的效果不错！
for( i=0; (sum[0]!=260 || sum[1] != 260 || sum[2] != 260) && i<MAX_COUNT; i++)
{
//output(N);
//随机选取N中的一列，调整其数字，使得更接近结果
if(!adjust(N,sum))
{
break;//如果没有可以调整的列，那么放弃处理
}
//output(N);
}
return (sum[0]==260 && sum[1] == 260 && sum[2] == 260);
}

/////////////////////////////////////////////////////////////////////////////////////////////
int flag[40]={0}; //用于记录数字是否被选中
//判断一个3元组中的数字是否与先前所选有重复，如果无重复表示可选，返回真，否则返回假
bool can_select(TupleType& tuple)
{
return(flag[tuple.d[0]]==0 &&flag[tuple.d[1]]==0 && flag[tuple.d[2]]==0);
}
//修改flag,标记当前三元组已经被选中
void select(TupleType& tuple)
{
assert(can_select(tuple));
flag[tuple.d[0]]=1 ;flag[tuple.d[1]]=1; flag[tuple.d[2]]=1;
}
//从flag数组中去除3元组的标记。要求前提是改三元组确实被选中过
void unselect(TupleType& tuple)
{
assert(flag[tuple.d[0]]==1 &&flag[tuple.d[1]]==1&&flag[tuple.d[2]]==1);
flag[tuple.d[0]]=0;flag[tuple.d[1]]=0;flag[tuple.d[2]]=0;
}

/////////////////////////////////////////////////////////////////////////////////////////////
//将possible_answer转换为整型数组的形式，再使用函数find寻找解
int find_answer(set<TupleType >& possible_answer)
{
static int cnt =0;
static MyTimer mytimer;
cnt++;
if(cnt%1000==0)
{
cout<<cnt<<"..\t";
cout<<mytimer.end()<<"毫秒"<<endl;
mytimer.reset();
}

int N[3][13];
int i=0;
for(set<TupleType >::iterator it=possible_answer.begin(); it!=possible_answer.end();it++)
{
for(int j=0; j<3;j++)
N[j][i]=(*it).d[j];
i++;
}
if(find(N))
{
output(N);
return true;
}
else
return false;
}
/////////////////////////////////////////////////////////////////////////////////////////////
//穷举所有可能的13个3元组的组合，找出所有这样的组合：所有元组使用的数字互不相同，并且属于集合1..39
//输入： tuples由候选3元组组成的集合，possible_answer 一个由选出的3元组组成的集合
//当possible_answer长度为13时，就使用find函数寻找答案
//输出：
int enum_all_tuples(set<TupleType >& tuples, set<TupleType >& possible_answer)
{
int cnt = 0; //记录数字互不相同的13个3元组的组合的数目
if(possible_answer.size()==13)
{
find_answer(possible_answer);
return 1;
}
else if(tuples.size()+possible_answer.size()<13)
return 0;

//复制集合，仅仅是防止在删除元素后，集合元素顺序改变导致遍历失效
set<TupleType> new_set = tuples;
set<TupleType> backup_set;
//递规求解
for(set<TupleType>::iterator it = tuples.begin(); it!=tuples.end(); it++)
{
//将当前元组从候选集合中删除并插入到possible_answer中
new_set.erase(*it);

if(can_select(*it))
{
//前向检验,清除候选集合new_set中所有与possible_answer中的元组冲突的元组
//并且将其备份到backup_set
backup_set.clear();

for(set<TupleType>::iterator it1 = new_set.begin(); it1!=new_set.end();)
{
if(!can_select(*it1))
{
backup_set.insert(*it1);
new_set.erase(*it1++);
}
else
{
it1++;
}
}

//递规求解
select(*it);
possible_answer.insert((*it));
cnt+=enum_all_tuples(new_set,possible_answer);

//试探过元组(*it)后，将其从possible_answer删除，准备试用其它元组
possible_answer.erase((*it));
unselect(*it);
//将前向检验删除的元素从backup_set恢复到new_set中
for(set<TupleType>::iterator it2 = backup_set.begin(); it2!=backup_set.end();it2++)
{
new_set.insert(*it2);
}
//这里不恢复(*it)到new_set，原因是需要组合，而不是排列
//这样做避免出现同一组合试探多次的情况
}

}
return cnt;
}

void solve()
{
int i,j;
set<TupleType >  nums;//记录x+y+z＝60的元组（x,y,z）
set<TupleType >  possible_answer;
for(i=1; i<=39; i++)
{
for(j=i+1; j<=39; j++)
{
for(int k=j+1;k<=39; k++)
if(i+j+k==60)
{
TupleType temp;
temp.d[0]=i;
temp.d[1]=j;
temp.d[2]=k;
nums.insert(temp);
}
}
}
cout<<"满足x+y+z=60的所有组合数目为"<<nums.size()<<endl;

//穷举所有可能的可能组合，并检验之
int count = enum_all_tuples(nums, possible_answer);
cout<<"数字互不相同的13个3元组的组合数目为\t"<<count<<endl;
}

int main()
{
MyTimer mytimer;
solve();
cout<<"共耗时 "<<mytimer.end()<<"毫秒"<<endl;
return 0;
}

#8

上面的代码是对每列满足和为60的情况，通过调整列中元素的位置，来寻找解。
使用了启发式方法（adjust函数），无法穷举所有的解。

思路就是给定一种每列满足和为60情况后，随机选取一列，调整其中元素的位置使得他们的顺序关系与行的和的顺序关系相反。
例如
39， 2 38  4 28  6 31 36 26 10 34 30 14  和为298
20，23 19 24 27 21 22 16 25 13 15 18 17  和为260
1 ，35  3 32  5 33  7  8  9 37 11 12 29  和为222
针对第一列，调整39 20 1 的顺序，使得列中最大元素移到和为最小的行，就是将39移到222对应的那一行。最小元素移到和为最大的行

穷举所有组合的算法效率太差，比老盛的慢十倍以上

#9

回楼上, 如果"给定一种每列满足和为60情况后", 只计算一种情况, 而不计算所有组合的时候, 则我的方法对于每个记录只需1毫秒还不到, 则整个第三部只需要十几分钟就可以完成

#10

Record Count: 703722, Error Count: 0

RecNo: 1024, Time: 881 ms, Count: 1024
RecNo: 2048, Time: 1772 ms, Count: 2048
RecNo: 3072, Time: 2593 ms, Count: 3072
RecNo: 4096, Time: 3455 ms, Count: 4096
RecNo: 5120, Time: 4306 ms, Count: 5120
RecNo: 6144, Time: 5247 ms, Count: 6144
RecNo: 7168, Time: 6158 ms, Count: 7168
RecNo: 8192, Time: 7020 ms, Count: 8192
RecNo: 9216, Time: 7841 ms, Count: 9216
RecNo: 10240, Time: 8712 ms, Count: 10240
RecNo: 11264, Time: 9583 ms, Count: 11264
RecNo: 12288, Time: 10495 ms, Count: 12288
RecNo: 13312, Time: 11416 ms, Count: 13312
RecNo: 14336, Time: 12317 ms, Count: 14336
RecNo: 15360, Time: 13169 ms, Count: 15360
RecNo: 16384, Time: 14000 ms, Count: 16384
RecNo: 17408, Time: 14801 ms, Count: 17408
RecNo: 18432, Time: 15652 ms, Count: 18432
RecNo: 19456, Time: 16503 ms, Count: 19456
RecNo: 20480, Time: 17395 ms, Count: 20480
RecNo: 21504, Time: 18226 ms, Count: 21504
RecNo: 22528, Time: 19087 ms, Count: 22528
RecNo: 23552, Time: 19908 ms, Count: 23552
RecNo: 24576, Time: 20779 ms, Count: 24576
RecNo: 25600, Time: 21611 ms, Count: 25600
RecNo: 26624, Time: 22442 ms, Count: 26624
RecNo: 27648, Time: 23283 ms, Count: 27648
RecNo: 28672, Time: 24114 ms, Count: 28672
RecNo: 29696, Time: 24945 ms, Count: 29696
RecNo: 30720, Time: 25777 ms, Count: 30720
RecNo: 31744, Time: 26628 ms, Count: 31744
RecNo: 32768, Time: 27449 ms, Count: 32768
RecNo: 33792, Time: 28280 ms, Count: 33792
RecNo: 34816, Time: 29132 ms, Count: 34816
RecNo: 35840, Time: 30033 ms, Count: 35840
RecNo: 36864, Time: 30884 ms, Count: 36864
RecNo: 37888, Time: 31725 ms, Count: 37888
RecNo: 38912, Time: 32546 ms, Count: 38912
RecNo: 39936, Time: 33368 ms, Count: 39936
RecNo: 40960, Time: 34219 ms, Count: 40960
RecNo: 41984, Time: 35050 ms, Count: 41984
RecNo: 43008, Time: 35881 ms, Count: 43008
RecNo: 44032, Time: 36712 ms, Count: 44032
RecNo: 45056, Time: 37574 ms, Count: 45056
RecNo: 46080, Time: 38405 ms, Count: 46080
RecNo: 47104, Time: 39246 ms, Count: 47104
RecNo: 48128, Time: 40067 ms, Count: 48128
RecNo: 49152, Time: 40888 ms, Count: 49152
RecNo: 50176, Time: 41750 ms, Count: 50176
RecNo: 51200, Time: 42621 ms, Count: 51200
RecNo: 52224, Time: 43512 ms, Count: 52224
RecNo: 53248, Time: 44373 ms, Count: 53248
RecNo: 54272, Time: 45265 ms, Count: 54272
RecNo: 55296, Time: 46126 ms, Count: 55296
RecNo: 56320, Time: 46967 ms, Count: 56320
RecNo: 57344, Time: 47838 ms, Count: 57344
RecNo: 58368, Time: 48630 ms, Count: 58368
RecNo: 59392, Time: 49561 ms, Count: 59392
RecNo: 60416, Time: 50442 ms, Count: 60416
RecNo: 61440, Time: 51293 ms, Count: 61440
RecNo: 62464, Time: 52095 ms, Count: 62464
RecNo: 63488, Time: 52946 ms, Count: 63488
RecNo: 64512, Time: 53857 ms, Count: 64512
RecNo: 65536, Time: 54818 ms, Count: 65536
RecNo: 66560, Time: 55660 ms, Count: 66560
RecNo: 67584, Time: 56501 ms, Count: 67584
RecNo: 68608, Time: 57342 ms, Count: 68608
RecNo: 69632, Time: 58193 ms, Count: 69632
RecNo: 70656, Time: 59085 ms, Count: 70656
RecNo: 71680, Time: 59996 ms, Count: 71680
RecNo: 72704, Time: 60877 ms, Count: 72704

#11

用启发式方法（adjust函数），可能得不到解,或者说是针对这个问题存在缺陷

我个人感觉该方法对本问题不适用,谢谢你，辛苦你了!
也谢谢老盛!

#12

to 老盛：
还是你的程序牛，佩服

顺便问一下，对每列已经满足和为60的情况下，是否一定存在解？

#13

to 楼上
RecNo: 703722, Time: 337235 ms, Count: 703690
可以看出, 不一定存在解, 其中存在的有 703690 种, 不存在有 32 种
这次用的是Release版本, 所以快很多, 总时间6分钟不到
另: 你的启方式方法很有新意, 我又学到了一招. 至于性能, 与实现的关系很大的, 其实你的程序性能在实现上可以改善很多

#14

MARK

#15

to 老盛
能说说你的经验，介绍一下如何入手，才能学会写性能好的程序吗？
很想学习一下

我用启发式方法就是因为写不出性能这么好的程序:-)

#16

最后一步我可以找到改进的算法,在我的计算机上估计4.9小时内能够完成.
unsigned char DC[N][3];
void CalcSum60()
{
int iRes=0;
for (int i=0; i<39; i++)
for (int j=i+1; j<39; j++)
{
int x = 60 - 3 - i - j;
if ((x>j) && (x<39))
{
Sum60[iRes] = (1LL<<i) | (1LL<<j) | (1LL<<x);
DC[iRes][0]=i+1;DC[iRes][1]=j+1;DC[iRes][2]=x+1;
iRes ++;
}
}
}


int the_sum[13][3];
int order_list[6][3]={
    {0,1,2},
    {0,2,1},
    {1,0,2},
    {1,2,0},
    {2,0,1},
    {2,1,0}
};
unsigned short hit[1<<24];

void verify_sum(int a[13][3], int start){
    if(start<7){
        int i;
        for(i=0;i<6;i++){
                int k;
            for(k=0;k<3;k++){
                    the_sum[start][k]=the_sum[start-1][k]+a[start][order_list[i][k]];
            }
            verify_sum(a,start+1);
        }
    }else{
int s1=260-the_sum[6][0],s2=260-the_sum[6][1],s3=260-the_sum[6][2];
int index=s1|(s2<<8)|(s3<<16);
iMatchCount+=hit[index];
    }
}

void accumulate(int a[13][3], int start){
    if(start<13){
int i;
for(i=0;i<6;i++){
    int k;
    for(k=0;k<3;k++){
the_sum[start][k]=the_sum[start-1][k]+a[start][order_list[i][k]];
    }
    accumulate(a,start+1);
}
    }else{
int index=the_sum[12][0]|(the_sum[12][1]<<8)|(the_sum[12][2]<<16);
hit[index]++;
if(hit[index]==0){
    fprintf(stderr,"Overflow\n");
    exit(-1);
}
    }
}
void CalcOneSet(unsigned char * p, int iRecNo)
{
int a[13][3];
int i;
for (i=0; i<13; i++)
{
int iPos = 0;
__int64 x = Sum60[p[i]];
a[i][0]=DC[p[i]][0];
a[i][1]=DC[p[i]][1];
a[i][2]=DC[p[i]][2];
}
memset(hit,0,sizeof(hit));
the_sum[6][0]=the_sum[6][1]=the_sum[6][2]=0;
accumulate(a,7);
the_sum[0][0]=a[0][0];
the_sum[0][1]=a[0][1];
the_sum[0][2]=a[0][2];
verify_sum(a,1);
}

程序是在spirit_sheng(老盛)基础上修改的.前面一些数据的结果是:
Record Count: 703722, Error Count: 0

RecNo:      1, Time: 80000/80000 ms, Count: 220568/220568
RecNo:      2, Time: 20000/100000 ms, Count: 221403/441971
RecNo:      3, Time: 30000/130000 ms, Count: 221737/663708
RecNo:      4, Time: 20000/150000 ms, Count: 215003/878711
RecNo:      5, Time: 30000/180000 ms, Count: 219477/1098188
RecNo:      6, Time: 20000/200000 ms, Count: 223962/1322150
RecNo:      7, Time: 30000/230000 ms, Count: 227101/1549251
RecNo:      8, Time: 20000/250000 ms, Count: 226082/1775333
RecNo:      9, Time: 30000/280000 ms, Count: 227152/2002485
RecNo:     10, Time: 20000/300000 ms, Count: 230511/2232996
RecNo:     11, Time: 30000/330000 ms, Count: 239601/2472597
RecNo:     12, Time: 20000/350000 ms, Count: 226919/2699516

RecNo:    100, Time: 30000/2510000 ms, Count: 250419/23920729

RecNo:  10000, Time: 20000/249140000 ms, Count: 228311/2327153975

#17

20000也出来了,为:
RecNo:  20000, Time: 30000/498480000 ms, Count: 243541/4644063997
还有,我输出的时间单位为微秒,不是毫秒,程序中忘了修改了(我用的操作系统是Linux)

#18

先留个记号

#19

发现hit[1<<24]可以改为hit[1<<16]
int s1=260-the_sum[6][0],s2=260-the_sum[6][1],s3=260-the_sum[6][2];
int index=s1|(s2<<8)|(s3<<16);
中，s3部分可以不放进去。
这样，由于大量节省内存访问，速度可以提高10倍左右

#20

比如:
RecNo: 100000, Time: 0/246650000 ms, Count: 230467/23197929956

#21

代码的变化:
unsigned short hit[1<<16];

void verify_sum(int a[13][3], int start){
    if(start<7){
        int i;
        for(i=0;i<6;i++){
                int k;
            for(k=0;k<3;k++){
                    the_sum[start][k]=the_sum[start-1][k]+a[start][order_list[i][k]];
            }
            verify_sum(a,start+1);
        }
    }else{
int s1=260-the_sum[6][0],s2=260-the_sum[6][1],s3=260-the_sum[6][2];
int index=s1|(s2<<8);
iMatchCount+=hit[index];
    }
}

void accumulate(int a[13][3], int start){
    if(start<13){
int i;
for(i=0;i<6;i++){
    int k;
    for(k=0;k<3;k++){
the_sum[start][k]=the_sum[start-1][k]+a[start][order_list[i][k]];
    }
    accumulate(a,start+1);
}
    }else{
int index=the_sum[12][0]|(the_sum[12][1]<<8);
hit[index]++;
if(hit[index]==0){
    fprintf(stderr,"Overflow\n");
    exit(-1);
}
    }
}

#22

RecNo: 200000, Time: 0/504830000 ms, Count: 228616/46379319352
估计半小时有结果

#23

一半时的数据：
RecNo: 351861, Time: 10000/900020000 ms, Count: 230113/81651581066

#24

RecNo: 703722, Time: 0/1820330000 ms, Count: 191901/163247714969
Match count 38957721

#25

mathe()牛的

to 39457760(人间一日，网上一年◎分要多多的给，贴要慢慢的结)
mathe()可是大牛, 你可以多多请教mathe()

#26

另, 对于增加斜线三个数字等于60的限制时
如果一个方向十三条斜线都进行限制的话, 没有满足要求的数据

增加斜线的限制, 则方法与上面的完全不同
可以利用以下点, 如定下前两列的数据后, 则第三列有一个数据是确定的, 如
X1 Y2已经确定, 则Z3 = 60 - X1 - Y2

#27

To mathe()

能把你的全部源代码发过来看看好吗?
我用的BCB,怎么不对呢?
我的邮箱是[e-mail]
谢谢!

#28

我的代码是在Linux上面运行的,同你的不同:)
你同样需要做一些修改的

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
typedef clock_t DWORD;
const int N=181;
__int64 Sum60[N];
unsigned char DC[N][3];
int max_sum[13];
int min_sum[13];
#define GetTickCount() clock()

int GetSum60Count()
{
int iRes=0;
for (int i=0; i<39; i++)
for (int j=i+1; j<39; j++)
{
int x = 60 - 3 - i - j;
if ((x>j) && (x<39))
iRes ++;
}
return iRes;
// The Result is 181
}


void CalcSum60()
{
int iRes=0;
for (int i=0; i<39; i++)
for (int j=i+1; j<39; j++)
{
int x = 60 - 3 - i - j;
if ((x>j) && (x<39))
{
Sum60[iRes] = (1LL<<i) | (1LL<<j) | (1LL<<x);
DC[iRes][0]=i+1;DC[iRes][1]=j+1;DC[iRes][2]=x+1;
iRes ++;
}
}
}

void PrintSum60()
{
for (int i=0; i<N; i++)
printf("%3d is %010I64X\n", i, Sum60[i]);
}

int GetSetCount(__int64 s[], int SN, int M)
{
if (M<0) return 0;
if (M==0) return 1;
if (SN<=0) return 0;

int iCount=0;
__int64 a[14];
int indexes[14];
indexes[0] = -1;
a[0] = 0;
int level=1;
int nextIndex = 0;
while (true)
{
__int64 x = a[level-1];
while ((nextIndex < SN) && (x & s[nextIndex]))
nextIndex ++;
if (nextIndex < SN)
{
if (level == M)
{
iCount ++;
nextIndex ++;
}
else
{
a[level] = x | s[nextIndex];
indexes[level] = nextIndex;
level ++;
nextIndex ++;
}
}
else
{
// 退一级
level--;
nextIndex = indexes[level] + 1;
if (!level) break;
// if (level == 2)
//   printf("i1: %d, i2: %d, count: %d\n", indexes[1], indexes[2], iCount);
}

}

return iCount;
// 703722 种 // 703722 种, 计算用时 19分左右
}

const char * DATA_FILE_NAME = "M39.DAT";

#define BUFF_SIZE 1024
void CalcSets(__int64 s[], int SN, int M)
{
if (SN <= 0) return;
if (M != 13) return;

unsigned char IndexBuff[BUFF_SIZE][13];
FILE * fFile = fopen(DATA_FILE_NAME, "wb");

int iCount=0;
int iTotalCount=0;
__int64 a[14];
int indexes[14];
indexes[0] = -1;
a[0] = 0;
int level=1;
int nextIndex = 0;
while (true)
{
__int64 x = a[level-1];
while ((nextIndex < SN) && (x & s[nextIndex]))
nextIndex ++;
if (nextIndex < SN)
{
if (level == M)
{
indexes[level] = nextIndex;
for (int i=0; i<13; i++)
IndexBuff[iCount][i] = indexes[i+1];
iCount ++;
iTotalCount ++;
nextIndex ++;
if (iCount == BUFF_SIZE)
{
fwrite(IndexBuff, 13, iCount, fFile);
iCount = 0;
}
}
else
{
a[level] = x | s[nextIndex];
indexes[level] = nextIndex;
level ++;
nextIndex ++;
}
}
else
{
// 退一级
level--;
nextIndex = indexes[level] + 1;
if (!level) break;
//if ((level== 2) && (a[1] & 1 == 0)) break;
if (level == 2)
   printf("i1: %d, i2: %d, count: %d\n", indexes[1], indexes[2], iTotalCount);
}

}
if (iCount>0)
{
fwrite(IndexBuff, 13, iCount, fFile);
iCount = 0;
}
fclose(fFile);

printf("Write finished\n");

// 703722 种 // 703722 种, 计算用时 19分左右
}


void CheckSetFile()
{
FILE * fFile = fopen(DATA_FILE_NAME, "rb");
int iTotalCount = 0;
int iErrorCount = 0;
unsigned char IndexBuff[BUFF_SIZE][13];
while (true)
{
int iRes = fread(IndexBuff, 13, BUFF_SIZE, fFile);
if (iRes > 0) 
{
iTotalCount += iRes;
for (int i=0; i<iRes; i++)
{
__int64 x=0;
for (int j=0; j<13; j++)
x |= Sum60[IndexBuff[i][j]];
if (x != 0x7FFFFFFFFFLL)
iErrorCount ++;
}
}
if (iRes < BUFF_SIZE) break;
}

fclose(fFile);

printf("Record Count: %d, Error Count: %d\n\n", iTotalCount, iErrorCount);
}

// char Buff[]

__int64 iMatchCount;
int the_sum[13][3];
int order_list[6][3]={
    {0,1,2},
    {0,2,1},
    {1,0,2},
    {1,2,0},
    {2,0,1},
    {2,1,0}
};
unsigned short hit[1<<16];

void verify_sum(int a[13][3], int start){
    if(start<7){
        int i;
        for(i=0;i<6;i++){
                int k;
            for(k=0;k<3;k++){
                    the_sum[start][k]=the_sum[start-1][k]+a[start][order_list[i][k]];
            }
            verify_sum(a,start+1);
        }
    }else{
int s1=260-the_sum[6][0],s2=260-the_sum[6][1],s3=260-the_sum[6][2];
int index=s1|(s2<<8);
iMatchCount+=hit[index];
    }
}

void accumulate(int a[13][3], int start){
    if(start<13){
int i;
for(i=0;i<6;i++){
    int k;
    for(k=0;k<3;k++){
the_sum[start][k]=the_sum[start-1][k]+a[start][order_list[i][k]];
    }
    accumulate(a,start+1);
}
    }else{
int index=the_sum[12][0]|(the_sum[12][1]<<8);
hit[index]++;
if(hit[index]==0){
    fprintf(stderr,"Overflow\n");
    exit(-1);
}
    }
}

void CalcOneSet(unsigned char * p, int iRecNo)
{
int a[13][3];
int i;
for (i=0; i<13; i++)
{
int iPos = 0;
__int64 x = Sum60[p[i]];
a[i][0]=DC[p[i]][0];
a[i][1]=DC[p[i]][1];
a[i][2]=DC[p[i]][2];
}
memset(hit,0,sizeof(hit));
the_sum[6][0]=the_sum[6][1]=the_sum[6][2]=0;
accumulate(a,7);
the_sum[0][0]=a[0][0];
the_sum[0][1]=a[0][1];
the_sum[0][2]=a[0][2];
verify_sum(a,1);
/*
the_sum[0][0]=a[0][0];
the_sum[0][1]=a[0][1];
the_sum[0][2]=a[0][2];
accumulate(a,1);
*/
}

#undef BUFF_SIZE
#define BUFF_SIZE 16
void CalcAllSet()
{
FILE * fFile = fopen(DATA_FILE_NAME, "rb");
int iRecNo = 0;
unsigned char IndexBuff[BUFF_SIZE][13];
iMatchCount = 0;
DWORD dwStartTick = ::GetTickCount();
DWORD dwLastTick = dwStartTick;
while (true)
{
int iRes = fread(IndexBuff, 13, BUFF_SIZE, fFile);
if (iRes > 0) 
{
for (int i=0; i<iRes; i++)
{
iRecNo++;
__int64 lastCount = iMatchCount;
CalcOneSet(IndexBuff[i], iRecNo);
DWORD dwCurTick = ::GetTickCount();
DWORD dwThis = dwCurTick - dwLastTick;
DWORD dwTotal = dwCurTick - dwStartTick;
dwLastTick = dwCurTick;
__int64 thisCount = iMatchCount - lastCount;
    printf("RecNo: %6d, Time: %u/%u ms, Count: %lld/%lld\n", 
iRecNo, dwThis, dwTotal, thisCount, iMatchCount);
}
}
if (iRes < BUFF_SIZE) break;
}

fclose(fFile);

printf("Match count %d\n", iMatchCount);

}

void init_min_max(){
  int i;
  min_sum[0]=0;
  max_sum[0]=0;
  for(i=1;i<13;i++){
    min_sum[i]=min_sum[i-1]+i;
    max_sum[i]=max_sum[i-1]+40-i;    
  }
}

void CalcRecordAndWriteToFile()
{
// printf("GetSum60Count=%d\n", GetSum60Count());
CalcSum60();
// PrintSum60();
// printf("GetSetCount = %d\n", GetSetCount(Sum60, N, 13));
CalcSets(Sum60, N, 13);
}

void ReadRecordAndCalcResult()
{
CalcSum60();
CheckSetFile();
CalcAllSet();
}

int main(int argc, char* argv[])
{
  init_min_max();
// CalcRecordAndWriteToFile();
  ReadRecordAndCalcResult();
return 0;
}

#29

回复人：spirit_sheng(老盛) ( 三级(初级)) 信誉：100  2006-11-15 20:33:29  得分:0

mathe()牛的

to 39457760(人间一日，网上一年◎分要多多的给，贴要慢慢的结)
mathe()可是大牛, 你可以多多请教mathe()

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
你们都是牛人！！！

#30

进来纯粹是为了学习！！！
向各位牛人致敬

#31

mathe()的代码的功能是计算组合数
我的代码的主要功能是计算出所有情况

但计算组合数mathe()的分治法牛的

#32

mark,study...

#33

我算了大约18个小时
得到了大概 8.4M 个结果
硬盘已经不够了

#34

原来这个题目是要求输出所有结果.不过这个要求不大现实.
根据计算结果,这个题目总共需要输出13!*3!*163247714969=6.1*10^21个结果,
如果每个结果需要10个字节来保存(简单压缩一下),那么总共需要6.1*10^22个字节的硬盘空间.
估计将全球的所有PC都用上还是不够.

如果我们将系数13!*3!去掉(也就是那些通过行列交换可以相互转化的都认为是相同的),还是有163G个结果,需要大概1.6T的硬盘空间,现在一般的PC机都是承受不了的.

#35

每个结果10个字节恐怕很难做到
39 = 10 0111  ( 3/4 B )
39 * 39  = 30 B

#36

这个看你怎么来编码了.
比如使用老盛的方案,我们首先知道所有结果可以分成703722类,
那么对于类别,只要使用20bits就可以编码了.
对于每个类别内部,我们只需要知道后面12个三元组是如何安排的就可以了,总共有6^12<2^32种.
所以如果用这种方法编码,我们对于每个结果,只需要52bits就可以了,不超过7个字节.
只是在这之前,我们需要预先保存703722个类使用的13个三元组分别是什么(只是无序的),但是这部分空间开销相对于后面的编码空间,可以忽略不计.
如果我们还需要加上13!*3!的编码,那么可能就会略微超过10个字节,但是总体上,差不多10个字节左右就可以表示一个结果了.

#37

的确,这样省些
不过
13!*3!?
我怎么觉得应该是(3!)^12

#38

(3!)^12前面我已经提到了,也就是6^12<2^32

#39

每个记录都保存类别有些浪费, 可以先保存类别, 然后保存所有情况, 
这样, 每个记录用4个字节就可以了, 在加上每个类别8个字节(类别4字节, 类别结束标识4字节)
其光记录空间就需要
163247714969 * 4 Bytes = 608.14 GB 空间
也就是说至少需要 

其他部分 每个类别13+8=21字节(我的文件每个类别需要13字节)
则 703722 * 21 Bytes = 14.09 MB 
所以, 按此种方法, 需要608.16 GB 空间

楼主的硬盘不知有没有这么大

#40

楼主的硬盘不知有没有这么大
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
呵呵，这么大的硬盘保存这些数据实在是暴殄天物啊

#41

其实现在的代码已经可以用来写一个程序来快速浏览所有的数据。
我们可以事先计算出703722个类中每个类中数据的数目。
然后在这个程序中，对于每个给定的系数x,1<=x<=163247714969,程序可以快速确定所在的分类，以及在类内部的索引值。
然后对于给定的类内部，分别调用类似上面accumulate和verify_sum这样的函数，记录下所有的数据，同上面程序的区别是这里还需要记录下每个局面。然后将这些数据根据hit的值进行快速排序。而这部分代码由于数据不大，可以非常迅速计算。最后我们就可以通过这种方法快速产生对于给定的系数x,显示出第x个结果的局面。这样，只需要通过保存少量的数据以及一个程序，就可以任意的浏览所有的数据。

#42

我还要做一些计算,计算斜向三数和也要等60,
即
X1+Y2+N3=60....
X3+Y2+N1=60....
这样的对称斜向三数和相等,但是这样以来,就有个漫长的过程了,
不过结果就没那么多了,
不知道大侠有没有高效的代码?

#43

要求哪些斜向三数和都是60呢? 不过的确题目要复杂很多了,最主要原先对13列的排列没有任何要求,现在是对它们的排列顺序也有要求了.

#44

有了这样的约束条件，计算应该会更快一些

#45

我已经算过了, 没有满足要求的结果, 其实这样就几秒就能算出结果,
算法思想是选定第一列及第二列, 后面的列就可以直接计算

X3 = 60 - Z1 - Y2
Z3 = 60 - X1 - Y2
Y3 = 60 - X3 - Y3

所以, 一共的情况是 (181 * 3!) * (180 * 3!) 种

#46

MARK

#47

其实这个问题题设还隐藏了一些可以大量减少运算的优化可能，比如，根据情况，其实只需要判断XY两组的和是否为260，不需要在计算N组了。同样，对排列中依次计算也可以少算一组，此外还可以加快计算，就是某两个和小于21就表示排列错误了，这些都是在算法中就要先考虑到的。

#48

to: xdspower() ( ) 信誉：130    Blog 
我看了一个你的说明, 你说的可以优化的地方有以下三种:

1. 根据情况，其实只需要判断XY两组的和是否为260，不需要在计算N组了
答: 你仔细看我和mathe()的程序, 对于行的和为260的情况, 我和mathe()都只计算了第一行和第二行( mathe() 一开始计算了三行, 但后来的程序改过来了 hit[1<<24] 变为了 hit[1<<16])

2. 同样，对排列中依次计算也可以少算一组
答: 你仔细看我的mathe()的程序, 我们的计算方法都认为第一列是固定, 实际上只算了12列, 你说可以少算一组, 不会说只用计算11列吧

3. 就是某两个和小于21就表示排列错误了
答: 如果是对于3个数的和为60的情况, 其实第一步就已经实现了, 如果对于13个数和为260的情况, 则好象这个不成立吧.

当然, 我们的程序是有可以优化的地方, 但你好象没好好理解我们的程序哟.
比如, 第二步, 实际上优化的空间很大, 如果按照我的方法, 
则第一列只用考虑包括数字1的所有三元组, 则由 181种减为 10种
第二列只用考虑包括数字2的所有三元组,
第三列只用考虑包括数字3的所有三元组
...
第十列只用考虑包括数字10的所有三元组
这样, 性能大约会提高80%左右
但由于大头是第三步, 而优化第二步编程需要一些时间, 而且意义不大, 所以就没有进行此优化

#49

任何一个符合条件的排列经过行列交换后都可以变成:
1.第一行的第一个元素为1, 
2.第一行按升序排列;
3.第一列按升序排列;

符合1,2条件与和为260的条件,即第一行的排列大约有3千万个;
符合1,3条件与和为60的条件,即第一列的排列只有10个;

我写了一个简单的程序,直接先求出第一行与第一列后,再求其他的24个元素;
每秒大约能判断第一列的10多个组合,总共大约需要20多天的时间;

感觉先求出和为60的三元组并没有什么优势;

#50

哦，这样啊，不现在编程和读程序很少了，主要是看算法描述，谢谢指正。