[C language] implementation of magic square array (the most complete)

One 、 What is Rubik's Cube ？

Rubik's cube matrix , Also called magic square , Have the same number of rows and columns , And in Every row, every column 、 The sum on the diagonal is equal Matrix .

N Step magic square , Natural number 1 To Line up N That's ok N Array of columns , Make each line 、 On each column and two main diagonals N The sum of the numbers is equal , be equal to  .

Two 、 The classification of magic square matrix

For the construction of magic square matrix , It can be divided into the following three types ：

• Odd order （N It's odd [2n+1 In the form of ] ）
• Single even order （N by 4 Multiple [4n In the form of ] ）
• Double even order （N For other even numbers [4n+2 In the form of ] ）

3、 ... and 、 Magic square matrix and code implementation

1、 Odd order magic square matrix （n It's odd ）

General solution ：

1. take 1 Put it in the middle of the first row
2. from 2 Start to until , The emission law of each number is ： The number of rows of each number is less than the number of rows of the previous number 1, The number of columns emitted by each number is greater than the number of columns of the previous number 1
3. Special case of the line ： If the number of lines of the previous number is 1, Then the number is ranked at n That's ok
4. Special case of column ： If the number of columns of the previous number is n, Then the number is ranked at 1 Column
5. Other situations ： If there are already numbers on the position determined according to the above rule , Put the number to be arranged under the previous number .

The following is 5 Example of order magic square matrix （ Readers can think according to the above solution ）：

17	24	1	8	15
23	5	7	14	16
4	6	13	20	22
10	12	19	21	3
11	18	25	2	9

Code implementation ： 

// Odd order magic square matrix 
void odd_number(int n)
{
    int i;
    int row,line,row_0,line_0;//row Column coordinates ,line For row coordinates ,row_0 Record line coordinates ,line_0 Record column coordinates 
    line=0;row=(n+1)/2-1;// Initialization line 、 Column coordinates 
    a[line][row]=1;
    for(i=2;i<=n*n;i++)
    {
        line_0=line;row_0=row;// Record the last loop line 、 Column coordinates 
        if(line==0&&row==n-1)// The first 1 Xing di n List the situation 
        {
            line=n-1;// Row coordinates go to n That's ok 
            row=0;// Column coordinates go to 1 That's ok 
        }
        else if(line==0)// The first 1 Non line n List the situation 
        {
            line=n-1;// Row coordinates go to n That's ok 
            row++;// Column coordinates +1
        }
        else if(row==n-1)// The first n Column No 1 Yes, I can 
        {
            row=0;// Column coordinates go to 1 Column 
            line--;// Row coordinates -1
        }
        else// In general 
        {
            line--;// Row coordinates -1
            row++;// Column coordinates +1
        }
        if(a[line][row]!=0)// Determine whether there are numbers in this position 
        {
            line=line_0+1;//（ Based on this for Coordinates of the beginning of the cycle ） Row coordinates -1, Jump to the next line 
            row=row_0;//（ Based on this for Coordinates of the beginning of the cycle ） The column coordinates do not change 
        }
        a[line][row]=i;// assignment 
    }
}

2、 Single even order magic square matrix （n For the even , And can't be 4 to be divisible by ）

General solution （ With 10 Take the magic cube as an example ）：

1. First, divide the magic square array into four quadrants （ Form four odd order magic squares ）, The four quadrants are filled with odd order magic square matrix （ In sequence A→D→B→C）.

   A	B
   C	D

   17	24	1	8	15	67	74	51	58	65
   23	5	7	14	16	73	55	57	64	66
   4	6	13	20	22	54	56	63	70	72
   10	12	19	21	3	60	62	69	71	53
   11	18	25	2	9	61	68	75	52	59
   92	99	76	83	90	42	49	26	33	40
   98	80	82	89	91	48	30	32	39	41
   79	81	88	95	97	29	31	38	45	47
   85	87	94	96	78	35	37	44	46	28
   86	93	100	77	84	36	43	50	27	34

