5x5

解一个简单的数学问题：

将1 至 25 的整数分别不重复地填入一个 5 行 5 列的矩阵中，求满足当 N 为 1 至 5 的整数时第 N 行数字的乘积和第 N 列数字的乘积相等的矩阵。

计算得到了 26412140760 个解，输出文件约 9.198 GiB。

简单分析问题可得知以下约束条件：

左上至右下斜对角线中的数字将会同时出现在行乘积和列乘积中，这 5 个空格可以填入任意数。因此将数字排列到左上至右下斜对角线以外的 20 个空格中即可，剩余 5 个数字简单排列即可得出 120（5P5）种解。
- 已在程序中实现。
13，17，19 和 23 这 4 个数字是质数且没有它们的倍数，只能出现在左上至右下斜对角线中。因此使用这 4 个数字以外的 21 个数字进行排列。
- 已在程序中实现。
11 是质数且只有 22 是它的倍数。因此 11 和 22 一定会在以左上至右下斜对角线为对称轴对称的两个空格中。
- 尚未在程序中实现。
7 是质数且只有 14 和 21 是它的倍数。因此 7，14 和 21 一定会在三个空格中，任意一个在左上至右下斜对角线上，或者其中任意一个空格的行坐标一定等于另一空格的列坐标。
- 尚未在程序中实现。
一些 4 个数的组合的乘积在所有组合的乘积中只出现了一次。因此这些组合一定不会出现在同一行或同一列中。
- 部分在程序中实现。

编写了这些程序：

gen.py 用于枚举所有一定不会出现在同一行或同一列中的 4 个数的排列。
- 输出到 ./data.txt。
5x5.cpp 用于枚举所有符合部分约束条件的情况并测试是否满足条件。
- 多线程计算，考虑了部分约束条件，计算速度较快（在 AMD R7 4800U 上预计需要几十个小时）。
- 结果输出到 ./result.txt，进度输出到 stderr。
5x5.old.cpp 用于枚举所有的情况并测试是否满足条件。
- 单线程计算，没有考虑约束条件，计算速度极慢（预计需要几百亿年）。可能有漏洞。
- 输出到 stdout。
count.py 用于统计解的数量。
- 从 ./result.txt 输入，输出到 stdout。

构建

$ git clone https://github.com/NKID00/5x5.git
$ cd 5x5
$ g++ ./5x5.cpp --std=c++11 -O3 -o ./5x5  # 构建
$ ./5x5  # 运行

如果发现漏洞或者遇到问题，欢迎提交 Issue 或者 Pull Request。

使用 MIT License 进行许可。