题目166：十字形

欧拉计划

Criss Cross

A 4x4 grid is filled with digits d, 0 ≤ d ≤ 9.

It can be seen that in the grid

6 3 3 0
5 0 4 3
0 7 1 4
1 2 4 5

the sum of each row and each column has the value 12. Moreover the sum of each diagonal is also 12.

In how many ways can you fill a 4x4 grid with the digits d, 0 ≤ d ≤ 9 so that each row, each column, and both diagonals have the same sum?

题目：

一个 4×4 的网格用数字 d 填充，0 ≤ d ≤ 9。

可以看出，在下面这个网格中：

6 3 3 0
5 0 4 3
0 7 1 4
1 2 4 5

每一行和每一列的和都是 12，此外对角线之和也是 12。


那么，你能以多少种方法用 0-9 的数字填充一个 4×4 的网格，使得每行、每列和对角线的和相等呢？

guosl

应用穷举搜索。
答案：7130034

1. #include <iostream>
   
2. #include <vector>
   
3. #include <set>
   
4. #include <algorithm>
   
5. #include <cstring>
   
6. #include <omp.h>
   
7. using namespace std;
   
8. 
   
9. struct stMatrix//4x4矩阵
   
10. {
    
11.   unsigned char a[4][4];
    
12.   stMatrix(void)
    
13.   {
    
14.     memset(a, 0, sizeof(a));
    
15.   }
    
16.   bool check(int d)//验证对角线与反对角线元素之和是否满足要求
    
17.   {
    
18.     if (int(a[0][0] + a[1][1] + a[2][2] + a[3][3]) != d)
    
19.       return false;
    
20.     if (int(a[3][0] + a[2][1] + a[1][2] + a[0][3]) != d)
    
21.       return false;
    
22.     return true;
    
23.   }
    
24. };
    
25. 
    
26. inline void getrow(int d, int n, vector<short>& vRows) //生成所有满足条件的行
    
27. {
    
28.   int s = 0, k = n;
    
29.   while (k > 0)
    
30.   {
    
31.     s += k % 10;
    
32.     k /= 10;
    
33.   }
    
34.   if (s == d)
    
35.     vRows.push_back(n);
    
36. }
    
37. 
    
38. long long cml(stMatrix m)//将矩阵变成long long以便查重
    
39. {
    
40.   long long x = 0;
    
41.   for (int r = 3; r >= 0; --r)
    
42.   {
    
43.     for (int c = 3; c >= 0; --c)
    
44.       x = x * 10 + m.a[r][c];
    
45.   }
    
46.   return x;
    
47. }
    
48. 
    
49. void gm1(stMatrix m, int d, set<long long>& sM)//检验矩阵是否满足要求并查重
    
50. {
    
51.   if (m.check(d))
    
52.   {
    
53.     sM.insert(cml(m));
    
54.     stMatrix m1;
    
55.     for (int i = 0; i < 4; ++i)
    
56.     {
    
57.       for (int j = 0; j < 4; ++j)
    
58.         m1.a[i][j] = m.a[j][i];
    
59.     }
    
60.     sM.insert(cml(m1));
    
61.     for (int i = 0; i < 4; ++i)
    
62.     {
    
63.       for (int j = 0; j < 4; ++j)
    
64.         m1.a[i][j] = m.a[3 - i][3 - j];
    
65.     }
    
66.     sM.insert(cml(m1));
    
67.     for (int i = 0; i < 4; ++i)
    
68.     {
    
69.       for (int j = 0; j < 4; ++j)
    
70.         m1.a[i][j] = m.a[3 - j][3 - i];
    
71.     }
    
72.     sM.insert(cml(m1));
    
73.   }
    
74. }
    
75. 
    
76. void gm(const short b[3], int d, set<long long>& sM)//根据前3行来生成一个矩阵
    
77. {
    
78.   stMatrix m;
    
79.   short c[3];
    
80.   c[0] = b[0];
    
81.   c[1] = b[1];
    
82.   c[2] = b[2];
    
83.   short s = 0;
    
84.   for (int i = 0; i < 4; ++i)//生成矩阵
    
85.   {
    
86.     m.a[0][i] = c[0] % 10;
    
87.     m.a[1][i] = c[1] % 10;
    
88.     m.a[2][i] = c[2] % 10;
    
89.     m.a[3][i] = d - (m.a[0][i] + m.a[1][i] + m.a[2][i]);
    
90.     if (m.a[3][i] < 0 || m.a[3][i]>9)
    
91.       return;
    
92.     s += m.a[3][i];
    
93.     c[0] /= 10;
    
94.     c[1] /= 10;
    
95.     c[2] /= 10;
    
96.   }
    
97.   if (s != d)
    
98.     return;
    
99.   int x[4] = { 0,1,2,3 };
    
100.   do //对行进行排列变换
     
101.   {
     
102.     stMatrix m1;
     
103.     for (int i = 0; i < 4; ++i)
     
104.     {
     
105.       for (int j = 0; j < 4; ++j)
     
106.         m1.a[i][j] = m.a[x[i]][j];
     
107.     }
     
108.     int y[4] = { 0,1,2,3 };
     
109.     do //对列进行排列变换
     
110.     {
     
111.       stMatrix m2;
     
112.       for (int i = 0; i < 4; ++i)
     
113.       {
     
114.         for (int j = 0; j < 4; ++j)
     
115.           m2.a[i][j] = m1.a[i][y[j]];
     
116.       }
     
117.       gm1(m2, d, sM);//检验并查重
     
118.     } while (next_permutation(y, y + 4));
     
119.   } while (next_permutation(x, x + 4));
     
120. }
     
121. 
     
122. int main(void)
     
123. {
     
124.   long long nCount = 0;
     
125. #pragma omp parallel for reduction(+:nCount) schedule(dynamic,1)
     
126.   for (int d = 0; d <= 18; ++d)//对和值进行枚举
     
127.   {
     
128.     vector<short> vRows;
     
129.     for (short i = 0; i < 10000; ++i)
     
130.       getrow(d, i, vRows);
     
131.     set<long long> sM;
     
132.     for (int i = 0; i < (int)vRows.size(); ++i)
     
133.     {
     
134.       short b[3];
     
135.       b[0] = vRows[i];
     
136.       for (int j = i; j < (int)vRows.size(); ++j)
     
137.       {
     
138.         b[1] = vRows[j];
     
139.         for (int k = j; k < (int)vRows.size(); ++k)
     
140.         {
     
141.           b[2] = vRows[k];
     
142.           gm(b, d, sM);
     
143.         }
     
144.       }
     
145.     }
     
146.     nCount += sM.size();
     
147.     if (36 - d != d)
     
148.       nCount += sM.size();//根据对称性
     
149.   }
     
150.   cout << nCount << endl;
     
151.   return 0;
     
152. }

复制代码