2. about A The middle line of the quadrant , Start with the middle pane , Mark from left to right k grid ; about A Other rows of quadrants , Mark the leftmost k grid （ among ,k Satisfy expression n=4k+2）.

   17	24	1	8	15	67	74	51	58	65
   23	5	7	14	16	73	55	57	64	66
   4	6	13	20	22	54	56	63	70	72
   10	12	19	21	3	60	62	69	71	53
   11	18	25	2	9	61	68	75	52	59
   92	99	76	83	90	42	49	26	33	40
   98	80	82	89	91	48	30	32	39	41
   79	81	88	95	97	29	31	38	45	47
   85	87	94	96	78	35	37	44	46	28
   86	93	100	77	84	36	43	50	27	34

3. take A The numbers in the quadrants are the same as C The number exchange position on the corresponding position in the quadrant .

   92	99	1	8	15	67	74	51	58	65
   98	80	7	14	16	73	55	57	64	66
   4	6	88	95	22	54	56	63	70	72
   85	87	19	21	3	60	62	69	71	53
   86	93	25	2	9	61	68	75	52	59
   17	24	76	83	90	42	49	26	33	40
   23	5	82	89	91	48	30	32	39	41
   79	81	13	20	97	29	31	38	45	47
   10	12	94	96	78	35	37	44	46	28
   11	18	100	77	84	36	43	50	27	34

4. about B Middle grid of all rows in quadrant , Mark from left to right k-1 grid , And with D The digital exchange of the corresponding position in the quadrant .

   92	99	1	8	15	67	74	51	58	65
   98	80	7	14	16	73	55	57	64	66
   4	6	88	95	22	54	56	63	70	72
   85	87	19	21	3	60	62	69	71	53
   86	93	25	2	9	61	68	75	52	59
   17	24	76	83	90	42	49	26	33	40
   23	5	82	89	91	48	30	32	39	41
   79	81	13	20	97	29	31	38	45	47
   10	12	94	96	78	35	37	44	46	28
   11	18	100	77	84	36	43	50	27	34

   92	99	1	8	15	67	74	26	58	65
   98	80	7	14	16	73	55	32	64	66
   4	6	88	95	22	54	56	38	70	72
   85	87	19	21	3	60	62	44	71	53
   86	93	25	2	9	61	68	50	52	59
   17	24	76	83	90	42	49	51	33	40
   23	5	82	89	91	48	30	57	39	41
   79	81	13	20	97	29	31	63	45	47
   10	12	94	96	78	35	37	69	46	28
   11	18	100	77	84	36	43	75	27	34

  Code implementation ：

