题目

编程实现把1~9九个数字填入九宫格中，满足每行、每列和对角线上的三个数字和为15。如图所示。

Paste_Image.png

解题思路

“魔方阵“问题

魔方阵，古代又称“纵横图”，是指组成元素为自然数1、2…n2
的平方的n×n的方阵，其中每个元素值都不相等，且每行、每列以及主、副对角线上各n个元素之和都相等。

两种解题思路

• 方法1.利用魔方阵的数学规律解题
  这个方法属于利用了前人总结的经验，写程序会很简单。这也是课本例题。

• 方法2.穷举赋值
  把9个数字不重复的放到九个位置之中。再检查结果是否符合横竖斜的和都是15的要求。
  可以利用递归实现赋值。如下图所示，给第一个位置赋值1_{9，再给第二个位置赋值1}9，在给第三个位置赋值前先检查前面位置赋值是否有重复的，有的话这个递归的赋值就可以结束了……一直递归赋值到第九个位置

树图.png

源码1

利用魔方阵的数学规律，修改RANK值可输出任意奇数阶的魔方阵

#include <stdio.h>
#include <time.h>
#define RANK 3
void main()
{
    /*记时行,不用在意*/clock_t start, finish; start = clock();/*记时行*/
    int i, j, temp1, temp2;
    int  num = 1;
    int a[RANK][RANK];
    for (i = 0; i < RANK; i++)
    {
        for (j = 0; j < RANK; j++)
        {
            a[i][j] = 0;
        }
    }
    /*以上初始化矩阵*/
    /*下面都是运用魔方阵数学规律的运算*/
    i = 0;
    j = RANK / 2;
    a[i][j] = 1;
    do
    {
        num += 1;
        temp1 = i;
        temp2 = j;      
        if (i == 0)   
        {
            i = RANK - 1;
            j = j + 1;
        }
        else if (j == RANK - 1)
        {
            i = i - 1;
            j = 0;
        }
        else
        {
            i = i - 1; 
            j = j + 1;
        }

        if (a[i][j] == 0)
        {
            a[i][j] = num;
        }
        else
        {
            i = temp1 + 1;
            j = temp2;
            a[i][j] = num;
        }
    } while (num < RANK*RANK);
    /*输出魔方阵*/
    for (i = 0; i < RANK; ++i)
    {
        for (j = 0; j < RANK; ++j)
        {
            printf("%-3d", a[i][j]);
        }
        printf("\n");
    }
    /*记时*/finish = clock(); printf("共耗时%.3lf秒", ((double)finish - start) / 1000);/*记时*/
    getchar();
}

执行结果1

数学建模法.PNG

源码2

递归穷举法
可输出所有合适的排列方式
修改RANK 和SUM值可输出任意阶魔方阵

#include <stdio.h>
#include <time.h>
#define SUM 15
#define RANK 3
#define MAX (RANK*RANK)
void fillNum(int num, int position);
int checkRepeatedFigures(int * p, int position);
int checkSum(int * p);
int g_arr[MAX];

void main()
{
    /*记时用,不用在意*/clock_t start, finish; start = clock();/*记时用*/
    int i;
    for (i = 1; i <= MAX; i++)
    {
        fillNum(i, 0);
    }
    printf("查找完毕！\n");
    /*记时*/finish = clock(); printf("共耗时%.3lf秒", ((double)finish - start) / 1000);/*记时*/
    getchar();
}

void fillNum(int num, int position)
{
    int i;
    g_arr[position] = num;
    position++;
    if (position > MAX - 1)
    {
        if (checkRepeatedFigures(g_arr, position))//检查g_arr[9]有没有重复数字
        {
            if (checkSum(g_arr))//检查横竖斜和是否为15
            {
                printf("你得到了一个%d阶魔方阵\n", RANK);
                for (i = 0; i < MAX; i++)
                {
                    printf("%d ", g_arr[i]);
                    if ((i + 1) % RANK == 0)
                    {
                        printf("\n");
                    }
                }
                printf("\n");
            }
        }
    }
    else
    {
        if (checkRepeatedFigures(g_arr, position))
        {
            for (i = 1; i <= MAX; i++)
            {
                fillNum(i, position);
            }
        }
    }
}

int checkRepeatedFigures(int * p, int position)//检查指针p指向数组arr的position位置前是否有重复值，有返回0.无返回1
{
    int i, j;
    for (i = 0; i < position; i++)
    {
        for (j = i + 1; j < position; j++)
        {
            if (*(p + i) == *(p + j))
            {
                return 0;
            }
        }
    }
    return 1;
}

int checkSum(int * p)//检查p指向数组横竖斜和是否为15 是返回1，否返回0
{
    int arr[RANK][RANK];
    int i, j;
    int lineSum, columnSum;
    int leanSumX = 0, leanSumY = 0;
    //转化成二维数组
    for (i = 0; i < RANK; i++)
    {
        for (j = 0; j < RANK; j++)
        {
            arr[i][j] = *(p++);
        }
    }
    //检查横竖行和；
    for (i = 0; i < RANK; i++)
    {
        lineSum = 0;
        columnSum = 0;
        for (j = 0; j < RANK; j++)
        {
            lineSum += arr[i][j];
            columnSum += arr[j][i];
            if (i == j)
            {
                leanSumX += arr[i][j];
            }
            if (i == RANK - j - 1)
            {
                leanSumY += arr[i][j];
            }
        }
        if (lineSum != SUM || columnSum != SUM)
        {
            return 0;
        }
    }
    //检查对角线和
    if (leanSumX != SUM || leanSumY != SUM)
    {
        return 0;
    }
    return 1;
}

执行结果2

穷举法.PNG

总结

• 数学建模法
  优点:
  1.运算时间效率高，用时小于0.0001秒
  2. 代码简单。
  缺点:
  1.只能运算出一种结果，不全面。
  2.对于奇偶阶魔方阵，要区别对待写两段代码
• 递归穷举法
  优点:
  1.运算全面，可输出所有结果
  2.可输出任意魔方阵
  缺点:
  1.运行时间效率低，对于3阶魔方阵就需0.774秒的时长
  2.要提前查知指导N阶魔方阵的和SUM