0

我一直在看一个电视选秀节目，一个人刚刚挑战整个国家（！）来解决一个问题。我觉得我可以写一个小脚本来解决它，但我仍然需要以某种方式识别问题。所以问题是这样的：

    +---+---+---+
    |   |   |   |  -->
    +---+---+---+
    |   |   |   |  -->  sum of
    +---+---+---+       3 rows
    |   |   |   |  -->
    +---+---+---+

      |   |   |     also sum of
      v   v   v     2 diagonals
       sum of
       3 columns

将数字从1到写到9上面的正方形中，以获得所有标记线的相同总和（例如 3 行、3 列和 2 条对角线的总和）。

然后，他通过临时扩展大正方形并按以下顺序写下数字，继续展示此问题实例的解决方案：

        +---+
        | 3 |
    +---+---+---+
    | 2 |   | 6 |
+---+---+---+---+---+
| 1 |   | 5 |   | 9 |
+---+---+---+---+---+
    | 4 |   | 8 |
    +---+---+---+
        | 7 |
        +---+

然后，他删除了多余的方格，并将其中的值分别放在最远的空方格中：

    +---+---+---+
    | 2 | 7 | 6 |
    +---+---+---+
    | 9 | 5 | 1 |
    +---+---+---+
    | 4 | 3 | 8 |
    +---+---+---+

然后他得到了总和：

rows:
2 + 7 + 6 = 15
9 + 5 + 1 = 15
4 + 3 + 8 = 15

columns:
2 + 9 + 4 = 15
7 + 5 + 3 = 15
6 + 1 + 8 = 15

diagonals:
2 + 5 + 8 = 15
6 + 5 + 4 = 15

所以问题是用 100 x 100 的正方形来解决这个问题。

  1. 这是什么问题？
  2. NP完全吗？
  3. 我该如何解决这个问题？

我可能记错了一些细节，但它不在 youtube 上，所以请随时建议对问题进行更改。

注意电视很棒

4

2 回答 2

2

这样的正方形被称为 MAGIC SQUARES。在http://en.wikipedia.org/wiki/Magic_square#Method_for_constructing_a_magic_square_of_odd_order了解他们的构造

于 2012-11-24T21:41:53.237 回答
2

它被称为“魔方”，维基百科提供了一些算法示例来生成魔方。

于 2012-11-24T21:33:00.907 回答