void single_even_number(int n)
{
    int i,j;
    int k,line,row,line_0,row_0;//k Is with the n Related parameters ,line For row coordinates ,row Column coordinates ,line_0 Record line coordinates ,row_0 Record column coordinates 
    k=(n-2)/4;
    //A quadrant 
    line=0;row=k;// initialization A Quadrant row and column coordinates 
    a[line][row]=1;
    for(i=2;i<=(2*k+1)*(2*k+1);i++)//A The number range of quadrants is 1~(2*k+1)*(2*k+1)
    {
        line_0=line;row_0=row;// Record the initial row and column coordinates of this cycle 
        if(line==0&&row==2*k)// The first 0 Xing di 2*k List the situation 
        {
            line=2*k;// The row coordinates are changed to 2*k
            row=0;// The column coordinates are converted to 0
        }
        else if(line==0)// The first 0 Non line 2*k List the situation 
        {
            line=2*k;// The row coordinates are changed to 2*k
            row++;// Column coordinates +1
        }
        else if(row==2*k)// The first 2*k Column No 0 Yes, I can 
        {
            row=0;// The column coordinates are converted to 0
            line--;// Row coordinates -1
        }
        else// In general 
        {
            line--;// Row coordinates -1
            row++;// Column coordinates +1
        }
        if(a[line][row]!=0)// Judge whether there are numbers in this position 
        {
            line=line_0+1;
            row=row_0;
        }
        a[line][row]=i;// assignment 
    }
    //D quadrant 
    line=2*k+1;row=3*k+1;// initialization D Quadrant row and column coordinates 
    a[2*k+1][3*k+1]=(2*k+1)*(2*k+1)+1;
    for(i=(2*k+1)*(2*k+1)+2;i<=2*(2*k+1)*(2*k+1);i++)//D Quadrant number range (2*k+1)*(2*k+1)+1~2*(2*k+1)*(2*k+1)
	{
		line_0=line;row_0=row;// Record the initial row and column coordinates of this cycle 
		if((line==2*k+1)&&(row==4*k+1))// The first (2*k+1) Xing di (4*k+1) List the situation 
		{
			line=4*k+1;// The row coordinates are changed to 4*k+1
			row=2*k+1;// The column coordinates are converted to 2*k+1
		}
		else if(line==2*k+1)// The first (2*k+1) Non line (4*k+1) List the situation 
		{
			line=4*k+1;// The row coordinates are changed to 4*k+1
			row++;// Column coordinates +1
		}
		else if(row==4*k+1)// The first (4*k+1) Column No (2*k+1) Yes, I can 
		{
			row=2*k+1;// The column coordinates are converted to 2*k+1
			line--;// Row coordinates -1
		}
		else// In general 
		{
			line--;// Row coordinates -1
			row++;// Column coordinates +1
		}
		if(a[line][row]!=0)// Judge whether there are numbers in this position 
		{
			line=line_0+1;
			row=row_0;
		}
		a[line][row]=i;// assignment 
	}
    //B quadrant 
    line=0;row=3*k+1;// initialization B Quadrant row and column coordinates 
    a[line][row]=2*(2*k+1)*(2*k+1)+1;
    for(i=2*(2*k+1)*(2*k+1)+2;i<=3*(2*k+1)*(2*k+1);i++)//B Quadrant number range 2*(2*k+1)*(2*k+1)+1~3*(2*k+1)*(2*k+1)
	{
		line_0=line;row_0=row;// Record the initial row and column coordinates of this cycle 
		if((line==0)&&(row==4*k+1))// The first 0 Xing di (4*k+1) List the situation 
		{
			line=2*k;// The row coordinates are changed to 2*k
			row=2*k+1;// The column coordinates are converted to 2*k+1
		}
		else if(line==0)// The first 0 Non line (4*k+1) List the situation 
		{
			line=2*k;// The row coordinates are changed to 2*k
			row++;// Column coordinates +1
		}
		else if(row==4*k+1)// The first (4*k+1) Column No 0 Yes, I can 
		{
			row=2*k+1;// The column coordinates are converted to 2*k+1
			line--;// Row coordinates -1
		}
		else// In general 
		{
			line--;// Row coordinates -1
			row++;// Column coordinates +1
		}
		if(a[line][row]!=0)// Judge whether there are numbers in this position 
		{
			line=line_0+1;
			row=row_0;
		}
		a[line][row]=i;// assignment 
	}
    //C quadrant 
    line=2*k+1;row=k;// initialization C Quadrant row and column coordinates 
    a[line][row]=3*(2*k+1)*(2*k+1)+1;
    for(i=3*(2*k+1)*(2*k+1)+2;i<=4*(2*k+1)*(2*k+1);i++)//C Quadrant number range 3*(2*k+1)*(2*k+1)+1~4*(2*k+1)*(2*k+1)
	{
		line_0=line;row_0=row;// Record the initial row and column coordinates of this cycle 
		if((line==2*k+1)&&(row==2*k))// The first (2*k+1) Xing di 2*k List the situation 
		{
			line=4*k+1;// The row coordinates are changed to 4*k+1
			row=0;// The column coordinates are converted to 0
		}
		else if(line==2*k+1)// The first (2*k+1) Non line 2*k List the situation 
		{
			line=4*k+1;// The row coordinates are changed to 4*k+1
			row++;// Column coordinates +1
		}
		else if(row==2*k)// The first 2*k Column No (2*k+1) Yes, I can 
		{
			row=0;// The column coordinates are converted to 0
			line--;// Row coordinates -1
		}
		else// In general 
		{
			line--;// Row coordinates -1
			row++;// Column coordinates +1
		}
		if(a[line][row]!=0)// Judge whether there are numbers in this position 
		{
			line=line_0+1;
			row=row_0;
		}
		a[line][row]=i;// assignment 
	}
    // in A、C Position of quadrant related digits 
    for(i=0;i<2*k+1;i++)// about A、C quadrant 
	{
        int j_0,f=0;//j_0 Record the number of cycles ,f=0 Is the flag bit 
        for(j=0,j_0=0;j_0<k;j_0++,j++)// Conduct k Secondary exchange 
		{
			if(i==k&&f==0)// Determine whether it is an intermediate line 
			{
				j+=k;
				f=1;
			}	
			x=a[i][j];
			a[i][j]=a[i+2*k+1][j];
			a[i+2*k+1][j]=x;
		} 
    }
	// in B、D Position of quadrant related digits 
	if(k>=2)
		for(i=0;i<k-1;i++)// Swap each line k-1 Number 
			for(j=0;j<2*k+1;j++)// From 0 Go to the first place 2*k Line exchange 
			{
				x=a[j][3*k+1+i];
				a[j][3*k+1+i]=a[2*k+1+j][3*k+1+i];
				a[2*k+1+j][3*k+1+i]=x;
			}
}

