题目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

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
#include <omp.h>
using namespace std;

struct stMatrix//4x4矩阵
{
  unsigned char a[4][4];
  stMatrix(void)
  {
    memset(a, 0, sizeof(a));
  }
  bool check(int d)//验证对角线与反对角线元素之和是否满足要求
  {
    if (int(a[0][0] + a[1][1] + a[2][2] + a[3][3]) != d)
      return false;
    if (int(a[3][0] + a[2][1] + a[1][2] + a[0][3]) != d)
      return false;
    return true;
  }
};

inline void getrow(int d, int n, vector<short>& vRows) //生成所有满足条件的行
{
  int s = 0, k = n;
  while (k > 0)
  {
    s += k % 10;
    k /= 10;
  }
  if (s == d)
    vRows.push_back(n);
}

long long cml(stMatrix m)//将矩阵变成long long以便查重
{
  long long x = 0;
  for (int r = 3; r >= 0; --r)
  {
    for (int c = 3; c >= 0; --c)
      x = x * 10 + m.a[r][c];
  }
  return x;
}

void gm1(stMatrix m, int d, set<long long>& sM)//检验矩阵是否满足要求并查重
{
  if (m.check(d))
  {
    sM.insert(cml(m));
    stMatrix m1;
    for (int i = 0; i < 4; ++i)
    {
      for (int j = 0; j < 4; ++j)
        m1.a[i][j] = m.a[j][i];
    }
    sM.insert(cml(m1));
    for (int i = 0; i < 4; ++i)
    {
      for (int j = 0; j < 4; ++j)
        m1.a[i][j] = m.a[3 - i][3 - j];
    }
    sM.insert(cml(m1));
    for (int i = 0; i < 4; ++i)
    {
      for (int j = 0; j < 4; ++j)
        m1.a[i][j] = m.a[3 - j][3 - i];
    }
    sM.insert(cml(m1));
  }
}

void gm(const short b[3], int d, set<long long>& sM)//根据前3行来生成一个矩阵
{
  stMatrix m;
  short c[3];
  c[0] = b[0];
  c[1] = b[1];
  c[2] = b[2];
  short s = 0;
  for (int i = 0; i < 4; ++i)//生成矩阵
  {
    m.a[0][i] = c[0] % 10;
    m.a[1][i] = c[1] % 10;
    m.a[2][i] = c[2] % 10;
    m.a[3][i] = d - (m.a[0][i] + m.a[1][i] + m.a[2][i]);
    if (m.a[3][i] < 0 || m.a[3][i]>9)
      return;
    s += m.a[3][i];
    c[0] /= 10;
    c[1] /= 10;
    c[2] /= 10;
  }
  if (s != d)
    return;
  int x[4] = { 0,1,2,3 };
  do //对行进行排列变换
  {
    stMatrix m1;
    for (int i = 0; i < 4; ++i)
    {
      for (int j = 0; j < 4; ++j)
        m1.a[i][j] = m.a[x[i]][j];
    }
    int y[4] = { 0,1,2,3 };
    do //对列进行排列变换
    {
      stMatrix m2;
      for (int i = 0; i < 4; ++i)
      {
        for (int j = 0; j < 4; ++j)
          m2.a[i][j] = m1.a[i][y[j]];
      }
      gm1(m2, d, sM);//检验并查重
    } while (next_permutation(y, y + 4));
  } while (next_permutation(x, x + 4));
}

int main(void)
{
  long long nCount = 0;
#pragma omp parallel for reduction(+:nCount) schedule(dynamic,1)
  for (int d = 0; d <= 18; ++d)//对和值进行枚举
  {
    vector<short> vRows;
    for (short i = 0; i < 10000; ++i)
      getrow(d, i, vRows);
    set<long long> sM;
    for (int i = 0; i < (int)vRows.size(); ++i)
    {
      short b[3];
      b[0] = vRows[i];
      for (int j = i; j < (int)vRows.size(); ++j)
      {
        b[1] = vRows[j];
        for (int k = j; k < (int)vRows.size(); ++k)
        {
          b[2] = vRows[k];
          gm(b, d, sM);
        }
      }
    }
    nCount += sM.size();
    if (36 - d != d)
      nCount += sM.size();//根据对称性
  }
  cout << nCount << endl;
  return 0;
}