九宫格C语言递归程序 [置顶] C语言递归实现N宫格（九宫格）源码

刚开始做九宫格的时候，能想到的就是几个for循环，很清楚很简单，同样也比较的低级，了解递归的魅力后，在高人的指点下，原来也可以这样的实现，写到这时，让我想到了当年教我们的老师，thanx，好代码，我还留着呢，我把当年写的源码分享一下，欢迎拍砖

如果有更好的方法，也可交流一下。。。。。。。

/**************************************************************************************************************

**文件:mian.c

**编写者:huangminqiang

**编写日期:3月12号

**简要描述:递归实现N宫格(九宫格)

**修改者:

**修改日期:

**注:N>5后，运行结果需要的时间很长，适用于4-9-16宫格。

**************************************************************************************************************/

#include

#define N4//每行或列的数的个数

#define MAX(N*N)//最大数

#define ROW_END1//行结束标志

#define COL_END2//列结束标志

#define LEFT_DOWN3//左下角标志

#define RIGHT_DOWN4//右下角标志

#define OTHER0//其它情况标志

//定义N宫格结构体

struct _ngg

{

int num[MAX];//定义填数的数组

int val;//判断相等的值

int count;//符合条件的组合数

};

//函数原型声明

//初始化结构体变量

void init(struct _ngg *pngg);

//开始填数

void fill(struct _ngg * pngg,int pos);

//获取标志

int getFlag(int pos);

//判断某个数在之前是否已填过，已填过则返回 1 ，否则返回 0

int isFilled(struct _ngg * pngg,int pos,int i);

//计算行和

int sumRow(struct _ngg * pngg,int pos);

//计算列和

int sumCol(struct _ngg * pngg, int pos);

//计算左上-右下对角和

int sumLU_RD(struct _ngg * pngg);

//计算右上-左下对角和

int sumRU_LD(struct _ngg * pngg);

//打印数组

void prt(struct _ngg * pngg);

//主函数，初始化并开始按位置填数

int main(void)

{

//变量声明

struct _ngg ngg = {0};

//初始化结构体变量

init(&ngg);

printf("N = %d, MAX = %d, val = %d\n",N,MAX,ngg.val);

//开始填数

fill(&ngg,0);

return 0;

}

//初始化结构体变量

void init(struct _ngg *pngg)

{

//计算val的值

pngg->val = MAX * (MAX + 1) / 2 / N;

}

//子函数实现填数

void fill(struct _ngg * pngg,int pos)

{

//声明变量

int flag = getFlag(pos);//结束标志

int i;

//从 1 到 MAX 逐个填入数组的 pos 位置

for(i = 1; i <=MAX; i++)

{

//判断 i 在前面有没有填过，填过则填下一个数

if(isFilled(pngg,pos,i))

{

continue;

}

//填入 i 到 pos 位置

pngg->num[pos] = i;

//根据 flag 分情况进行处理

switch(flag)

{

//行结束

case ROW_END:

//如果行和相等则继续填下一个位置

if(pngg->val == sumRow(pngg,pos))

{

fill(pngg,pos+1);

}

break;

//列结束

case COL_END:

//如果列和相等则继续填下一个位置

if(pngg->val == sumCol(pngg,pos))

{

fill(pngg,pos+1);

}

break;

//左下角

case LEFT_DOWN:

//如果列和、右上-左下对角和相等则填下一个位置

if(pngg->val == sumCol(pngg,pos) &&

pngg->val == sumRU_LD(pngg))

{

fill(pngg,pos+1);

}

break;

//右下角

case RIGHT_DOWN:

//如果行和、列和、左上-右下对角和相等则打印数组

if(pngg->val == sumRow(pngg,pos) &&

pngg->val == sumCol(pngg,pos) &&

pngg->val == sumLU_RD(pngg) )

{

prt(pngg);

}

break;

//其它情况

//case OTHER:

default:

//其它情况填下一个位置

fill(pngg,pos+1);

}

}

}

//获取标志

int getFlag(int pos)

{

//如果到了行尾，但不是最后一个元素则为行结束

if(0 == (pos + 1) % N && MAX - 1 != pos)

{

return ROW_END;

}

//如果到了列尾，但不是第 0 列，也不是最后一个元素，则为列结束

if(pos > N * (N - 1) && MAX - 1 != pos)

{

return COL_END;

}

//如果是最后一行，并且是第 0 列，则为左下角

if(pos == N * (N - 1))

{

return LEFT_DOWN;

}

//如果是最后一个元素，则是右下角

if(MAX - 1 == pos)

{

return RIGHT_DOWN;

}

//除此之外是其它情况

return OTHER;

}

//判断某个数在之前是否已填过，已填过则返回 1 ，否则返回 0

int isFilled(struct _ngg * pngg,int pos,int i)

{

int j;

for(j = 0; j < pos;j++)

{

if(pngg->num[j] == i)

{

return 1;

}

}

return 0;

}

//计算行和

int sumRow(struct _ngg * pngg,int pos)

{

int i,sum = 0;

//从第 pos 个元素往回加

for(i = pos; i > pos - N; i--)

{

sum += pngg->num[i];

}

return sum;

}

//计算列和

int sumCol(struct _ngg * pngg, int pos)

{

int i,sum = 0;

//从第 pos 个元素往上加

for(i = pos; i >= 0; i -= N)

{

sum += pngg->num[i];

}

return sum;

}

//计算右上-左下对角和

int sumRU_LD(struct _ngg * pngg)

{

int i,sum = 0;

//从第 N - 1 个元素开始每次跳过 N - 1 个元素累加

for(i = N - 1; i < MAX -1; i += N - 1)

{

sum += pngg->num[i];

}

return sum;

}

//计算左上-右下对角和

int sumLU_RD(struct _ngg * pngg)

{

int i,sum = 0;

//从第 0 个元素开始每次跳过 N + 1个元素累加

for(i = 0; i < MAX; i += N + 1)

{

sum += pngg->num[i];

}

return sum;

}

//打印数组

void prt(struct _ngg * pngg)

{

int i;

printf("-----------------------------------------%d\n",++pngg->count);

for(i = 0; i < MAX; i++)

{

printf("\t%d",pngg->num[i]);

if(0 == (i + 1) % N)

{

printf("\n");

}

}

}