3、 Double even order magic square matrix （n For the even , And can be 4 to be divisible by ）

General rules ：

1. Use horizontal and vertical lines to mark n The first order magic square array is divided into m individual Small magic square array .
2. take The number increases from small to large , From left to right , From top to bottom , Fill in the square matrix in turn , encounter 4*4 The diagonals of the small square matrix of are not filled （ notes ： The number not filled in this position will not be used as the number filled in the next position ）
3. take The number increases from small to large , From right to left , From bottom to top , Fill in the square matrix in turn 4*4 On the diagonal of the small square matrix , Do not fill in other places （ notes ： The number not filled in this position will not be used as the number filled in the next position ）
4. take 2、3 The two-step magic square array is merged into a magic square array , Double even order magic square array is arranged .

64	2	3	61	60	6	7	57
9	55	54	12	13	51	50	16
17	47	46	20	21	43	42	24
40	26	27	37	36	30	31	33
32	34	35	29	28	38	39	25
41	23	22	44	45	19	18	48
49	15	14	52	53	11	10	56
8	58	59	5	4	62	63	1

The key to solve the double even order magic square matrix is to Calculate diagonals accurately .

The diagonal line from the top left to the bottom right meets line % 4 == row % 4

The diagonals from the top right to the bottom left meet  ( line + row ) % 4 == 3

	0	1	2	3	4	5	6	7
0	0			3	4			7
1		2	3			6	7
2		3	4			7	8
3	3			6	7			10
4	4			7	8			11
5		6	7			10	11
6		7	8			11	12
7	7			10	11			14

Code implementation ：

void double_even_number(int n)
{
    int line,row;
	int t_1=1,t_2=n*n;//t_1 It is positive ,t_2 Reverse 
	for(line=0;line<n;line++)
	{
		for(row=0;row<n;row++)
		{
			if(line%4==row%4||(line+row)%4==3)// Judge whether it is diagonal 
				a[line][row]=t_2;
			else
				a[line][row]=t_1;
			t_1++;
			t_2--;
		}
	}
}

The main function is as follows ：

#include<stdio.h>
#include<math.h> 
int a[100][100]={0};// Will array a All elements in the are assigned the value 0
int main()
{
	int n,i,j;
	void odd_number(int n);
	void single_even_number(int n);
	void double_even_number(int n);
	printf(" Please enter “ Rubik's Cube  ” Parameters of n=");
	scanf("%d",&n);
	if(n%2==1)
		odd_number(n);
	else if(n%4==2)
		single_even_number(n); 
	else if(n%4==0)
		double_even_number(n);
	printf(" The “ Rubik's Cube  ” as follows :\n");
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			printf("%4d",a[i][j]);
		printf("\n");
	}
	return 0;
 }