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）

问题：问题是我不'不知道如何填充数组或使用回溯功能来继续检查:(。有人可以帮助我吗？如何填充 2D 数组，使其包含素数表中的值，并且总和在所有角度上都是正确的?

*注意：生成 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

Answer 1

根据您所写的内容，我假设您已经有了一个 5 位数素数列表。
过滤列表，使其仅包含数字总和正确的素数。

您需要一个 valid 函数来检查一个有效的方块，给定列中的 1 到 5 个数字。 （很明显，列号决定了其他行和对角线。因此，如果第一列的第 3 位数字是 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、an 和 c3 的情况，valid() 将检查第 3 行。它采用 c1、c2 和 c3 的第 3 位数字，我们可以将它们解释为必须出现的数字的前 3 位数字在第 3 行中。我们只需要用零填充它，然后可以检查我们是否知道大于该数字的质数，但差值必须小于 100（以便保留前导数字）。但是，如果我们有一个候选素数的排序数组，则只需要在该数组中进行二分搜索即可。