拿到这个题目，第一感觉就是一道acm简单题，于是用dfs算法+多重剪枝直接切掉。由于只加了几个简单的优化剪枝条件，没有针对幻方的特点进行专门的优化，因此运行时间有点长。
当然，这个算法的效率没法和网上那些专门针对幻方的算法相比，这只是一个经过优化的暴力搜索，但是相比那些幻方算法，我这也算是一个原创了，哈哈。
在这里就把算法思路和代码贴上，与大家分享！算法比较简单，熟悉图搜索算法的一看就明白，只是几处剪枝的地方详细的说明了一下！
算法思路：
由于是将1~16这16个数填入幻方，所以可以算出每行、每列以及对角线之和一定为34（如果这都不知道，那我就吐了！呵呵）,因此开设数组res，4行+4列+2对角线，正好是10个，res数组记录的是代表的行、列或对角线在当前状态的时候（0~3表示行，4~7表示列，8、9表示对角线），还剩下的值，res数组的初始值均为34，如果剩下的值正好为零，则说明这一行、列或者对角线填入的值之和为34。
整型变量num，代表已经填入幻方的数字个数，初始值为0，当num==16时，表明幻方已经填满，若结果满足条件，就直接输出结果。
数字填入幻方的顺序是依次填入，即从1到16号，所以是将幻方一行一行的填满。每填满一行时，就会检查一下这一行和之前填满的行的和是否为34，如果符合，则继续向下填充，否则就回溯到上一行，继续搜索；当填到最后一行的时候，就需要检查一填满的每一列之和是否为34，如果符合，就继续向下填充，否则就回溯搜索。当行和列都填满的时候，就检查两个对角线时候和均为34，如果符合，就输出结果，否则直接返回。
每填入一个数字的之后，就将此数字的标志位置为true，表明下层递归搜索时要跳过这个数字。
由于搜索填入的数字的顺序是递增的，因此只要当前搜索的数字过大，不符合继续搜索的条件时，那么剩下的数字就不需要继续搜索了。
下面直接上代码：）
c++ code：
"copyright by lzeng,2010-10-20"
#include <iostream>
int res[10],result[16];
int count,num;
bool used[17];
//打印输出函数
void print(){
printf("case %d\n%d %d %d %d\n%d %d %d %d\n%d %d %d %d\n%d %d %d %d\n\n",
count++,result[0],result[1],result[2],result[3],result[4],
result[5],result[6],result[7],result[8],result[9],result[10],result[11],result[12],
result[13],result[14],result[15]);
}
//递归函数
void dfs(){
if(num==16)//表示幻方已经填满
{
if(res[9]+res[8]==0)//剪枝1，当两个对角线之和不全为34时，结果不符合
print();
return;
}
int rid,cid,did;//rid：行号，从0开始；cid：列号，从0开始；did：代表对角线，-1表示不在对角线上，0表示在右斜对角线上，1表示在左斜对角线上
rid=(num>>2);
cid=(num%4);
if((num%5==0)) did=0;
else if(num%3==0) did=1;
else did=-1;
for(int i=0;i<rid;i++)
if(res[i]!=0) return;//剪枝2，已经填满的行，如果有和不为34的，停止向下搜索，直接返回
if(num>12){
for(int i=0;i<cid;i++)
if(res[4+i]!=0) return;;//剪枝3，已经填满的列，如果有和不为34的，停止向下搜索，直接返回
}
for (int i=1;i<=16;i++)
{
if(used[i]) continue;
if(res[rid]<i) return;//剪枝4，当前所选的要填入的值比当前要填入的行剩下的值大的话，停止向下搜索，直接返回
if(res[4+cid]<i) return;//剪枝5，当前所选的要填入的值比当前要填入的列剩下的值大的话，停止向下搜索，直接返回
if(did!=-1&&res[8+did]<i) return;//剪枝6，当前所选的要填入的值，如果在对角线上的话，同时又比当前要填入的对角线剩下的值大的话，停止向下搜索，直接返回
res[rid]-=i;
res[4+cid]-=i;
if(did!=-1)res[8+did]-=i;
used[i]=true;
result[num]=i;
num++;
dfs();//递归迭代
num--;
res[rid]+=i;
res[4+cid]+=i;
if(did!=-1)res[8+did]+=i;
used[i]=false;
}
}
int main(){
count=1;
for(int i=0;i<16;i++) res[i]=34;
memset(used,false,sizeof(used));
num=0;
dfs();
return 0;
}
第一次参加这种比赛，也只能做做这种简单的算法题来安慰一下自己了！自己学习破解才刚刚起步，前方的路还很长，以后还要多多向大家学习！希望大家多多与我交流，不吝赐教！
by lzeng
2010-10-21
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
