一个 5x5 的网格中的五位质数

Question

|---|---|---|---|---|
| 1 | 1 | 3 | 5 | 1 |
|---|---|---|---|---|
| 3 | 3 | 2 | 0 | 3 |
|---|---|---|---|---|
| 3 | 0 | 3 | 2 | 3 |
|---|---|---|---|---|
| 1 | 4 | 0 | 3 | 3 |
|---|---|---|---|---|
| 3 | 3 | 3 | 1 | 1 |
|---|---|---|---|---| 

(图1)

图1展示了一个正方形，每一行、每一列和两个对角线都可以读作一个五位素数。行从左到右读取，列从上到下读取，两个对角线都是从左到右读取。根据输入文件INPUT.TXT中的数据，编写一个程序来构建这样的正方形。

素数必须具有相同的数字总和（例如示例中的11）。正方形左上角的数字是预先确定的（例如示例中为1）。

同一个正方形中可能会使用多次素数。

如果有多种解决方案，则必须全部呈现出来。一个五位素数不能以零开头，即00003不是一个五位素数。

输入数据

11 1

我正在尝试解IOI'94竞赛的问题-问题3-质数。

我已经构建了大部分辅助函数...

1. 使用埃拉托斯特尼筛选法生成5位素数（在9999和100000之间）
2. 构建一个计算数字总和的函数（12345 = 1+2+3+4+5 = 15）
3. 构建一个检查数组是否整体数字总和相等的函数
4. 构建一个检查数字是否以指定数字开头的函数（startWith(12345,1)返回true）

问题：我的问题是我不知道如何填充数组或使用回溯能力进行持续的检查:(。有谁可以帮助我吗?我该如何填充二维数组，以便它包含来自素数表的值，并且所有角度上的数字总和都正确?

*NB: 生成5位素数的埃拉托斯特尼筛法方法也有过滤以X开头并且总和等于M的值的能力*

完整问题：http://olympiads.win.tue.nl/ioi/ioi94/contest/day1prb3/problem.html

添加值的潜在顺序，只是不知道如何实现:(。

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

- ferronrsmith

---

我已经突出了问题。 - ferronrsmith

Answer 1

根据您的描述，我假设您已经有了一个由5位质数组成的列表。请过滤该列表，使其仅包含具有正确数字总和的质数。

您需要一个名为valid的函数来检查给定1到5个数字是否可以组成一个有效的正方形。（很明显，列数字决定其他行和对角线。因此，如果第一列的第三个数字是7，但没有以7开头的质数，我们知道不能在第一列中使用此质数。这样，在不查看所有其他数字的情况下，可以提前剪枝搜索树。）

您需要另一个函数来获取所有在位置n（1..5）具有特定数字的有效质数集。也许您想预先计算并将其存储在某个树或数组中。

主要工作是在valid函数中完成的，它必须检查是否存在具有由列中的质数确定的位置上的数字的行和对角线的质数。

然后解决方案列表如下：

[ (c1, c2, c3, c4, c5) | c1 <- primes, valid [c1], 
      c2 <- primes, valid [c1,c2],
      c3 <- primes, valid [c1,c2,c3],
      c4 <- primes, valid [c1,c2,c3,c4],
      c5 <- primes, valid [c1,c2,c3,c4,c5] ]

或者，更加强调地说：

 for each c1 in primes
    if valid(c1) then foreach c2 in primes
        if valid(c1,c2) then foreach c3 in primes
            if valid(c1,c2,c3) then foreach c4 in primes
                 if valid(c1,c2,c3,c4) then foreach c5 in primes
                      if valid(c1,c2,c3,c4,c5) then print solution

补充：由于我们只需要查找以某些数字序列开头的数字，因此可以使解决方案更加高效。考虑当c1、c2和c3已知且valid()即将检查第3行时。它获取c1、c2和c3的第3位数字，并将其解释为必须出现在第3行的数字的主导3位数字。我们只需要用零填充它，然后检查是否知道一个大于此数字的质数，但该差值必须低于100（以保留前导数字）。但如果我们有一个按质数候选数排序的数组，则不需要进行比二进制搜索更多的操作。

- Ingo

---

同时请记住，没有以2、4、5、6、8或0结尾的5位质数。 - Carl Manaster

这个算法在最坏情况下不起作用，即23 3，需要很长时间才能找到答案。 - 2147483647